Algorithm for general p

[andreas bjorklund]

Show that one can compute per(A) mod p^{cn/p} for some c>0 in time 2^{(1-Omega(1/(p log p)))n} for every prime p. (I think I know how to do this but there may very well be even better ways of doing it. I don't want to "destroy" your innovation power by telling you just yet how my algorithm goes :-) )

This would get us via the Chinese Remainder Theorem (CRT) that you can compute the permanent of an integer matrix whose absolute value you know is bounded from above by d^n in 2^{(1-Omega(1/(d log d)))n} time.

For instance, a random matrix with each element u.i.d. in {-1,1} has absolute permanent < (2sqrt(n))^n w.h.p. For these matrices the new algorithm would run in

2^(n-Omega(sqrt(n/log n))) time,

meeting the runtime guarantee I found in http://arxiv.org/abs/1211.0391.

Coincidence?

[andreas bjorklund]

It should hold that sum_(p<m, p prime) (log p)/p = log m + O(1), but I cannot find the reference I found before. This means that if |per A|<d^n, then we only need to use primes up to d to decide per A via CRT.

[Isak Lyckberg]

I understand that the result is due to Chebyshev, and is explained here. I assume this should suffice as a reference.