Can some one suggest a good source for VNP completeness of Permanent. I tried reading it from book on Algebraic complexity theory by Burgisser,clausen,shokrollahi,lickteig. And What is the best known lower-bound on determinental complexity of $PERM_{n}$?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
The place from which I had read the proof was Completeness and Reduction in Algebraic Complexity Theory by Peter Bürgisser (.ps). As for the determinental complexity of the permanent, the best lower bound known so far is $\Omega(n^2)$ by Mignon and Ressayre.
-
2$\begingroup$ Jin Yi Cai et al have extended Mignon's result to char $p$. The basic idea is to consider Hessian but specific matrices differ. $\endgroup$– TurboSep 26, 2013 at 14:40
-
3$\begingroup$ Landsberg, Manivel, and Ressayre (arxiv.org/abs/1004.4802) have also extended the Mignon--Ressayre result from determinantal complexity to border-determinantal complexity. (The LMR paper is fairly advanced from this point of view, but I thought I should at least mention that it was out there.) $\endgroup$ Sep 26, 2013 at 19:06