Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR15-171 | 23rd December 2016 18:03

Monotone projection lower bounds from extended formulation lower bounds

RSS-Feed




Revision #2
Authors: Joshua Grochow
Accepted on: 23rd December 2016 18:03
Downloads: 983
Keywords: 


Abstract:

In this short note, we show that the Hamiltonian Cycle polynomial is not a monotone sub-exponential-size projection of the permanent; this both rules out a natural attempt at a monotone lower bound on the Boolean permanent, and shows that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. We also show that the cut polynomials and the perfect matching polynomial (or ``unsigned Pfaffian'') are not monotone p-projections of the permanent. The latter can be interpreted as saying that there is no monotone projection reduction from counting perfect matchings in general graphs to counting perfect matchings in bipartite graphs, putting at least one theorem behind the well-established intuition. As the permanent is universal for monotone formulas, these results also imply exponential lower bounds on the monotone formula size and monotone circuit size of these polynomials. To prove these results we introduce a new connection between monotone projections of polynomials and extended formulations of linear programs that may have further applications.



Changes to previous version:

To appear in Theory of Computing (ToC; http://theoryofcomputing.org/). This version has benefited from anonymous reviewers at ToC. In particular, monotone formula and circuit size lower bounds were added.


Revision #1 to TR15-171 | 3rd November 2015 18:49

Monotone projection lower bounds from extended formulation lower bounds


Abstract:

In this short note, we show that the Hamilton Cycle polynomial is not a monotone sub-exponential-size projection of the permanent; this both rules out a natural attempt at a monotone lower bound on the Boolean permanent, and shows that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. We also show that the cut polynomials and the perfect matching polynomial (or ``unsigned Pfaffian'') are not monotone p-projections of the permanent. The latter can be interpreted as saying that there is no monotone projection reduction from counting perfect matchings in general graphs to counting perfect matchings in bipartite graphs, putting at least one theorem behind the well-established intuition. To prove these results we introduce a new connection between monotone projections of polynomials and extended formulations of linear programs that may have further applications.



Changes to previous version:

New connection relating bipartite and general perfect matchings. Clarified that results hold over many semi-rings, including the Boolean and-or semi-ring. Significantly updated discussion and open questions.


Paper:

TR15-171 | 28th October 2015 19:46

Monotone projection lower bounds from extended formulation lower bounds





TR15-171
Authors: Joshua Grochow
Publication: 28th October 2015 19:57
Downloads: 1471
Keywords: 


Abstract:

In this short note, we show that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections and extended formulations of linear programs that may have further applications.


Comment(s):

Comment #1 to TR15-171 | 27th March 2016 18:11

Clique, Permanent and Monotone projections





Comment #1
Authors: Nitin Saurabh
Accepted on: 27th March 2016 18:11
Downloads: 1491
Keywords: 


Abstract:

We extend Grochow's argument to show that Clique itself is not a monotone p-projection of the Permanent. Thus the possibility of transferring monotone lower bounds for Clique to Permanent, via projections, cannot work.




ISSN 1433-8092 | Imprint