5
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.]

$\endgroup$
  • $\begingroup$ So this is randomized speedup? $\endgroup$ – T.... Feb 18 '17 at 21:45
  • $\begingroup$ Yes, but it can be derandomized by standard techniques: en.m.wikipedia.org/wiki/Method_of_conditional_probabilities $\endgroup$ – Andreas Björklund Feb 19 '17 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$ – T.... Feb 19 '17 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.