pdf icon
Volume 13 (2017) Article 18 pp. 1-15
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
Received: November 10, 2015
Revised: July 27, 2016
Published: December 22, 2017
Download article from ToC site:
[PDF (255K)] [PS (1125K)] [Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
Keywords: lower bounds, algebraic circuit complexity, extended formulations of polytopes, Newton polytope, monotone formula, monotone circuit, projection, permanent, VNP, matching
Categories: complexity theory, lower bounds, algebraic complexity, polytopes, extended formulations, linear programming, monotone formula, monotone circuits, projection, permanent, VNP, matching, short
ACM Classification: F.1.3, F.2.1, G.1.6
AMS Classification: 68Q15, 68Q17, 90C05, 15A15, 05C70

Abstract: [Plain Text Version]

$ \newcommand{\R}{{\mathbb R}} \newcommand{\cclass}[1]{{\textsf{#1}}} $

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 subexponential-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 $\cclass{VNP}_{\R}$ under monotone p-projections.
  2. The cut polynomials and the perfect matching polynomial (or “unsigned Pfaffian”) are not monotone p-projections of the permanent. The latter, over the Boolean and-or semi-ring, 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.