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$

1 Answer 1

6
$\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
  • 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$
    – Turbo
    Sep 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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