Monotone projection lower bounds from extended formulation lower bounds

摘要

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