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$

1 Answer 1

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$
3
  • $\begingroup$ So this is randomized speedup? $\endgroup$
    – Turbo
    Feb 18, 2017 at 21:45
  • $\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$
    – Turbo
    Feb 19, 2017 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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