A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs

Tommaso d'Orsi, Luca Trevisan

Here is a blog-style summary of the paper.

TL;DR

The authors develop a generalized Ihara-Bass formula and non-backtracking matrix framework that applies to arbitrary real symmetric matrices (rather than just $0/1$ graph adjacency matrices). Using this spectral machinery, they eliminate a long-standing $\text{polylog}(n)$ barrier for polynomial-time strong refutations of random $k$-CSPs when $k$ is odd, matching the optimal constraint density $m \approx n^{k/2}/\epsilon^2$ previously known only for even $k$.

What Problem Does This Paper Address?

In a random constraint satisfaction problem (CSP)—such as 3-SAT or 3-XOR—formulas with sufficiently many clauses almost surely cannot have more than a fraction $p + O(\epsilon)$ of constraints satisfied simultaneously. Proving that an individual given random formula has this property is known as strong refutation.

While strong refutation is well understood when the constraint arity $k$ is even, odd $k$ poses a notorious technical barrier:

  • For even $k$ (e.g., $k=4$), the instance tensor flattens into an $n^{k/2} \times n^{k/2}$ symmetric matrix whose entries are independent random variables. Standard union-bound arguments (such as Grothendieck's inequality or Feige–Ofek style techniques) certify quasirandomness with $O(n^{k/2}/\epsilon^2)$ constraints.
  • For odd $k$ (e.g., $k=3$), Cauchy-Schwarz flattening introduces dependencies between entries, and the resulting matrix is very sparse (constant average degree per row). Standard spectral methods using the trace method require $\Omega(n^{k/2} \text{polylog } n)$ clauses because high-degree vertices distort the adjacency spectrum by $\sqrt{\log n}$, while union bounds fail because the matrix lacks enough entropy.

The paper asks: Can we efficiently strongly refute odd $k$-CSPs at the sharp constraint threshold $n^{k/2}/\epsilon^2$, removing the polylogarithmic factor?

Methods

The authors bypass the high-degree vertex barrier using non-backtracking matrices:

  1. Generalized Ihara-Bass Formula: The classical Ihara-Bass formula relates the determinant of a graph's adjacency matrix to its non-backtracking walk matrix $B$, which is immune to local hub artifacts. The authors invent an explicit definition of non-backtracking matrices $B(A)$, alongside auxiliary matrices $L(A)$, $J(A)$, and $D(A)$, that holds for arbitrary real symmetric matrices $A$. They prove the identity: $$\det(\text{Id}_{2m} - u(B + L - J)) = (1 - u^2)^{m - n} \det(\text{Id}_n - u A + u^2 D - u^2 \text{Id}_n)$$
  2. Eigenvalue and Norm Bounds: Leveraging this identity (inspired by Fan and Montanari), they show that the smallest eigenvalue $\lambda_{\min}$ of $B + L - J$ directly yields a positive semidefinite (PSD) certificate on $A$, which translates into tight bounds on the cut/$\infty \to 1$ norm $\|A\|_{\infty \to 1}$.
  3. Trace Method on Weighted Hyper-Walks: To control the spectrum of $B$, the authors evaluate high-power traces via combinatorics on closed "hypergraph walks," using compact encoding techniques and showing that sparse hypergraphs are sufficiently "tangle-free" with high probability.
  4. Local-to-Global Rounding (for Algorithms): Combining this norm certificate with the local-to-global correlation framework of Barak et al., they design an approximation algorithm that resists adversarial literal sign perturbations.

Datasets

Not discussed in the paper. This is a purely theoretical paper; evaluation is mathematical rather than empirical, analyzing standard distributional random CSP models ($\mathcal{F}_{k\text{-XOR}}(n, p)$ and $\mathcal{F}_{\text{CSP}(P)}(n, p)$) and semi-random CSP variants.

Key Insights and Ideas

  • Why Non-Backtracking Works: In sparse random matrices with heavy-tailed degrees, ordinary adjacency matrices develop localized, outlier eigenvectors around high-degree nodes that blow up the spectral norm by $O(\sqrt{\log n})$. Non-backtracking matrices eliminate immediate back-and-forth walks ($u \to v \to u$), effectively erasing these hub traps and restoring optimal spectral bounds without needing vertex trimming.
  • Handling Non-Boolean / Real Entries: Classical Ihara-Bass identities only hold for unweighted $0/1$ matrices. The authors show that assigning directional sign and square-root weight dependencies to directed edges ($e = uv$ and $f = vw$ depending on whether $u < v$, $v < w$, etc.) yields an exact polynomial identity for any symmetric matrix.
  • SDP Duals without Solving SDPs: The resulting spectral certificates imply valid dual certificates for Sum-of-Squares/SDP relaxations, but require only an eigenvalue computation on a non-backtracking matrix, giving an efficient purely spectral algorithm.

Key Results

  • Strong Refutations of Random $k$-XOR and $k$-CSPs: For any odd $k$ and predicate $P$ satisfied with probability $p$ by a random assignment, an efficient algorithm finds a certificate that $\text{Opt} \le p + O_k(\epsilon)$ with probability $\ge 0.99$ given $m \ge n^{k/2}/\epsilon^2$ constraints (Theorems 1 & 2). This completely shaves the $(\log n)^{O(1)}$ overhead of Allen, O’Donnell, and Witmer (2015).
  • Semi-Random CSP PTAS: A randomized algorithm running in $n^{O(k/\epsilon^2)}$ time outputs an assignment achieving value $\ge \text{Opt} - O(\epsilon)$ for $k$-CSPs with $m \ge n^{k/2}/\epsilon^2$ random constraints, even when the literal signs (negations) in each clause are chosen by an adversary (Theorems 3 & 4).

Limitations and Future Work

  • Algorithmic Runtime: The PTAS for semi-random CSPs runs in time $n^{O(k/\epsilon^2)}$; finding an algorithm polynomial in $1/\epsilon$ remains open.
  • Extension to Higher Levels of SoS: The current work relies on low-degree/spectral relaxations. The authors note that extending these non-backtracking techniques to higher-degree Sum-of-Squares hierarchies or more general sparse matrices with non-independent entries is an enticing future direction.

Summary updated

Abstract

We define a novel notion of "non-backtracking" matrix associated to any symmetric matrix, and we prove a "Ihara-Bass" type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfaction problems with k variables per constraints (k-CSPs). For a random k-CSP instance constructed out of a constraint that is satisfied by a p fraction of assignments, if the instance contains n variables and n^{k/2} / ε² constraints, we can efficiently compute a certificate that the optimum satisfies at most a p+O_k(ε) fraction of constraints. Previously, this was known for even k, but for odd k one needed n^{k/2} (log n)^{O(1)} / ε² random constraints to achieve the same conclusion. Although the improvement is only polylogarithmic, it overcomes a significant barrier to these types of results. Strong refutation results based on current approaches construct a certificate that a certain matrix associated to the k-CSP instance is quasirandom. Such certificate can come from a Feige-Ofek type argument, from an application of Grothendieck’s inequality, or from a spectral bound obtained with a trace argument. The first two approaches require a union bound that cannot work when the number of constraints is o(n^⌈k/2⌉) and the third one cannot work when the number of constraints is o(n^{k/2} √{log n}). We further apply our techniques to obtain a new PTAS finding assignments for k-CSP instances with n^{k/2} / ε² constraints in the semi-random settings where the constraints are random, but the sign patterns are adversarial.
BibTeX
@inproceedings{dorsi2023ihara,
  author = {Tommaso d'Orsi and Luca Trevisan},
  title = {{A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs}},
  booktitle = {CCC},
  year = {2023},
  url = {https://openreview.net/forum?id=e9Vd0I377H},
}
Figure