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.
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.
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.
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.
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.
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.
