Authors Joshua A. Grochow,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15
www.theoryofcomputing.org
Monotone Projection Lower Bounds from
Extended Formulation Lower Bounds
Joshua A. Grochow∗
Received November 10, 2015; Revised July 27, 2016; Published December 22, 2017
Abstract: In this short note, we reduce lower bounds on monotone projections of polyno-
mials 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 VNPR 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.
ACM Classification: F.1.3, F.2.1, G.1.6
AMS Classification: 68Q15, 68Q17, 90C05, 15A15, 05C70
Key words and phrases: lower bounds, algebraic circuit complexity, extended formulations of polytopes,
Newton polytope, monotone formula, monotone circuit, projection, permanent, VNP, matching
∗ The author was supported during this work by an Omidyar Fellowship from the Santa Fe Institute.
© 2017 Joshua A. Grochow
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a018
J OSHUA A. G ROCHOW
1 Introduction
The permanent
permn (X) = ∑ x1,π(1) x2,π(2) · · · xn,π(n)
π∈Sn
(where Sn denotes the symmetric group of all permutations of {1, . . . , n}) has long fascinated combina-
torists [17, 14, 18], more recently physicists [33, 2], and, since Valiant’s seminal paper [29], has also
been a key object of study in computational complexity. Despite its beauty, the permanent has some
computational quirks: in particular, although the permanent of integer matrices is #P-complete and the
permanent is VNP-complete in characteristic zero, the permanent mod 2 is the same as the determinant,
and hence can easily be computed. In fact, computing the permanent mod 2k is easy for any k [29],
though the proof is more involved. Modulo any odd number n, the permanent of integer matrices is
Modn P-complete [29].
In contrast, the seemingly similar Hamiltonian Cycle polynomial,
HCn (X) = ∑ x1,σ (1) x2,σ (2) · · · xn,σ (n) ,
n-cycles σ
where the sum is only over n-cycles rather than over all permutations, does not have these quirks: the
Hamiltonian Cycle polynomial is VNP-complete over any ring R [28] and Modn P-complete for all n (that
is, counting Hamiltonian cycles is complete for these Boolean counting classes).
Jukna [12] observed that, over the Boolean semi-ring, if the Hamiltonian Cycle polynomial were
Ω(1)
a monotone p-projection of the permanent, there would be a 2n lower bound on monotone circuits
computing the permanent, a lower bound that still remains open. (The current record is still Razborov’s
nΩ(log n) [20].) Even over the real numbers, such a monotone p-projection would give an alternative proof
Ω(1)
of a 2n lower bound on the permanent. (Jerrum and Snir [11] already showed the permanent requires
monotone circuits of size 2Ω(n) over R and over the tropical (min, +) semi-ring.) Here, by building on
Fiorini et al.’s [8] and Rothvoss’s [22] extended formulation lower bound for the TSP polytope, we show
that no such monotone reduction exists—over R, nor over the tropical semi-ring, nor over the Boolean
semi-ring—by connecting monotone p-projections to extended formulations of polytopes.
In the past five years, there has been exciting progress on extended formulations of polytopes, which
we leverage by using our new connection. Indeed, with this connection in hand, one immediately gets
a monotone projection lower bound from essentially any lower bound on extended formulations. An
extended formulation of a polytope P is another polytope in a higher-dimensional space that projects down
onto P by an affine linear map. Since linear programming can be solved in polynomial time, and optima
of linear programs are preserved by affine linear projections, solving the LP on the extended formulation
allows one to solve the LP on the original polytope. Thus, if a polytope P has an extended formulation
that is in some sense “small,” one can solve LP optimization problems over P by instead solving them
over its smaller extended formulation; if the extended formulation is small enough, this would yield
a polynomial-time algorithm. To show that such an extended formulation is not small, it suffices to
prove a lower bound on its number of facets. In 1988, Yannakakis [34] ruled out a large and natural
class of extended formulations of the TSP polytope—so-called symmetric extended formulations—thus
showing that a certain natural class of algorithms for an NP-complete problem indeed did not solve it in
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 2
M ONOTONE P ROJECTION L OWER B OUNDS FROM E XTENDED F ORMULATION L OWER B OUNDS
polynomial time, and ruling out several attempted proofs that P = NP. But for more than 20 years, it was
an open question of how to remove the condition of symmetry from Yannakakis’s result. In a landmark
result, Fiorini, Massar, Pokutta, Tiwary, and de Wolf [8] achieved this, by showing an exponential lower
bound on arbitrary extended formulations of several different polytopes. We will use their lower bound
on the cut polytope below. Rothvoss [22] then showed such lower bounds on several other polytopes; we
use his lower bound on the TSP polytope, improving that of Fiorini et al. [8], to get the result above.
We use the same connection to extended formulations, now in combination with Rothvoss’s lower
bound on extended formulations of the perfect matching polytope [22], to show that the perfect matching
polynomial or “unsigned Pfaffian”
n n
1
∑ ∏ xπ(2i−1),π(2i) =
2n n! π∈S ∑ ∏ xπ(2i−1),π(2i)
2n i=1 π∈S2n i=1
π(1)<π(3)<···<π(2n−1)
π(2k−1)<π(2k) ∀k
is not a monotone p-projection of the permanent. As the perfect matching polynomial counts perfect
matchings in a general graph, and the permanent counts perfect matchings in a bipartite graph, it is
interesting to consider this result in the context of the difference in complication between algorithms for
finding perfect matchings in bipartite graphs (e. g., [19, 7]) and those for finding perfect matchings in
general graphs (e. g., [6, 16, 32, 27]).
Remark 1.1 (On the Boolean semi-ring). Our results also hold for formal polynomials over the Boolean
semi-ring B = ({0, 1}, ∨, ∧). Over the Boolean semi-ring, the permanent is the indicator function of the
existence of a perfect matching in a bipartite graph, and the unsigned Pfaffian is the indicator function of
a perfect matching in a general graph. However, over B, each function is represented by more than one
formal polynomial, and we do not know how to extend our results to the setting of functions over B. See
Section 5 for details and specific questions.
We also use the same technique, this time in combination with the lower bound of Fiorini et al. on
extended formulations of the cut polytope [8], to show that the cut polynomials
Cutq = ∑ ∏ xiq−1
j
A⊆[n] i∈A, j∈A
/
are not monotone p-projections of the permanent. Perhaps the main complexity-theoretic interest in the
cut polynomials is that Cutq over the finite field Fq was (until recently [15]) the only known example of
a natural polynomial that is neither expected to be in VPFq nor to be VNPFq -complete. (Indeed, either
its membership in VPFq or its VNPFq -completeness would imply the collapse of the polynomial-time
hierarchy [4], contradicting a standard complexity-theoretic hypothesis.) There Bürgisser also showed that
if VPFq 6= VNPFq then such polynomials of intermediate complexity must exist. In that paper, Bürgisser
asked whether the cut polynomials, considered as polynomials over the rationals, were VNPQ -complete.1
Although our results don’t touch on this question, these previous results motivate the study of these
polynomials over Q.
1 Cut2 was subsequently shown to be VNP
Q -complete under circuit reductions [23]; its completeness under projections
remains open.
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 3
J OSHUA A. G ROCHOW
Because the permanent is universal for monotone formulas, our lower bounds also imply exponential
lower bounds on the monotone algebraic formula size—and, by balancing algebraic circuits, monotone
algebraic circuit size—of these polynomials; see Section 4.2.
Finally, we note that our results shed a little more light on the intricacy of the known VNP-
completeness proofs for the permanent [29, 3, 1]. Namely, prior to our result, the fact that the permanent
is not hard modulo 2 already implied that any completeness result must use 2 in a “bad” way: for example,
dividing by 2 somewhere. This is indeed true of Valiant’s original proof [29], Ben-Dor & Halevi’s
proof [3], and Aaronson’s quantum linear-optics proof [1].
Remark 1.2. One might hope for a classical analogue of Aaronson’s quantum proof, using the character-
ization of BPP in terms of stochastic matrices as a replacement for the characterization of BQP using
unitary matrices. However, our result indicates that the most straightforward adaptation of Aaronson’s
proof from the BQP setting to the BPP setting cannot work, as the use of stochastic matrices in this
manner would produce a monotone reduction.
Our results also imply the necessity of the use of negative numbers in Valiant’s 4 × 4 gadget [29,
p. 195] and Ben-Dor and Halevi’s 7 × 7 gadget [3, App. A]. In light of these results, Valiant’s 4 × 4 gadget
may perhaps seem less mysterious than the fact that such a gadget exists that is only 4 × 4!
To prove these results, we show that a monotone projection between non-negative polynomials
essentially implies that the Newton polytope of one polynomial is an extension of the Newton polytope
of the other (Lemma 3.1), and then apply known lower bounds on the extension complexity of certain
polytopes. We hope that the connection between Newton polytopes, monotone projections, and extended
formulations finds further use.
2 Preliminaries
A polynomial f (x1 , . . . , xn ) is a (simple) projection of a polynomial g(y1 , . . . , ym ) if f can be constructed
from g by replacing each yi with a constant or with some x j . The polynomial f is an affine projection of g
if f can be constructed from g by replacing each yi with an affine linear function πi (~x). When we say
“projection” we mean simple projection. Given two families of polynomials, ( fn ) and (gn ), if there is a
function p(n) such that fn is a projection of g p(n) for all sufficiently large n, then we say that ( fn ) is a
projection of (gn ) with blow-up p(n). If ( fn ) is a projection of (gn ) with polynomial blow-up, we say
that ( fn ) is a p-projection of (gn ).
Over any subring of R—or more generally any totally ordered semi-ring (see below)—a monotone
projection is a projection in which all constants appearing in the projection are non-negative. Monotone
p-projection is defined analogously.
To each monomial x1e1 · · · xnen we associate its exponent vector (e1 , . . . , en ), as a point in Nn ⊆ Rn .
These vectors determine the Newton polytope, defined as follows.
Definition 2.1. The Newton polytope of a polynomial f (x1 , . . . , xn ), denoted Newt( f ), is the convex hull
in Rn of the exponent vectors of all monomials appearing in f with non-zero coefficient.
A polytope is integral if all its vertices have integer coordinates; note that Newton polytopes are
always integral. A face of a polytope P is the intersection of P with a linear space L such that none of the
interior points of P lie in L.
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 4
M ONOTONE P ROJECTION L OWER B OUNDS FROM E XTENDED F ORMULATION L OWER B OUNDS
For a polytope P, let c(P) denote the “complexity” of P, as measured by the minimal number of
linear inequalities needed to define P (equivalently, the number of faces of P of dimension dim P − 1).
A polytope Q ⊆ Rm is an extension or extended formulation of P ⊆ Rn if there is an affine linear
map ` : Rm → Rn such that `(Q) = P. The extension complexity of P, denoted xc(P), is the minimum
complexity of any extension of P (of any dimension): xc(P) = min{c(Q) | Q is an extension of P}.
The m-th cycle cover polytope (also known as the bipartite perfect matching polytope) is the convex
2
hull in Rm of the {0, 1}-indicator functions of the directed cycle covers of the complete directed graph
with self-loops on m vertices. The cycle cover polytope is the Newton polytope of the permanent, as each
monomial in the permanent corresponds to such a cycle cover.
A totally ordered semi-ring (we only consider commutative ones here) is a totally ordered set together
with two operations, denoted (R, ≤, ×, +, 1, 0) such that (R, ×, 1) and (R, +, 0) are both commutative
monoids, × distributes over +, 0 × a = 0 for all a, a + c ≤ b + c whenever a ≤ b, and ac ≤ bc whenever
a ≤ b and 0 ≤ c. An element c of a totally ordered semi-ring is non-negative if 0 ≤ c, and is positive if
furthermore c 6= 0. We will restrict our attention to non-zero totally ordered semi-rings; equivalently, we
assume 1 6= 0. Note that in a totally ordered semiring, 1 + · · · + 1 is never zero.
The following totally ordered semi-rings are of particular interest.
• The real numbers with its usual ordering and arithmetic operations, (R, ≤, ×, +).
• The so-called “tropical semi-ring” (R, ≤, +, min), which is the real numbers with its usual ordering,
where the product is taken to be real addition and the addition operation is taken to be the minimum.
• The Boolean and-or semi-ring B = ({0, 1}, ≤, ∧, ∨), where 0 ≤ 1.
To get a feel for the latter two semi-rings, note that polynomials over the tropical semi-ring generally
compute some optimization problem, and over B generally compute a decision problem. For example, the
Hamiltonian Cycle polynomial over the tropical semi-ring computes the Traveling Salesperson Problem,
and over B, the indicator function of the existence of a Hamiltonian cycle. Note that over R, if two formal
polynomials compute the same function then they must be identical, but this is not true over the tropical
or Boolean semi-rings.
3 Main lemma
Lemma 3.1. Let R be a totally ordered semi-ring, and let f (x1 , . . . , xn ) and g(y1 , . . . , ym ) be polynomials
over R with non-negative coefficients. If f is a monotone projection of g, then some face of Newt(g) is an
extension of Newt( f ). In particular, xc(Newt( f )) ≤ c(Newt(g)).
Proof. Under simple projections, a monomial in the yi maps to some scalar multiple of a monomial in
the x j (possibly the empty monomial, resulting in a constant term, or possibly the zero multiple, resulting
in zero). Let π be a monotone projection map, defined on the variables yi , and extended naturally to
monomials and terms in the yi . (Recall that a term of a polynomial is a monomial together with its
coefficient.) Since each term t of g is a monomial multiplied by a positive coefficient, and since π is
non-negative, π(t) is either zero or a single monomial in the x j with nonzero coefficient. The former
situation can happen only if t contains some variable yi such that π(yi ) = 0. Let ker(π) denote the
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 5
J OSHUA A. G ROCHOW
set {yi | π(yi ) = 0}. Thus, for every term t of g that is disjoint from ker(π), π(t) actually appears in
f —possibly with a different coefficient, but still non-zero—since no terms can cancel under projection
by π.
Let e1 , . . . , em be the coordinate functions on Rm , the ambient space of Newt(g); that is, ei : Rm → R
is projection onto the i-th coordinate. Let K denote the subspace of Rm defined by the equations ei = 0 for
each i such that yi ∈ ker(π). Let P be the intersection of Newt(g) with K, considered as a polytope in K;
since all vertices of Newt(g) are non-negative, intersecting Newt(g) with a coordinate hyperplane, ei = 0,
results in a face of Newt(g), and thus P is a face of Newt(g). Note that P is exactly the convex hull of the
exponent vectors of monomials in g that are disjoint from ker(π). In particular, since π is multiplicative
on monomials, it induces a linear map `π from K to Rn (the ambient space of Newt( f )). By the previous
paragraph, the exponent vectors of f are exactly `π applied to the exponent vectors of monomials in g
that are disjoint from ker(π). By the linearity of `π and the convexity of P and Newt( f ), we have that
Newt( f ) = `π (P), so P is an extension of Newt( f ). Since P is defined by intersecting Newt(g) with
additional linear equations, the lemma follows.
Several partial converses to our Main Lemma also hold. Perhaps the most natural and interesting of
these is the following.
Observation 3.2. Let R be a totally ordered semi-ring. Given any sequence of non-negative integral
polytopes Pn ⊆ Rn such that the poly(n)-th cycle cover polytope is an extension of Pn along an affine
linear map `n : Rpoly(n) → Rn with integer coefficients of polynomial bit-length, there is a sequence of
polynomials ( fn ) ∈ VNPR such that Newt( fn ) = Pn and f is a monotone p-projection of the permanent.
Proof. Let Cm denote the m-th cycle cover polytope, let m(n) be a polynomial such that Cm(n) is an
extended formulation of Pn , and let b(n) be a polynomial upper bound on the bit-length of the coefficients
of `n . Let Vm denote the vertex set of the cycle cover polytope, i. e., the incidence vectors of cycle covers.
Define fn as
∑ ~y`n (~e) ,
~e∈Vm
0 e0 e0 e0
where ~y = (y1 , . . . , yn ), and the vector notation ~y~e is defined as y11 y22 · · · ynn . Note that `n has only integer
coefficients by assumption, and each ~e ∈ Vm is integral, so the vector `n (~e) is integral, and the above
expression is a well-defined Laurent polynomial. To see that all the exponents are non-negative, note
that by assumption each `n (~e) lies in Pn , which is itself a non-negative polytope, so the above expression
is in fact a well-defined polynomial. By construction, every exponent vector of fn is in `n (Cm(n) ) = Pn .
Conversely, every vertex of Pn is an exponent vector of fn , since its coefficient is simply 1 + 1 + · · · + 1,
which is never zero in a totally ordered semi-ring. (Without noting this, it would be possible that k distinct
vertices in Vm would get mapped to the same point under `n , and then the corresponding monomials ~y`n (~e)
might add up to 0 in fn .) Thus Newt( fn ) = Pn . Furthermore, fn is a monotone nonlinear projection of the
permanent using the map xi j 7→ ~y`((0,0,...,1,...,0)) , where the 1 is in the (i, j) position. Using the universality
of the permanent and repeated squaring, this can easily be turned into a monotone simple projection of
the permanent of size poly(m(n), b(n)).
This can be generalized from the cycle cover polytopes and the permanent to arbitrary integral
polytopes and the natural associated polynomial (the sum over all monomials whose exponent vectors are
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 6
M ONOTONE P ROJECTION L OWER B OUNDS FROM E XTENDED F ORMULATION L OWER B OUNDS
vertices of the polytope), but at the price of using “monomial projections”—in which each variable is
replaced by a monomial—rather than simple projections. There ought to be a version of this observation
over sufficiently large fields and allowing rational coefficients in `, using Strassen’s division trick [26], but
the only such versions the author could come up with had so many hypotheses as to seem uninteresting.
4 Applications
4.1 Projection lower bounds
Remark 4.1. The following theorems hold over any totally ordered semi-ring, including the Boolean
and-or semi-ring, the non-negative real numbers under multiplication and addition, and the tropical
semi-ring of real numbers under addition and min. To see that this introduces no additional difficulty,
note that over any totally ordered semi-ring R, the Newton polytope of a polynomial over R is still a
polytope in a vector space over the real numbers, so standard results on polytopes and the cited results on
extension complexity still apply.
Theorem 4.2 (Main Lemma + Rothvoss’s TSP polytope lower bound). Over any totally ordered semi-
ring, the Hamiltonian Cycle polynomial is not a monotone affine p-projection of the permanent; in fact,
any monotone affine projection from the permanent to the Hamiltonian Cycle polynomial has blow-up at
least 2Ω(n) .
We will need the following folklore lemma; as we could not find a proof in the literature, we a sketch
its well-known proof here for completeness, and so that it can be verified that the standard proof preserves
monotonicity.
Lemma 4.3 (Folklore). If an n-variable polynomial is an affine projection of the m × m permanent, then
it is a simple projection of the N × N permanent for N = m + (n + 1)m2 . The same holds with “affine
projection” replaced by “monotone affine projection” in both places.
Proof sketch. Let πi j (~x) be the affine linear function corresponding to the variable yi j of the m × m
permanent, and write πi j = a0 + a1 x1 + · · · + an xn . Let G be the complete directed graph with loops
on m vertices and edge weights yi j . Replace the edge (i, j) by n + 1 parallel edges with weights
a0 , a1 x1 , · · · , an xn . Add a new vertex on each of these parallel edges, splitting each parallel edge into two.
For the edge weighted a0 , the two edges have weights 1, a0 , and for the remaining edges the new edges
get weights ai , xi . On each of the added vertices, add a self-loop of weight 1. Now consider the permanent
of the weighted adjacency matrix of this edge-weighted directed graph. It is a simple exercise to see that
this has the desired effect. Note also that if the original affine projection π was monotone, then so is the
constructed simple projection.
Proof of Theorem 4.2. By Lemma 4.3, it suffices to show the result for simple projections. If the
Hamiltonian Cycle polynomial were a monotone projection of the permanent, then by the Main Lemma,
some face of Newt(perm) would be an extension of Newt(HC).
The Newton polytope of the permanent is the cycle cover polytope (see Section 2). The cycle cover
polytope can easily be described by the m2 inequalities asserting that all variables xi, j are non-negative,
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 7
J OSHUA A. G ROCHOW
together with the equalities asserting that each vertex has in-degree and out-degree exactly 1, namely
∑i xi, j = 1 for all j and ∑ j xi, j = 1 for all i. (It is easy to see that these are necessary; for sufficiency, see,
e. g., [25, Theorem 18.1].) Since equalities do not count towards the complexity of a polytope, we have
c(Newt(permm )) ≤ m2 .
But the Newton polytope of the n-th Hamiltonian Cycle polynomial is exactly the TSP polytope,
which, by a recent result by Rothvoss [22, Corollary 2], requires extension complexity 2Ω(n) .
Theorem 4.4 (Main Lemma + Rothvoss’s perfect matching polytope lower bound). Over any totally
ordered semi-ring, the perfect matching polynomial (or “unsigned Pfaffian”) is not a monotone affine
p-projection of the permanent; in fact, any monotone affine projection from the permanent to the perfect
matching polynomial has blow-up at least 2Ω(n) .
Proof. The proof is the same as for the Hamiltonian Cycle polynomial, using [22, Theorem 1] by
Rothvoss, which gives a lower bound of 2Ω(n) on the extension complexity of the perfect matching
polytope, which is the Newton polytope of the perfect matching polynomial.
Theorem 4.5 (Main Lemma + Fiorini et al.’s cut polytope lower bound). Over any totally ordered
semi-ring, for any q, the q-th cut polynomial is not a monotone affine p-projection of the permanent; in
fact, any monotone affine projection from the permanent to the q-th cut polynomial has blow-up at least
2Ω(n) .
Proof. Use [8, Theorem 7] by Fiorini et al. which says that xc(Newt(Cut2 )) ≥ 2Ω(n) , as Newt(Cut2 ) is
the cut polytope. The one additional observation we need is that Newt(Cutq ) is just the (q − 1)-scaled
version of Newt(Cut2 ), and this rescaling does not affect the extension complexity.
4.2 Monotone formula and circuit lower bounds
As pointed out by an anonymous reviewer, the universality of the permanent for formula size also holds
in the monotone setting, so lower bounds on monotone projections from the permanent imply the same
lower bounds on monotone formula size, and therefore quasi-polynomially related lower bounds on
monotone circuit size. We assume circuits only have gates of bounded fan-in; with unbounded fan-in,
rather than losing a factor of a half in the exponent of the exponent, we lose a factor of a third.
Proposition 4.6. Any polynomial computable by a monotone formula of size s is a monotone projection
of perms+1 .
Proof. The proof of the universality of the permanent given in [5, Proposition 2.16] works mutatis
mutandis in the monotone setting.
As a consequence of this, Theorems 4.2–4.5 are nearly tight, since every monotone polynomial in n
variables of poly(n) degree can be written as a monotone formula of size 2O(n log n) (write it as a sum of
monomials).
Corollary 4.7. Over any totally ordered semi-ring, any monotone formula computing the Hamiltonian
Ω(n) .
√ at least 2
Cycle polynomial, the perfect matching polynomial, or the q-th cut polynomial has size
Consequently, any monotone circuit computing these polynomials has size at least 2 Ω( n) .
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 8
M ONOTONE P ROJECTION L OWER B OUNDS FROM E XTENDED F ORMULATION L OWER B OUNDS
For the cut polynomials, we believe this result to be new. For the other polynomials, this provides a
new proof of (slightly weaker versions of) previously known lower bounds. Namely, Jerrum and Snir
gave a lower bound of (n − 1)((n − 2)2n−3 + 1) = 2n+Ω(log n) on the monotone circuit size of HC [11,
Section 4.4], and a lower bound of n(2n−1 − 1) on the monotone circuit size of the permanent [11,
Section 4.3]. As the permanent is a monotone projection of the perfect matching polynomial—namely,
restrict the perfect matching polynomial to a bipartite graph, e. g., by setting xi j = 0 whenever i and j
have the same parity—the same lower bound holds for the perfect matching polynomial.
Proof. The first part follows by combining Proposition 4.6 with Theorems 4.2–4.5. The second part
follows from the fact that monotone circuits of size s can be balanced to have size poly(s) and depth
O(log2 s) (the proof in [31] works mutatis mutandis in the monotone setting), which can then be converted
2
to monotone formulas of size sO(log s) = 2O(log s) by the usual conversion from bounded fan-in circuits
to formulas. If there is a monotone circuit of size s computing any of these polynomials, there is thus a
2 1/2
monotone formula of size 2O(log s) , which must be at least 2Ω(n) , so s ≥ 2Ω(n ) .
5 Open questions
Despite the common feeling that Razborov’s super-polynomial lower bound [20] on monotone Boolean
circuits for CLIQUE “finished off” monotone Boolean circuit lower bounds, several natural and interesting
question remain. For example, does Directed s-t Connectivity require monotone Boolean circuits of size
Ω(n3 )? (A matching upper bound is given by the Bellman–Ford algorithm.) Is there a monotone Boolean
reduction from general perfect matching to bipartite perfect matching? A positive answer to the following
question would rule out such monotone (projection) reductions.
Open Question 5.1. Extend Theorem 4.4 from formal polynomials over the Boolean semi-ring to Boolean
functions.
However, there are even easier questions, intermediate between the Boolean function case and the
algebraic case considered in this paper; Jukna [13] discusses the notion of one polynomial “counting”
another, which means that they agree on all {0, 1} inputs.
Open Question 5.2. Prove that no monotone polynomial-size projection of the permanent agrees with the
perfect matching polynomial on all {0, 1} inputs (“counts the perfect matching polynomial”). Similarly,
prove that no monotone polynomial-size projection of the permanent counts the Hamiltonian cycle
polynomial.
S. Jukna points out (personal communication) that projections of the s-t connectivity polynomial
correspond, even in the Boolean setting, to switching-and-rectifier networks, so the known lower bounds
on monotone switching-and-rectifier networks (see, e. g., the survey [21]) imply that the Hamiltonian
path polynomial and the permanent are not monotone p-projections of the s-t connectivity polynomial,
even over the Boolean semi-ring. This helps explain why the only known monotone lower bound
on the s-t connectivity polynomial that we are aware of [13] goes by a somewhat roundabout proof:
Razborov’s lower bound on CLIQUE [20], followed by Valiant’s reduction from the clique polynomial
to the Hamiltonian path polynomial [28], followed by a standard reduction from Hamiltonian path to
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 9
J OSHUA A. G ROCHOW
counting s-t paths. In the course of discussing this, we were led to the following question; although
the motivation for the question has since disappeared, it still seems like an interesting question about
polytopes, whose answer may require new methods.
Open Question 5.3 (S. Jukna, personal communication). Is the m-th s-t path polytope an extension of
the n-th TSP polytope (or n-th cycle cover polytope) with m ≤ poly(n)?
Since the separation problem for the s-t path polytope is NP-hard (see, e. g., [25, §13.1])—and
the cycle cover polytope has low (extension) complexity—answering this question negatively seems
to require more subtle understanding of these polytopes than “simply” an extended formulation lower
bound.
Another example of a natural polytope question with a similar flavor comes from the cut polynomials.
In combination with Bürgisser’s results and questions on the cut polynomials [4] (discussed in Section 1),
we are led to the following question.
Open Question 5.4. Is the m-th cut polytope an extension of the n-th TSP polytope, for m ≤ poly(n)?
A negative answer would show that Cutq is not complete for non-negative polynomials in VNPQ
under monotone p-projections, though as with the example of the permanent, this is not necessarily an
obstacle to being VNP-complete under general p-projections. Yet even the monotone completeness of the
cut polynomials remains open. In fact, even more basic questions remain open:
Open Question 5.5. Is every non-negative polynomial in VNP a monotone projection of the Hamiltonian
Cycle polynomial? Is there any polynomial that is “positive VNP-complete” in this sense?
To relate this to the current proofs of VNP-completeness of HCn , we need to draw a distinction.
Let VP≥0
R denote the polynomial families in VPR all of whose coefficients are non-negative, and let
mVPR (“monotone VP”) denote the class of families of polynomials with polynomially many variables,
of polynomial degree, and computable by polynomial-size monotone circuits over R. Similarly, define
VNP≥0R to be the non-negative polynomials in VNPR , and mVNPR to be the function families of the form
poly(n)
fn = ∑ gm (~e,~x) ,
~e∈{0,1}
where m ≤ poly(n) and (gm ) ∈ mVPR .
Valiant’s original completeness proof for the Hamiltonian Cycle polynomial [28] is “mostly” mono-
tone: it uses polynomial-size formulas for the coefficients of the monomials (coming from the definition
of VNP), but otherwise is entirely monotone. In other words, the proof shows that HC is mVNP-hard
under monotone projections. However, we note that it is not clear whether HC is even in mVNP! Ques-
tion 5.5 asks whether HC, or indeed any polynomial, is VNP≥0 -complete under monotone projections;
the question of whether there exist polynomials that are mVNP-complete under monotone projections
also seems potentially interesting.
Finally, we ask about stronger notions of monotone reduction, which seem to require a different kind
of proof technique. Recall that a c-reduction from f to g is a family of polynomial-size algebraic circuits
for f with oracle gates for g.
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 10
M ONOTONE P ROJECTION L OWER B OUNDS FROM E XTENDED F ORMULATION L OWER B OUNDS
Open Question 5.6. Do the analogues of Theorems 4.2–4.5 hold for monotone bounded-depth c-
reductions in place of affine p-projections? What about weakly-skew or even general monotone c-
reductions?
6 Subsequent developments
Since the appearance of the preliminary version of this paper [9], our Main Lemma 3.1 has been used
by Mahajan and Saurabh [15] to prove that several other polynomials of combinatorial and complexity-
theoretic interest are not subexponential-size projections of the permanent.
1. The n-th satisfiability polynomial over Fq is a polynomial in n + 8 n3 variables denoted X1 , . . . , Xn
and {Yc : c ∈ Cn } where Cn denote the set of clauses on 3 literals in n variables. It is defined as
! !
Satqn (X,Y ) = ∑ ∏ Xiq−1 ∏ Ycq−1 .
a∈{0,1}n i∈[n] c∈Cn :c(a)=1
2. A clow in an n-vertex graph is a closed walk of length exactly n, in which the minimum-numbered
vertex appears exactly once. The n-th clow polynomial over Fq is a polynomial in n2 + n variables
Xe for each edge e in the complete undirected graph Kn on n vertices and Yv for each v ∈ [n]. It is
defined as
! !
Clowqn (X,Y ) = ∑ ∏ Xeq−1 ∏ Yvq−1 ,
w:clow of length n e:edges in w v:distinct vertices in w
or more precisely,
! !
Clowqn (X,Y ) = ∑ ∏ X(vq−1
i−1 ,vi mod n ) ∏ Yvq−1 ,
w=[v0 ,...,vn−1 ] i∈[n] v∈{v0 ,...,vn−1 }
where the sum is over clows w and v0 denotes the minimum-numbered vertex in w.
3. The clique polynomial is a polynomial in n2 variables Xe :
Cliquen (X) = ∑ ∏ Xe .
T ⊆([n] e∈T
2)
T is a clique in Kn
Theorem (Mahajan and Saurabh [15, Theorems 2 and 6]). Over any totally ordered semi-ring, any
monotone√ affine projection from the permanent to Satqn or to the clique polynomial requires blow-up at
least 2Ω( n) . Any monotone affine projection from the permanent to Clowqn requires blow-up at least
2Ω(n) .
As in Section 4.2, we get the following corollary. Again, we note that the lower bound on the clique
polynomial over the Boolean semi-ring only works for the formal clique polynomial (in contrast to
Razborov’s result [20], which works for any monotone Boolean circuit computing the CLIQUE function).
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 11
J OSHUA A. G ROCHOW
Corollary 6.1. Over any totally ordered semi-ring, any monotone formula computing
√ Clowqn has size at
Ω(n) q Ω( n)
least 2 and any monotone circuit computing √ Clown has size at least 2 . Any monotone formula
computing Satqn or Cliquen has size at least 2Ω( n) and any monotone circuit computing these polynomials
1/4
has size at least 2Ω(n ) .
For the clow and satisfiability polynomials, we believe this result to be new. For the clique polynomials,
this provides a new proof of a weaker version of the exponential monotone circuit lower bound due to
Schnorr [24].2
Acknowledgment. We would like to thank Stasys Jukna for the question that motivated this paper [12],
and cstheory.stackexchange.com for providing a forum for the question. We also thank Stasys for
comments on a draft, pointing out the paper by Schnorr [24], and interesting discussions leading to
Questions 5.2 and 5.3. We thank Leslie Valiant for an interesting conversation that led to Question 5.5. We
thank Ketan Mulmuley and Youming Qiao for collaborating on [10], which is why the author had Newton
polytopes on the mind. We thank an anonymous reviewer for pointing out the monotone universality
of the permanent and therefore the implications for monotone formula and circuit size (Section 4.2 and
Corollary 6.1). We thank Laci Babai for detailed comments on the journal submission.
References
[1] S COTT A ARONSON: A linear-optical proof that the permanent is #P-hard. Proc. Royal Soc. London
A, 467(2136):3393–3405, 2011. [doi:10.1098/rspa.2011.0232, arXiv:1109.1674] 4
[2] S COTT A ARONSON AND A LEX A RKHIPOV: The computational complexity of linear op-
tics. Theory of Computing, 9(4):143–252, 2013. Preliminary version in STOC’11.
[doi:10.4086/toc.2013.v009a004, arXiv:1011.3245] 2
[3] A MIR B EN -D OR AND S HAI H ALEVI: Zero-one permanent is #P-complete, a simpler proof.
In Proc. 2nd Israeli Symp. on Theory and Computing Systems. IEEE Comp. Soc. Press, 1993.
[doi:10.1109/ISTCS.1993.253457] 4
[4] P ETER B ÜRGISSER: On the structure of Valiant’s complexity classes. Discr. Math. & Theoret.
Comput. Sci., 3(3):73–94, 1999. HAL. Preliminary version in STACS’98. 3, 10
[5] P ETER B ÜRGISSER: Completeness and Reduction in Algebraic Complexity Theory. Volume 7 of
Algorithms and Computation in Mathematics. Springer, 2000. [doi:10.1007/978-3-662-04179-6] 8
[6] JACK E DMONDS: Paths, trees, and flowers. Canad. J. Math., 17:449–467, 1965. [doi:10.4153/CJM-
1965-045-4] 3
2 Schnorr showed a n − 1 lower bound on the monotone circuit size of the the k-th clique polynomial Cliquek , the sum
k pn
over all cliques of size k, rather than all cliques. For k = n/2, this lower bound is asymptotically equal to 2n / πn/2. The
k-th clique polynomial Cliquekn is the degree k homogeneous component of the clique polynomial Cliquen ; by homogenization
(implicit in Strassen’s work, explicit in Valiant [30, Lemma 2]), any monotone circuit of size s for Cliquen can be converted into
n/2
a monotone circuit of size s(n/2 + 1)2 computing Cliquen . Thus Schnorr’s result implies a lower bound of Ω(2n /n5/2 ) on the
monotone circuit complexity of Cliquen .
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 12
M ONOTONE P ROJECTION L OWER B OUNDS FROM E XTENDED F ORMULATION L OWER B OUNDS
[7] S TEPHEN A. F ENNER , ROHIT G URJAR , AND T HOMAS T HIERAUF: Bipartite perfect matching is
in quasi-NC. In Proc. 48th STOC, pp. 754–763. ACM Press, 2016. [doi:10.1145/2897518.2897564,
arXiv:1601.06319] 3
[8] S AMUEL F IORINI , S ERGE M ASSAR , S EBASTIAN P OKUTTA , H ANS R AJ T IWARY, AND RONALD
DE W OLF : Exponential lower bounds for polytopes in combinatorial optimization. J. ACM,
62(2):17:1–23, 2015. Preliminary version in STOC’12. [doi:10.1145/2716307, arXiv:1111.0837] 2,
3, 8
[9] J OSHUA A. G ROCHOW: Monotone projection lower bounds from extended formulation lower
bounds, 2015. ECCC TR15-171. [arXiv:1510.08417] 11
[10] J OSHUA A. G ROCHOW, K ETAN D. M ULMULEY, AND YOUMING Q IAO: Boundaries of VP and
VNP. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp.
34:1–34:14. Springer, 2016. [doi:10.4230/LIPIcs.ICALP.2016.34, arXiv:1605.02815] 12
[11] M ARK J ERRUM AND M ARC S NIR: Some exact complexity results for straight-line computations
over semirings. J. ACM, 29(3):874–897, 1982. [doi:10.1145/322326.322341] 2, 9
[12] S TASYS J UKNA: Why is Hamilton cycle so different from permanent? StackExchange, 2014. 2, 12
[13] S TASYS J UKNA: Lower bounds for monotone counting circuits. Discr. Appl. Math., 213:139–152,
2016. Preliminary version in ECCC TR14-169. [doi:10.1016/j.dam.2016.04.024, arXiv:1502.01865]
9
[14] JACOBUS H. VAN L INT AND R ICHARD M. W ILSON: A Course in Combinatorics. Cambridge
Univ. Press, 2001. 2
[15] M EENA M AHAJAN AND N ITIN S AURABH: Some complete and intermediate polynomials in
algebraic complexity theory. In Proc. 11th Comput. Sci. Symp. in Russia (CSR’16), pp. 251–265.
Springer, 2016. Full version available at ECCC TR16-038. [doi:10.1007/978-3-319-34171-2_18,
arXiv:1603.04606] 3, 11
[16] S ILVIO M ICALI AND V IJAY V. VAZIRANI: An O(sqrt(|V|) |E|) algorithm for finding max-
imum matching in general graphs. In Proc. 12th STOC, pp. 17–27. ACM Press, 1980.
[doi:10.1109/SFCS.1980.12] 3
[17] H ENRYK M INC: Permanents. Cambridge Univ. Press, 1984. 2
[18] T HOMAS M UIR AND W ILLIAM H. M ETZLER: A Treatise on the Theory of Determinants. Dover,
1960. 2
[19] K ETAN M ULMULEY, U MESH V. VAZIRANI , AND V IJAY V. VAZIRANI: Matching is as easy
as matrix inversion. Combinatorica, 7(1):105–113, 1987. Preliminary version in STOC’87.
[doi:10.1007/BF02579206] 3
[20] A LEXANDER A. R AZBOROV: Lower bounds on monotone complexity of the logical permanent
function. Math. Notes, 37(6):485–493, 1985. [doi:10.1007/BF01157687] 2, 9, 11
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 13
J OSHUA A. G ROCHOW
[21] A LEXANDER A. R AZBOROV: Lower bounds for deterministic and nondeterministic branching
programs. In Fundamentals of Computation Theory (FCT’91), volume 529 of LNCS, pp. 47–60.
Springer, 1991. [doi:10.1007/3-540-54458-5_49] 9
[22] T HOMAS ROTHVOSS: The matching polytope has exponential extension complexity. J. ACM,
64(6):41:1–19, 2017. Preliminary version in STOC’14. [doi:10.1145/3127497, arXiv:1311.2369] 2,
3, 8
[23] N ICOLAS DE RUGY -A LTHERRE: A dichotomy theorem for homomorphism polynomials. In
Proc. 37th Internat. Symp. Math. Found. Comput. Sci. (MFCS’12), pp. 308–322. Springer, 2012.
[doi:10.1007/978-3-642-32589-2_29, arXiv:1210.7641] 3
[24] C LAUS -P ETER S CHNORR: A lower bound on the number of additions in monotone computations.
Theoret. Comput. Sci., 2(3):305–315, 1976. [doi:10.1016/0304-3975(76)90083-9] 12
[25] A LEXANDER S CHRIJVER: Combinatorial optimization. Polyhedra and efficiency. Vol. A. Volume 24
of Algorithms and Combinatorics. Springer, 2003. Chapters 1–38. 8, 10
[26] VOLKER S TRASSEN: Vermeidung von Divisionen. J. Reine Angew. Math., 1973(264):184–202,
1973. [doi:10.1515/crll.1973.264.184] 7
[27] O LA S VENSSON AND JAKUB TARNAWSKI: The matching problem in general graphs is in quasi-NC.
In Proc. 58th FOCS, pp. 696–707. IEEE Comp. Soc. Press, 2017. [doi:10.1109/FOCS.2017.70,
arXiv:1704.01929] 3
[28] L ESLIE G. VALIANT: Completeness classes in algebra. In Proc. 11th STOC, pp. 249–261. ACM
Press, 1979. [doi:10.1145/800135.804419] 2, 9, 10
[29] L ESLIE G. VALIANT: The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189–
201, 1979. [doi:10.1016/0304-3975(79)90044-6] 2, 4
[30] L ESLIE G. VALIANT: Negation can be exponentially powerful. Theoret. Comput. Sci., 12(3):303–
314, 1980. Preliminary version in STOC’79. [doi:10.1016/0304-3975(80)90060-2] 12
[31] L ESLIE G. VALIANT, S VEN S KYUM , S TUART B ERKOWITZ , AND C HARLES R ACKOFF: Fast
parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641–644, 1983.
Preliminary version in MFCS’81. [doi:10.1137/0212043] 9
[32] V IJAY V. VAZIRANI: A simplification of the MV matching algorithm and its proof, 2013.
[arXiv:1210.4594] 3
[33] T ZU -C HIEH W EI AND S IMONE S EVERINI: Matrix permanent and quantum entanglement of
permutation invariant states. J. Math. Phys., 51(9), 2010. [doi:10.1063/1.3464263, arXiv:0905.0012]
2
[34] M IHALIS YANNAKAKIS: Expressing combinatorial optimization problems by linear programs. J.
Comput. System Sci., 43(3):441–466, 1991. Preliminary version in STOC’88. [doi:10.1016/0022-
0000(91)90024-Y] 2
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 14
M ONOTONE P ROJECTION L OWER B OUNDS FROM E XTENDED F ORMULATION L OWER B OUNDS
AUTHOR
Joshua A. Grochow
Assistant professor
Departments of Computer Science and Mathematics
University of Colorado, Boulder, CO, USA
jgrochow colorado edu
http://www.cs.colorado.edu/~jgrochow
ABOUT THE AUTHOR
J OSHUA A. G ROCHOW is an Assistant Professor in the Departments of Computer Science
and Mathematics and the University of Colorado, Boulder. Prior to that he was an
Omidyar Postdoctoral Fellow at the Santa Fe Institute, and a postdoc in the theory group at
University of Toronto. He graduated from The University of Chicago in 2012; his advisors
were Lance Fortnow and Ketan Mulmuley. In addition to his interests in algebraic and
geometric complexity theory, he is also interested in broader issues in complex networks
and complex adaptive systems, sometimes referred to in our community as “the other”
complexity theory.
T HEORY OF C OMPUTING, Volume 13 (18), 2017, pp. 1–15 15