Recently Landsberg and Ressayre announced an exponential lower bound for permanent's determinantal complexity assuming certain symmetry conditions.

What is the status of the problem of Permanent's determinantal complexity after this proof? What more needs to be done to close the loop? Will the natural proof barrier affect whatever needs to be done? In short what progress does this proof intend to give on this important problem?

  • $\begingroup$ Mark Rudelson, Ofer Zeitouni has one paper arxiv.org/abs/1301.6268 , in which, they prove that for a large class of graphs satisfying an appropriate expansion property, the Barvinok--Godsil-Gutman estimator for the permanent achieves sub-exponential errors with high probability. $\endgroup$
    – user17918
    Sep 22 '15 at 7:41
  • $\begingroup$ @RupeiXu What is the implication of your attached paper? $\endgroup$
    – user34945
    Feb 7 '16 at 8:22

Your Answer

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