2
$\begingroup$

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}$?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 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$ – T.... Sep 26 '13 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$ – Joshua Grochow Sep 26 '13 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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