New Spectral Algorithms for Refuting Smoothed k-SAT

Short Cycles in Graphs.

Feige’s conjecture¹⁰ is a generalization of a basic result about short cycles in graphs. Recall that a graph (aka network), is simply a collection of pairs, called edges (modeling pairwise associations), on $n$ nodes. A cycle in such a network is a sequence of nodes $v_1\to v_2\to \dots \to v_{\ell }\to v_1$ that starts and ends at the same node such that every consecutive pair has an edge between them. In his famous 1978 book,⁵ mathematician Béla Bollobás conjectured that every graph with $n$ nodes where every node, on average, has $d>2$ edges (this quantity is called the average degree), must have a cycle of length at most $\approx {log}_{d-1}\left(n\right)$. When $d=2$, the network can be a single giant cycle on all $n$ vertices that clearly has no cycle of length $\le n-1$. For any $d>2$, however, the conjecture implies that we cannot even avoid a cycle of length $O(logn)$—an exponentially smaller bound than $n$—and thus signals a phase transition in the extremal length of the smallest cycle as the average degree $d$ crosses 2.

Bollobas’s conjecture is an example of a result in extremal combinatorics. Such results uncover a truth that holds for all (thus extremal) mathematical objects. Here, it says that no matter how we might build a graph on $n$ nodes, so long as it has average degree $d>2$, we cannot avoid introducing a short cycle. In their elegant 2002 paper,³ mathematicians Alon, Hoory and Linial confirmed this conjecture.

Short Cycles in Hypergraphs.

Feige’s conjecture asks a similar question about short cycles in hypergraphs. A $k$-uniform hypergraph is a collection of subsets of size $k$ on $n$ nodes, called hyperedges, that model associations between a larger number of nodes (instead of 2 in graphs). A 2-uniform hypergraph is simply a graph. In order to pose Feige’s question, we will identify a key property of cycles in graphs and use it to motivate a generalized notion of cycles in hypergraphs. Observe that every vertex appears in either two or zero edges in any cycle in a graph. In particular, a cycle is an even subgraph—a subset of edges on which, every vertex appears an even integer number of times. Even subgraphs naturally generalize to hypergraphs. We will define a hypergraph cycle or even covers to be a collection $C_1,C_2,\dots ,C_{\ell }$ of hyperedges such that every node of the hypergraph is included in an even number of $C_i$’s (that is, an even subhypergraph). (See Figure 1a and 1b.)

Feige’s Conjecture and the Resolution.

As in the case of graphs, we are interested in the extremal trade-off between average degree (that is, average number of hyperedges containing a node) and the length of the smallest hypergraph cycle in a $k$-uniform hypergraph. Given the connection to linear dependencies above and the basic fact that every collection of $m=n+1$ equations in $n$ variables are linearly dependent, whenever the average degree $d=mk/n>k$, then the hypergraph must have a (rather long) cycle of length $n+1$. Making an analogy to graphs, one might expect that if $d\gg k$, the hypergraph must have a $O(logn)$-length cycle, but this turns out to be false! Mathematicians Assaf Naor and Jacques Verstraete in 2006 showed²¹ that one needs (and this is enough!) the average degree $d\gtrsim n^{k/2-1}$ in order for every hypergraph to have a $O(logn)$-length cycle. For $k=2$, this matches a coarse version of the bound for graphs but for $k\ge 3$ suggests a new regime between $d\approx 1$ and $d\approx \sqrt{n}$ that has no analog for graphs. What happens when, for example, $d\approx n^{0.25}$? Feige conjectured a precise behavior for this regime:

Feige’s conjecture (up to some $logn$ factors in $d$) was motivated by the hypothesis (and is, in fact, equivalent to it) that there is no better construction of hypergraphs avoiding short cycles than simply choosing a random hypergraph. It is thus analogous to the famous 1947 theorem of Shannon (the birthplace of modern coding theory!) that random error correcting codes are “best” in a precise sense.

Despite being a foundational statement about hypergraphs, the conjecture remained largely open with only some partial progress for a special case by Alon and Feige in 2009. Now, by invoking the new algorithms for solving smoothed $k$-SAT we can essentially completely resolve it — up to one additional $logn$ factor in the degree bound! This was established first by the authors with additional $logn$ factors which were later¹⁷ trimmed down to a single $logn$ factor.

As we will explain later in this article, the proof of this theorem makes a new connection between the success of our spectral approach for smoothed $k$-SAT and existence of short cycles in hypergraphs. It forms the first (of a growing list of) application spectral refutations via Kikuchi matrices in combinatorics.

2.1 From Quadratic Polynomials to Matrices

Let us show how spectral methods show up by starting with the simplest setting of $k=2$. Then, each $C\in H$ is a set of size 2, or simply a pair $\{i,j\}\subseteq \left[n\right]$, and $\Psi \left(x\right)$ from (2) is a degree 2 polynomial in $x$. The idea is to view such a degree 2 polynomial as a quadratic form.

For an $n\times n$ matrix $A$, its quadratic form on a vector $v$ equals $v^{\top }Av=〈v,Av〉={\sum }_{i,j\le n}{v}_i{v}_{j}A(i,j)$. This expression is a homogeneous quadratic polynomial in $v$. Indeed, every quadratic polynomial is a quadratic form of an associated matrix and vice-versa. For our $\Psi$, let the $n\times n$ matrix $A$ be defined by:

Then, for any $x\in {\{-1,1\}}^n$, $x^{\top }Ax={\sum }_{i,j}{x}_i{x}_j{b}_{i,j}=2\Psi \left(x\right)$.

A basic result in linear algebra allows upper-bounding any quadratic form of $A$ as:

where ${∥v∥}_2=\sqrt{{\sum }_i{v}_i^2}$ is the length of the vector $v$ and ${∥A∥}_2$ is the “spectral norm” or the largest singular value of $A$. Since $x$ has $\{\pm 1\}$-coordinates and thus length $\sqrt{n}$, we obtain that $\Psi \left(x\right)\le n{∥A∥}_2$.

This bound on $\Psi \left(x\right)$ is easily verifiable. Given $\Psi$ (obtained easily from the $k$-SAT formula $\varphi$), we form the matrix $A$ and use a linear time algorithm (called power iteration) to obtain good estimates on the spectral norm ${∥A∥}_2$.

To certify $\Psi \left(x\right)\le ∊m$, we need to check that ${∥A∥}_2\le ∊m/n$. $A$ is an example of a random matrix since its entries $b_{\{i,j\}}$ are uniformly and independently distributed in $\{\pm 1\}$. There is a well-developed theory for understanding the typical value of ${∥A∥}_2$ for such random matrices that allows us to conclude that ${∥A∥}_2\lesssim \sqrt{{\Delta }_{max}logn}$ where ${\Delta }_{max}$ is the maximum number of non-zero entries in any row of the matrix $A$. If the pairs $C=\{i,j\}$ are “equidistributed” that is, any variable $i$ participates in roughly the same number of pairs, then we would expect ${\Delta }_{max}\approx {\Delta }_{avg}\approx m/n$ where ${\Delta }_{avg}$ is the average number of non-zero entries in a row of $A$. Thus, ${∥A∥}_2\lesssim \sqrt{mlogn/n}$ which is $\le ∊m/n$ if $m\gtrsim nlogn$.

What if the set of pairs $H$ is not regular and some $i$ is “over-represented” in the set of pairs $C$? While we omit formal details, it turns out that one can use an elegant reweighting trick (discovered in the work of¹⁷) on the matrix $A$ that effectively allows us to assume regularity if ${\Delta }_{avg}\gg 1$.

2.2 Generalizing to Quartic Polynomials

The case of odd $k$ turns out to be technically challenging so let us skip $k=3$ and generalize the above approach when $\Psi \left(x\right)$ is of degree $k=4$ (that is, the case of 4-SAT). So, $\Psi \left(x\right)$ is not quadratic in $x$. We will now view it as a quadratic form in $\left({}_2^n\right)$ variables each corresponding to quadratic monomials $x_i{x}_j$ in the original assignment $x$. Let us write $x^{\circ 2}$ for the vector in $R^{\left({}_2^n\right)}$ indexed by pairs $\{i,j\}$ with entry at $\{i_1,i_2\}$ given by $x_{i_1}{x}_{i_2}$. Define the $\left({}_2^n\right)\times \left({}_2^n\right)$ matrix $A$:

Then, as before, we can observe that:

The factor 6 comes from the fact that there $\left({}_2^4\right)=6$ different ways that a set $C$ of size 4 can be broken into pairs of pairs each of which arises as a term in the quadratic form above.

We can now write

And a similar appeal to results in random matrix theory tells us that with high probability ${∥A∥}_2\lesssim \sqrt{{\Delta }_{max}log\left({}_2^n\right)}\lesssim \sqrt{{\Delta }_{max}logn}$ where ${\Delta }_{max}$ is the maximum number of non-zero entries in any row of $A$. Equivalently, ${\Delta }_{max}$ is the maximum number of 4-clauses that a pair $\{i,j\}$ participates in. When all pairs behave roughly similarly, we will have ${\Delta }_{max}\approx {\Delta }_{avg}\lesssim \frac{m}{\left({}_2^n\right)}$, in which case

with high probability if $m\gtrsim n^{2}logn$.

Early proofs of such facts used different tools from random matrix theory and worked for random 4-SAT by utilizing that $H$ is a random collection of 4-sets in that case. Our approach here explicitly reveals that only an equi-distribution (that is, ${\Delta }_{max}\approx {\Delta }_{avg}$) property of $H$ is required for the success of this approach. This allows us, via a similar reweighting trick (that succeeds if ${\Delta }_{avg}\gg 1$) discussed above, to obtain a result that works for arbitrary (worst-case) hypergraphs.

Let’s finish this part by noting our quantitative bounds. For $k=2$, our refutation succeeded when $m\gtrsim nlogn$. For $k=4$, we instead needed $m\gtrsim n^{2}logn$. Indeed, for arbitrary even $k$, a similar argument yields a bound of $m\gtrsim n^{k/2}logn$—a significant improvement over the $\Omega \left(n^k\right)$ clauses required for refuting an unsatisfiable $k$-SAT formula in the worst-case, showing us the power of the spectral approach.

2.3 Beyond Basic Spectral Refutations

A smoothed $k$-SAT formula is unsatisfiable with high probability whenever it has $m\gtrsim n$ clauses. But our spectral refutations above require $m\gtrsim n^{2}logn$—a bound higher by a factor $\approx n$ (and $n^{k/2-1}$ for arbitrary even $k$). This is because our approach fails whenever the average number of entries in a row of $A$, that is, ${\Delta }_{avg}=m/\left({}_2^n\right)$, is $\ll 1$. The question of whether there are non-trivial refutations for $k$-SAT formulas when $m\ll n^{k/2}$ (now called the spectral threshold) remained open for more than a decade and half. In the same time, researchers found evidence, in the form of restricted lower bounds,²⁰ that there may be no polynomial time refutation algorithm for $m\ll n^{k/2}$. This, nevertheless, left open the possibility of significantly beating brute-force search below this threshold. This possibility was realized for random$k$-SAT in 2017. We will now discuss a significantly simpler (described essentially in full below!) spectral approach that succeeds even for smoothed $k$-SAT.

We will continue to work with $k=4$. As before, we will write $\Psi \left(x\right)$ as a quadratic form but instead of the natural matrices we discussed above, we will use Kikuchi matrices that we next introduce. First, though, a piece of notation: for sets $S,T\subseteq \left[n\right]$, we let $S\oplus T=(S\cup T)(S\cap T)$ denote the symmetric difference of $S$ and $T$.

Observe that for $r=2$, the above Kikuchi matrices specialize to the $\left({}_2^n\right)\times \left({}_2^n\right)$ matrix we saw in the previous subsection. Let’s see why $\Psi \left(x\right)$ is a quadratic form of $A$.

For any assignment $x\in {\{\pm 1\}}^n$, denote by $x^{\circ r}$ the $\left({}_r^n\right)$-dimensional vector with coordinates indexed by sets $S\subseteq \left[n\right]$ of size $r$ and $S$-th entry given by $x_S={\prod }_{i\in S}{x}_i$. Then, for $D=\left({}_2^4\right)\left({}_r^n{}_{-}^{-}{}_2^4\right)$ we have:

Here, we used that since $S\oplus T=C$, for any $x\in {\{\pm 1\}}^n$, $x_S·x_T=x_{S\cup TS\cap T}{x}_{S\cap T}^2=x_C$ as $x_i^2=1$ for every $i$. The last equality holds true because the number of pairs $(S,T)$ such that $S,T$ are $r$-size sets and $S\oplus T=C$ is exactly $D$ for any set $C$ of size 4. Observe how our notational trick of switching to $\{\pm 1\}$-valued truth assignments paid off here.

Given this simple observation, we can now again construct the spectral upper bound $\Psi \left(x\right)\le {∥x^{\circ r}∥}_2^2{∥A∥}_2=\left({}_r^n\right){∥A∥}_2$. Furthermore, it turns out that powerful tools of random matrix theory still allow us to conclude as before that

Trace Moments and Spectral Norms.

To relate ${∥A_{\text{sat}}∥}_2$ and ${∥A_{\text{random}}∥}_2$ and to bring in the cycles in $H$, we will utilize a classical connection between ${∥B∥}_2$ and the so-called trace moments of a matrix $B$ that, in turn, are related to a certain combinatorial count of walks on $B$.

For any $N\times N$ symmetric matrix $B$, let ${∥B∥}_2={\sigma }_1\ge {\sigma }_2\ge \cdots {\sigma }_N\ge 0$ be its $N$ singular values placed in descending order. The trace $\mathrm{tr}\left(B\right)$ is simply the sum of the diagonal elements of $B$. For any even $2t\in N$, a classical observation in linear algebra says that the trace of the $2t$-th power of $B$ equals the sum of $2t$-th powers of its singular values:

This is helpful because we can now write:

That is, the $2t$-th power of ${∥B∥}_2$ equals $\mathrm{tr}\left(B^{2t}\right)$ up to a factor $N$. By taking $2t=logN$ and taking $1/2t$-th powers on both sides and recalling that $N^{1/logN}\to 1$ as $N\to \infty$ gives:

Thus, for $2t\approx logN$, $\mathrm{tr}{\left(B^{2t}\right)}^{1/2t}$ is a faithful approximation to ${∥B∥}_2$.

Relating ${∥A_{\text{sat}}∥}_2$ and ${∥A_{\text{random}}∥}_2$ via Trace Moments.

Using the above connection, we will now focus on arguing that $\mathrm{tr}\left(A_{\text{sat}}^{2t}\right)=\mathrm{tr}\left(A_{\text{random}}^{2t}\right)$ for $2t=logN=log\left({}_r^n\right)\approx rlogn$. This would give us ${∥A_{\text{sat}}∥}_2\approx {∥A_{\text{random}}∥}_2$.

We now recall another classical observation from basic linear algebra that relates trace moments of a matrix $B$ to a certain combinatorial count of “walks” on $B$. For $A$ (standing for $A_{\text{sat}}$ or $A_b$), we thus have:

That is, $\mathrm{tr}\left(A^{2t}\right)$ is the sum over all sequences of $2t$ row indices (that is, subsets of $\left[n\right]$ of size $r$) of product of the entries of $A$ on consecutive elements of the sequence.

Every entry of $A$ is either 0 or $\pm 1$ and for each non-zero entry $A(S_i,S_{i+1})$, $S_i\oplus S_{i+1}=C$ for some $C\in H$. Thus, any $2t$-sequence $(S_1,S_2,\dots ,S_{2t})$ that contributes a non-zero (and thus exactly ${\prod }_{i=1}^{2t}{b}_{C_i}$ in $\mathrm{tr}\left(A_b^{2t}\right)$) value to the sum above must correspond to a $2t$-tuple $(C_1,C_2,\dots ,C_{2t})$ of hyperedges from $H$, one for each entry $A(S_i,S_{i+1})$.

More is true about such a $(C_1,C_2,\dots ,C_{2t})$, as we next demonstrate in the crucial observation below. Let $1_{C_i}\in {\{0,1\}}^n$ be the 0-1 indicator of the set $C_i\subseteq \left[n\right]$. That is, $1_{C_i}\left(j\right)=1$ if and only if $j\in C_i$.

This crucial observation is actually quite simple to prove. We know that $1_{S_i}+1_{S_{i+1}}=1_{C_i}$ mod 2 for every $i$—since $S_i\oplus S_{i+1}=C_i$. If we add up all the left hand sides we get a sum over $1_{S_i}$’s where every $1_{S_i}$ appears exactly twice (since $S_i$ occurs in exactly two entries $A(S_{i-1},S_i)$ and $A(S_i,S_{i+1})$). Thus the left hand side (and thus also the right hand side) must add up to the 0 vector modulo 2.

Next, notice that the $j$-th entry ${\sum }_{i=1}^{2t}{1}_{C_i}\left(j\right)=0$ mod 2 if and only if $j$ occurs in an even number of $C_i$’s. Thus, the above observation says that the (multi)-set $\{C_1,C_2,\dots ,C_{2t}\}$ is a cycle or an even cover. This appears exciting since we have a direct relationship between $\mathrm{tr}\left(A_{\text{sat}}^{2t}\right)$ and cycles in $H$!

There is a crucial snag though—the same $C$ could recur multiple times in $(C_1,C_2,\dots ,C_{2t})$. Indeed, if $C_i=C$ for every $i$ or more generally, every $C_i$ appeared in pairs, then, of course every element $j\in \left[n\right]$ will occur in an even number of $C_i$’s, for the trivial reason that the $C_i$’s themselves occur in pairs. Let’s call such $2t$-tuples trivial cycles—that is, the $C_i$’s occur in pairs and thus do not relate to cycles in $H$.

Now for our endgame. For every trivial cycle, since $C_i$’s appear in pairs, the quantity ${\prod }_{i=1}^{2t}{b}_{C_i}$ has even number of copies of $b_{C_i}$ for every $b_{C_i}$. Since $b_{C_i}^2=1$, this quantity must equal 1 regardless of the $C_i$’s! Thus, no matter what the $b_{C_i}$’s, all non-zero terms contribute exactly 1. In particular, $\mathrm{tr}\left(A_{\text{sat}}^{2t}\right)$ (where all $b_{C_i}$’s equal 1) must equal $\mathrm{tr}\left(A_b^{2t}\right)$ regardless of $b_{C_i}$s.

This finishes our argument, but it’s perhaps helpful to summarize it: we related ${∥A∥}_2$ (for both $A=A_{\text{sat}}$ and $A=A_b$) to $\mathrm{tr}\left(A^{2t}\right)$. We then related $\mathrm{tr}\left(A^{2t}\right)$ to a sum over $2t$-tuples $(S_1,S_2,\dots ,S_{2t})$. The non-zero terms in this sum correspond to ${\prod }_{i=1}^{2t}{b}_{C_i}$ for $(C_1,C_2,\dots ,C_{2t})$ for $C_i\in H$ such that $\sum 1_{C_i}=0$ mod 2—this step crucially uses the structure of the Kikuchi matrices. If $H$ has no $2t=log\left({}_r^n\right)$ length cycles, then in every nonzero term in the sum the $C_i$’s must occur in pairs, in which case we observe that ${\prod }_{i=1}^{2t}{b}_{C_i}=1$ and is thus independent of what the $b_{C_i}$’s themselves are.