# Computing the permanent with polylog size matrices

The complexity of computing the permanent of a $l\times l$ binary matrix is known to be $\#\mathsf{P}$-complete, from the famous result of Valiant, where $l = \Theta(n)$.

We know that the problem is not in $\mathsf{P}$, unless $l = \mathcal{O}(\log_2 n)$. What can we say about the complexity of the problem when $l = \mathcal{o}(n)$ as well as $\log_2 n = \mathcal{o}(l)$ ? For example, if $l = \text{polylog}(n)$ ?

Does the problem remain $\#\mathsf{P}$-complete ? Or is it complete for a class in some level of the polynomial hierarchy ?

• I think you mean Valiant, not Vazirani. – Michael Lampis Jan 7 '14 at 17:06
• So your input is a polylog-sized description of a matrix plus some padding to make the input length n? If so, we can use the exponential time algorithm for the permanent to compute it in quasi-polynomial time (in n), so it's certainly not hard for NP (or any superset, such as #P) unless ETH fails. – Yonatan N Jan 7 '14 at 19:20
• ${\bf \#P}$ complete under Turing reductions. – Tayfun Pay Jan 7 '14 at 21:15
• @TayfunPay Could you kindly tell me why ? A citation would be great. – Pavithran Iyer Jan 7 '14 at 22:39
• This one might be a related question: cstheory.stackexchange.com/questions/20510/… – Pavithran Iyer Jan 9 '14 at 14:05