Explicit SoS lower bounds from high-dimensional expanders

The sum-of-squares hierarchy²²2For more on Sum-of-Squares, see the recent monograph by Fleming, Kothari and Pitassi [FKP19]. provides a hierarchy of semidefinite programming (SDP) relaxations, for various combinatorial optimization problems. Figure 1 describes the relaxation given by $t$ levels of the hierarchy for an instance $\mathcal{I}$ of 3XOR in $n$ variables, with $m$ constraints of the form $x_{i_{1}}+x_{i_{2}}+x_{i_{3}}=\beta_{i_{1}i_{2}i_{3}}$ over $\mathbb{F}_{2}$. We also use $\mathcal{I}$ to denote the set of all tuples $\{i_{1},i_{2},i_{3}\}$ present as constraints. A solution to the relaxation is specified by a collection of unit vectors $\left\{\mathbf{u}_{S}\right\}_{S\subseteq[n],\left\lvert S\right\rvert\leq t}$, satisfying the constraints in the program. The objective equals the fraction of constraints “satisfied” by the SDP solution.

To prove a lower bound on the value of the SDP relaxation, we will use the following result, which shows the existence of vectors $\mathbf{u}_{S}$ yielding an objective value of 1, when the given system of XOR constraints does not have any “low-width” refutations. Formally, we consider a system called $\oplus$-resolution, where the only rule allows us to combine two equations $\ell_{1}=b_{1}$ and $\ell_{2}=b_{2}$ to derive the equation $\ell_{1}+\ell_{2}=b_{1}+b_{2}$. A refutation is a derivation of $0=1$. The width of a refutation is the maximum number of variables in any equation used in the refutation. We include a proof of the following lemma in Appendix A.

A simplicial complex $X$ is a non-empty collection of sets (known as faces) which is closed downwards. The $i$-dimensional faces $X(i)$ are all sets of size $i+1$. The dimension of the complex is the maximal dimension of a face. Faces of that dimension are known as facets. Faces of dimensions $0,1,2,3$ are called vertices, edges, triangles, and tetrahedra, respectively.

Graphs are $1$-dimensional simplicial complexes. The skeleton of a simplicial complex is the graph obtained by retaining only faces of dimension at most $1$.

The infinite $k$-regular tree is the unique connected $k$-regular graph without cycles. Affine buildings are higher-dimensional analogs of the infinite $k$-regular tree. For $d=1$, the one-dimensional affine building $\mathcal{B}^{(1)}$ is the $k$-regular tree. For higher dimensions they are regular in the sense that all vertex links are bounded and identical in structure, they are connected and contractible,³³3A complex is contractible, roughly speaking, if it can be continuously deformed to a point (technically, it is homotopy-equivalent to a point). Since (co)homologies are preserved by such deformations, all (co)homologies of a contractible complex vanish. and so have vanishing cohomologies, that is, the cohomology spaces $H^{1},\ldots,H^{d-1}$ are trivial, where $d$ is the dimension.

We won’t describe $\mathcal{B}^{(d+1)}$ any further; the interested reader can check [Ji12, AB08]. A crucial property of $\mathcal{B}^{(d+1)}$ which we will need in the sequel is its being a CAT(0) space,⁴⁴4A space is CAT(0) if for every triangle $x,y,z$, the distance between $x$ and the midpoint of $y,z$ is at most the corresponding distance in a congruent triangle in Euclidean space. which is a geometric definition capturing non-positive curvature; see [BH99] for more information. The property of being CAT(0) has the following implication, due to Gromov [Gro83, Gut06, Wen08]:

Gromov’s filling inequality is an isoperimetric inequality. It generalizes the classic isoperimetric inequality in the plane, which states that any simple closed curve of length $L$ encloses a region whose area is at most $L^{2}/4\pi$.

The isoperimetric inequality in the plane can be stated in an equivalent way: the boundary of any bounded region of area $A$ is a curve whose length is at least $\sqrt{4\pi A}$. This inequality fails for unbounded regions, which could have infinite area but finite boundary (for example, consider the complement of a circle). In the same way, Gromov’s inequality doesn’t imply that each $g\in C_{2}$ satisfies $|\partial g|=\Omega(\sqrt{|g|})$. Rather, we have to replace $|g|$ with $\min_{h\in Z_{2}}|g+h|$.

Gromov’s filling inequality also applies to $i$-chains, with an exponent of $i+1$, but we will only need the case $i=1$.

In the sequel, we will apply Gromov’s filling inequality not to the building itself, but rather to balls in the building. The CAT(0) property almost immediately implies that a ball in a CAT(0) space is itself CAT(0) [BH99, Exercise II.1.6]. Furthermore, it is well-known that CAT(0) spaces are contractible, and so have vanishing homologies.

Whereas the affine building is an infinite simplicial complex, Lubotzky, Samuels and Vishne constructed a growing family of finite complexes that are obtained from quotients of the affine building. These quotients have a growing number of vertices, and locally, in a ball around each vertex, the complex is isomorphic to the affine building. Moreover, they gave a very explicit algorithm for constructing these complexes by first constructing a Cayley graph with an explicit set of generators, and then the higher dimensional faces are simply the cliques in the Cayley graph.

The precise definition of “Ramanujan complex” is not important for this context. For us, there are three important aspects of this theorem: efficient construction, local structure, and global structure.

• -

  Efficient construction: Firstly, the fact that the complex is constructible in polynomial time.

• -

  Local structure: Next, we highlight the fact that locally the complex looks like the building. The theorem states that the complex $X$ is covered by $\mathcal{B}^{(d)}$. A covering map maps a simplicial complex $Y$ surjectively to a simplicial complex $X$ by mapping the vertices $\psi:Y(0)\to X(0)$ such that for every $k\leq d$ the image of every $k$-face ${\{{v_{0},\ldots,v_{k}}\}}\in Y(k)$ is a $k$-face ${\{{\psi(v_{0}),\ldots,\psi(v_{k})}\}}\in X(k)$.

  The fact that $X$ is covered by $\mathcal{B}^{(d)}$ means that the neighborhood of a vertex in $X$ and in $\mathcal{B}^{(d)}$ look exactly the same. It turns out that for the LSV complexes this continues to be true also for balls of larger radius around any vertex. This is a higher-dimensional analog of the graph property of containing no short cycles (locally looking like a tree). Define the injectivity radius of $X$ to be the largest $r$ such that the covering map $\mathcal{B}^{(d)}\stackrel{{\scriptstyle\psi}}{{\rightarrow}}X$ is injective from balls of radius $\leq r$ in $\mathcal{B}^{(d)}$ and the ball of radius $\leq r$ in $X$. We do not mention the center of the ball they are all isomorphic.

  Theorem 2.8 (Lubotzky and Meshulam [LM07], see also⁵⁵5The theorem was proven by [LM07]. They stated their theorem using a slightly different definition for injectivity radius but one can prove that the two definitions coincide in this case. This was reproven in [EGL15] who use the definition of injectivity radius that is convenient for us. [EGL15, Corollary 5.2]).

  Let $X$ be the LSV complex above. Then the injectivity radius $r(X)$ of $X$ satisfies

  $$r(X)\geq\frac{\log_{q}|X|}{2(d-1)(d^{2}-1)}-\frac{1}{2}$$

  where $|X|$ is the number of vertices in $X$.

• -

  Global structure: Finally, we look at the second cohomology group of the LSV complexes. Kaufman, Kazhdan and Lubotzky [KKL16] showed that the groups defining the LSV quotient complexes can be chosen so that the second homology is non-empty.

  Proposition 2.9 (Kaufman, Kazhdan, Lubotzky [KKL16, Proposition 3.6]).

  There is an infinite and explicit sequence of LSV complexes with a non-vanishing second cohomology.

  We remark that Kaufman, Kazhdan and Lubotzky [KKL16] proved that these complexes exist. To show that they are also efficiently constructible, we look into their proof to recall the construction: start with any LSV complex $X$ viewed as a Cayley graph of a group $G$. Find some element of order $2$ in $G$ (such an element always exists), and then quotient $X$ by this element, thus obtaining a complex $Y$ that is itself is a Ramanujan complex because it is a quotient of one. $Y$ is clearly efficiently constructible from $X$, and has half as any vertices. This construction shows (see [KKL16, Proposition 3.5]) that $H^{1}(Y)\neq 0$. Furthermore, the proof of [KKL16, Proposition 3.6] shows that because $G$ has property $T$ one can deduce also that $H^{2}(Y)\neq 0$.

  Evra and Kaufman proved [EK16, Theorem 1.9] that quotients of $\mathcal{B}^{(d)}$ (and even a more general class of complexes) are so-called “cosystolic expanders” which in particular implies the following.

  Theorem 2.10 (Evra and Kaufman [EK16, Part of Theorem 1.9]).

  Let ${\{{X_{n}}\}}$ be a family of LSV complexes. There exists some constant $\mu>0$ that depends only on $q$ and $d$ but not on the size $n$ of the complex, such that every $f\in Z^{2}(X)\setminus B^{2}(X)$ must have weight at least $\mu\cdot|X(2)|$.

The infinite sequence of complexes we will be working with are the LSV complexes described in Section 2.4 above. The properties we care about are (1) that they are efficiently constructible, (2) that small balls in these complexes are isomorphic to the affine building, which satisfies certain isoperimetric inequalities because it is a CAT(0) space, and (3) that each complex has a two-dimensional cocycle with linear distance from the set of coboundaries. The second and third properties provide the tension between the local and the global structure of these complexes that we now harness for our hardness.

To construct an SDP solution, we will need to show that our instance based on the LSV complex “locally looks satisfiable”. To this end, we will first develop some local properties of the LSV complex.

Note that each $h\in C^{2}$ corresponds to a set of triangles. For the following statements, we consider two triangles to be connected if they share an edge. This can be used to define connected components. Note that if $h$ can be split into connected components $h_{1},\ldots,h_{s}$, then the components correspond to disjoint sets of triangles. Moreover, no triangle in $h_{i}$ shares an edge with a triangle in $h_{j}$ when $i\neq j$, which also implies that the boundaries $\partial h_{i}$ and $\partial h_{j}$ correspond to disjoint sets of edges.

We prove the following claims by mapping small connected sets in $X(2)$ to corresponding sets in the infinite building $\mathcal{B}$. The first proposition shows that there can be no small non-trivial cancellations (i.e., not coming from tetrahedra).

This proposition states that locally (i.e., within the injective radius $r$), $Z_{2}$ looks like $B_{2}$. We thus have a complex whose cohomology group is non-trivial, yet locally, the homology group “looks” trivial. Note that this is a twist on what we had claimed in the introduction, a complex whose cohomology group is non-trivial, yet locally, the cohomology group “looks” trivial. However, these are identical statements owing to 2.4.

The next proposition shows that Gromov’s filling inequality in the infinite building $\mathcal{B}$ can be used to yield a similar consequence for small sets in the finite complex $X$.

Let $X$ be a $d$-dimensional LSV complex, with $\left\lvert X(1)\right\rvert=n$ and non-trivial second cohomology group, as per Proposition 2.9. Below, we construct an instance of 3XOR in $n$ variables using this complex, and prove a lower bound on the integrality gap of the relaxation obtained by $\Omega(\sqrt{\log n})$ levels of the SoS hierarchy.