We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image
of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^c}$, for some constant $c > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-$O(1)$ sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.
We prove super-polynomial lower bounds on the size of linear programming relaxations for approximati
Let $G$ be a finite group with symmetric generating set $S$, and let $c = max_{R > 0} |B(2R)|/|B(R)|$ be the doubling constant of the corresponding Cayley graph, where $B(R)$ denotes an $R$-ball in the word-metric with respect to $S$. We show that th
e multiplicity of the $k$th eigenvalue of the Laplacian on the Cayley graph of $G$ is bounded by a function of only $c$ and $k$. More specifically, the multiplicity is at most $exp((log c)(log c + log k))$. Similarly, if $X$ is a compact, $n$-dimensional Riemannian manifold with non-negative Ricci curvature, then the multiplicity of the $k$th eigenvalue of the Laplace-Beltrami operator on $X$ is at most $exp(n^2 + n log k)$. The first result (for $k=2$) yields the following group-theoretic application. There exists a normal subgroup $N$ of $G$, with $[G : N] leq alpha(c)$, and such that $N$ admits a homomorphism onto the cyclic group $Z_M$, where $M geq |G|^{delta(c)}$ and $alpha(c), delta(c) > 0$ are explicit functions depending only on $c$. This is the finitary analog of a theorem of Gromov which states that every infinite group of polynomial growth has a subgroup of finite index which admits a homomorphism onto the integers. This addresses a question of Trevisan, and is proved by scaling down Kleiners proof of Gromovs theorem. In particular, we replace the space of harmonic functions of fixed polynomial growth by the second eigenspace of the Laplacian on the Cayley graph of $G$.
