<p>One can compute it in $\sum_{i=0}^{t-1} \binom{n}{i}n^3$ expected time. Consider a $(n+1)\times(n+1)$ matrix</p>

<p>$M^+ = \left[\begin{array}{ll} M &amp; v \\ 0 &amp; 1 \end{array}\right],$</p>

<p>where $v$ is a random vector with elements chosen from $\{0,1\}$, uniformly and independently. Note that $\operatorname{per}(M^+)=\operatorname{per}(M)$. Now consider Ryser's formula</p>

<p>$\operatorname{per}(M^+)=\sum_{(n+1)\in X\subseteq [n+1]} (-1)^{n+1-|X|}T(X)$, where $ T(X)=\prod_{i=1}^{n+1} \sum_{j\in X} M^+_{ij}.$</p>

<p>Note that for many $X$, the term T(X) will be zero modulo $2^t$, namely at least for all $X$'s that make $t$ or more row sums $\sum_{j\in X} M^+_{ij}=0 ( \operatorname{ mod} 2)$. We can list only those terms $X$ that stand a chance of contributing a non-zero term by solving $\sum_{i=0}^{t-1} \binom{n}{i}$ linear equation systems over GF($2$), where we guess what rows will be zero modulo $2$. In expectation there will be one solution for each guess, so by the linearity of expectation the runtime follows.</p>

<p>[This is proven in a paper by B., Husfeldt, and Lyckberg currently under submission.]</p>

CC BY-SA 3.0
2017-02-18T21:45:31.040Z
So this is randomized speedup?
Turbo
CC BY-SA 3.0
2017-02-19T09:12:12.853Z
Yes, but it can be derandomized by standard techniques: https://en.m.wikipedia.org/wiki/Method_of_conditional_probabilities
Andreas Björklund
CC BY-SA 3.0
2017-02-19T21:47:40.190Z
Then the $O(n^{4t-3})$ deterministic algorithm that Valiant gave is improved to deterministic $O(n^{t+3})$ complexity?
Turbo
CC BY-SA 3.0
2017-02-18T16:07:57.337Z
2017-02-18T16:07:57.337Z
Andreas Björklund
<p>Valiant showed $\mathsf{Per}(M)\bmod 2^t$ can be computed in $O(n^{4t-3})$ operations where $M\in\Bbb Z^{n\times n}$ holds. Has there been a better algorithm since then?</p>

<ds.algorithms><permanent>
On complexity of permanent ${}\bmod 2^t$?
Turbo
# On complexity of permanent ${}\bmod 2^t$?

(Asked by: username_0 on 2017-02-18)

Valiant showed $\mathsf{Per}(M)\bmod 2^t$ can be computed in $O(n^{4t-3})$ operations where $M\in\Bbb Z^{n\times n}$ holds. Has there been a better algorithm since then?

**Tags:** ds.algorithms, permanent


---

## 1 answers

### Answer by username_1 on 2017-02-18. Score: 9 | Accepted answer

One can compute it in $\sum\_{i=0}^{t-1} \binom{n}{i}n^3$ expected time. Consider a $(n+1)\times(n+1)$ matrix

$M^+ = \left[\begin{array}{ll} M & v \\ 0 & 1 \end{array}\right],$

where $v$ is a random vector with elements chosen from $\{0,1\}$, uniformly and independently. Note that $\operatorname{per}(M^+)=\operatorname{per}(M)$. Now consider Ryser's formula

$\operatorname{per}(M^+)=\sum\_{(n+1)\in X\subseteq [n+1]} (-1)^{n+1-|X|}T(X)$, where $ T(X)=\prod\_{i=1}^{n+1} \sum\_{j\in X} M^+\_{ij}.$

Note that for many $X$, the term T(X) will be zero modulo $2^t$, namely at least for all $X$'s that make $t$ or more row sums $\sum\_{j\in X} M^+\_{ij}=0 ( \operatorname{ mod} 2)$. We can list only those terms $X$ that stand a chance of contributing a non-zero term by solving $\sum\_{i=0}^{t-1} \binom{n}{i}$ linear equation systems over GF($2$), where we guess what rows will be zero modulo $2$. In expectation there will be one solution for each guess, so by the linearity of expectation the runtime follows.

[This is proven in a paper by B., Husfeldt, and Lyckberg currently under submission.]

> **Comments:**
> **username_0**: So this is randomized speedup?  
> **username_1**: Yes, but it can be derandomized by standard techniques: https://en.m.wikipedia.org/wiki/Method_of_conditional_probabilities  
> **username_0**: Then the $O(n^{4t-3})$ deterministic algorithm that Valiant gave is improved to deterministic $O(n^{t+3})$ complexity?  

---

