Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NEWTON POLYTOPE:
Reports tagged with Newton polytope:
TR15-171 | 28th October 2015
Joshua Grochow

#### Monotone projection lower bounds from extended formulation lower bounds

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

ISSN 1433-8092 | Imprint