Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
Abstract
In this short note, we reduce lower bounds on monotone projections of polynomials to lower bounds on extended formulations of polytopes. Applying our reduction to the seminal extended formulation lower bounds of Fiorini, Massar, Pokutta, Tiwari, & de Wolf (STOC 2012; J. ACM, 2015) and Rothvoss (STOC 2014; J. ACM, 2017), we obtain the following interesting consequences. 1. The Hamiltonian Cycle polynomial is not a monotone subexponentialsize 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 nonnegative polynomials in VNP$_{\mathbb R}$ under monotone pprojections. 2. The cut polynomials and the perfect matching polynomial (or "unsigned Pfaffian") are not monotone pprojections of the permanent. The latter, over the Boolean andor semiring, rules out monotone reductions in one of the natural approaches to reducing perfect matchings in general graphs to perfect matchings in bipartite graphs. 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.
 Publication:

arXiv eprints
 Pub Date:
 October 2015
 arXiv:
 arXiv:1510.08417
 Bibcode:
 2015arXiv151008417G
 Keywords:

 Computer Science  Computational Complexity;
 68Q15;
 68Q17;
 90C05;
 15A15;
 05C70;
 F.1.3;
 F.2.1;
 G.1.6
 EPrint:
 Published in Theory of Computing, Volume 13 (2017), Article 18