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

Tommaso d'Orsi, Luca Trevisan

Introduction

In theoretical computer science, the study of random Constraint Satisfaction Problems (CSPs), such as 3-SAT, often centers on the threshold at which an instance becomes unsatisfiable. While random instances are almost certainly unsatisfiable beyond a certain constraint density, the task of strong refutation—providing a polynomial-time certificate of unsatisfiability—is significantly more challenging.

For a $k$-CSP with $n$ variables, the information-theoretic threshold for unsatisfiability is linear in $n$. However, the computational threshold for efficient refutation has long been understood to be approximately $n^{k/2}$ constraints. While this threshold was achieved for even $k$ years ago, a persistent polylogarithmic gap remained for odd $k$. Specifically, existing spectral methods required $n^{k/2} \cdot (\log n)^{O(1)}$ constraints. This paper resolves this discrepancy by introducing a generalized Ihara-Bass formula, achieving the optimal refutation threshold for all $k$.

The Spectral Barrier in Sparse Regimes

The primary obstacle in reaching the $n^{k/2}$ threshold for odd $k$ lies in the limitations of standard spectral tools. Traditional approaches involve "flattening" the CSP tensor into a matrix and applying the trace method to bound its spectral norm. However, when the instance is sparse, the resulting matrices are highly non-uniform.

In these sparse regimes, the trace method incurs a logarithmic "penalty." This penalty arises because the eigenvalues of sparse random matrices are sensitive to local fluctuations in the graph structure. Consequently, the spectral norm does not concentrate tightly enough to distinguish between satisfiable and unsatisfiable instances at the optimal constraint density. This barrier was previously thought to be a fundamental limitation of spectral refutation for odd-degree predicates.

Generalizing the Ihara-Bass Formula

The authors overcome this barrier by shifting the analysis from standard adjacency matrices to non-backtracking matrices. A non-backtracking walk is a sequence of vertices where no edge is immediately traversed back to its origin. In graph theory, the Ihara-Bass formula is a celebrated identity that relates the zeta function of a graph to the determinant of its adjacency matrix.

The core theoretical contribution of this work is the extension of the Ihara-Bass theory from simple 0/1 adjacency matrices to any symmetric matrix $M$ with arbitrary real entries. The authors prove a novel identity relating the spectrum of a generalized non-backtracking matrix ($B_M$) to the original matrix ($M$). This generalization allows the non-backtracking machinery to be applied to the weighted matrices that arise from CSP tensors.

Non-Backtracking Spectral Analysis

The advantage of non-backtracking matrices lies in their behavior on sparse structures. In sparse random graphs, cycles are relatively rare, meaning the local neighborhood of a vertex looks like a tree for a long distance. Non-backtracking walks effectively "ignore" the local feedback loops that cause eigenvalue bloat in standard matrices.

By applying the trace method to the non-backtracking matrix $B_M$ rather than the original matrix $M$, the authors demonstrate that the spectral norm concentrates much more effectively. This allows them to bound the eigenvalues without the $(\log n)^{O(1)}$ penalty. To ensure these bounds hold with high probability, the authors introduce the concept of tangle-free hypergraphs—a flexible structural property that characterizes graphs where local cycles do not interfere with global spectral properties.

Key Results and Applications

The implications of this generalized formula are twofold:

  1. Optimal Refutation for Odd $k$: The paper proves that for random $k$-CSPs with odd $k$, $n^{k/2}/\epsilon^2$ constraints are sufficient for strong refutation. This matches the known lower bounds and finally removes the polylogarithmic gap from previous state-of-the-art results.
  2. Robustness in Semi-Random Models: The results extend to semi-random settings where the structure of the CSP is random, but the "signs" (negations of variables) are chosen by an adversary. The authors provide a Polynomial Time Approximation Scheme (PTAS) for these instances using a local-to-global rounding paradigm based on Sum-of-Squares (SOS) relaxations.

Conclusion

The generalization of the Ihara-Bass formula represents a significant advancement in matrix theory. Beyond its immediate application to $k$-CSPs, this tool provides a new lens for analyzing high-dimensional expanders, weighted graphs, and sparse recovery problems. By demonstrating that the polylogarithmic barrier was a limitation of our analytical tools rather than the problems themselves, this work provides the final piece of the puzzle for optimal spectral refutation of random CSPs.

Summary updated

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