The tag has no wiki summary.

learn more… | top users | synonyms

13
votes
1answer
370 views

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

This is a follow up to this question, and is related to this question of Shiva Kinali. It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use ...
19
votes
2answers
763 views

Lower bound for determinant and permanent

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
14
votes
2answers
304 views

A question to the #P-complete proof of the permanent from Ben-Dor/Halevi

In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is $\#P$-complete. In the later part of the paper, they show the reduction chain \begin{equation} \text{IntPerm} \propto ...
3
votes
0answers
101 views

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