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?
1 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.]
-
-
$\begingroup$ Yes, but it can be derandomized by standard techniques: en.m.wikipedia.org/wiki/Method_of_conditional_probabilities $\endgroup$ Feb 19, 2017 at 9:12
-
$\begingroup$ Then the $O(n^{4t-3})$ deterministic algorithm that Valiant gave is improved to deterministic $O(n^{t+3})$ complexity? $\endgroup$– TurboFeb 19, 2017 at 21:47