Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
Pith reviewed 2026-05-24 19:59 UTC · model grok-4.3
The pith
High-dimensional expanders on hypergraphs let sum-of-squares approximate MAX k-CSP to additive error ε with q to the O of k times (k over ε) to the O of 1 levels.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
If an instance of MAX k-CSP over alphabet [q] is a high-dimensional expander with parameter γ, then it is possible to approximate the maximum fraction of satisfiable constraints up to an additive error ε using q^{O(k)} · (k/ε)^{O(1)} levels of the sum-of-squares SDP hierarchy, provided γ ≤ ε^{O(1)} · (1/(kq))^{O(k)}. Instances with threshold rank r at threshold τ = (ε/k)^{O(1)} · (1/q)^{O(k)} admit an approximation using r · q^{O(k)} · (k/ε)^{O(1)} levels, and high-dimensional expanders with small γ have threshold rank 1.
What carries the argument
The high-dimensional expansion parameter γ of the hypergraph, which controls the error propagation in the sum-of-squares analysis and implies low threshold rank.
If this is right
- MAX k-CSP instances on high-dimensional expanders with small γ can be approximated to additive error ε using q^{O(k)} · (k/ε)^{O(1)} levels of sum-of-squares.
- Instances whose hypergraph has threshold rank r at the given threshold admit approximation using r · q^{O(k)} · (k/ε)^{O(1)} levels.
- High-dimensional expanders with sufficiently small γ have threshold rank 1 under the new definition for hypergraphs.
Where Pith is reading between the lines
- The same expansion condition might support approximation results for other SDP hierarchies or rounding procedures on k-uniform hypergraphs.
- Threshold rank could serve as a broader classification tool to identify additional families of hypergraphs that admit efficient approximation.
- The result suggests that expansion properties, rather than arity alone, determine whether structured k-CSP instances escape the hardness seen in random cases.
Load-bearing premise
The sum-of-squares analysis that works for graphs extends without essential change to k-CSPs on hypergraphs satisfying the expansion condition.
What would settle it
An explicit MAX k-CSP instance on a hypergraph with expansion parameter γ below the stated threshold where the sum-of-squares hierarchy at q^{O(k)} · (k/ε)^{O(1)} levels fails to produce an additive ε-approximation to the optimum.
read the original abstract
We consider the problem of approximately solving constraint satisfaction problems with arity $k > 2$ ($k$-CSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of $k$-CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed to be hard to approximate in polynomial time). However, we show that this is not necessarily the case for instances where the hypergraph is a high-dimensional expander. We consider the spectral definition of high-dimensional expansion used by Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs. They measure the expansion in terms of a parameter $\gamma$ which is the analogue of the second singular value for expanding graphs. Extending the results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that if an instance of MAX k-CSP over alphabet $[q]$ is a high-dimensional expander with parameter $\gamma$, then it is possible to approximate the maximum fraction of satisfiable constraints up to an additive error $\epsilon$ using $q^{O(k)} \cdot (k/\epsilon)^{O(1)}$ levels of the sum-of-squares SDP hierarchy, provided $\gamma \leq \epsilon^{O(1)} \cdot (1/(kq))^{O(k)}$. Based on our analysis, we also suggest a notion of threshold-rank for hypergraphs, which can be used to extend the results for approximating 2-CSPs on low threshold-rank graphs. We show that if an instance of MAX k-CSP has threshold rank $r$ for a threshold $\tau = (\epsilon/k)^{O(1)} \cdot (1/q)^{O(k)}$, then it is possible to approximately solve the instance up to additive error $\epsilon$, using $r \cdot q^{O(k)} \cdot (k/\epsilon)^{O(1)}$ levels of the sum-of-squares hierarchy. As in the case of graphs, high-dimensional expanders (with sufficiently small $\gamma$) have threshold rank 1 according to our definition.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that MAX k-CSP instances (k>2) whose underlying hypergraph is a high-dimensional expander in the Dinur-Kaufman sense (with small spectral parameter γ) admit additive ε-approximation via q^{O(k)}·(k/ε)^{O(1)} levels of the sum-of-squares hierarchy, provided γ ≤ ε^{O(1)}·(1/(kq))^{O(k)}. It extends the Barak-Raghavendra-Steurer spectral SoS analysis from 2-CSPs on graphs to k-CSPs on hypergraphs and introduces an analogous notion of threshold rank for hypergraphs, showing that low threshold-rank instances are likewise approximable at the same SoS level.
Significance. If the claimed extension of the BRS analysis holds, the result supplies a concrete algorithmic regime in which high-dimensional expansion yields efficient SoS-based approximation for higher-arity CSPs, in contrast to the believed hardness of random instances. The suggested threshold-rank definition for hypergraphs is a natural and potentially useful generalization that could support further work on non-expander instances.
major comments (1)
- [abstract, §1, and the proof of the main theorem] The central claim (abstract and §1) that the BRS spectral analysis extends to k-uniform hypergraphs under the Dinur-Kaufman link-expansion condition γ is load-bearing for both the level bound q^{O(k)}·(k/ε)^{O(1)} and the required γ threshold. The manuscript states the extension but does not exhibit the concrete substitution of the link-expansion parameter for the second singular value inside the key SoS inequalities (e.g., those controlling the pseudoexpectation or the rounding analysis). Without these steps, the claimed dependence on k and q cannot be verified.
minor comments (2)
- [§2] Notation for the Dinur-Kaufman expansion parameter γ and its relation to the links of the hypergraph should be introduced with a short self-contained definition before the main theorem statement.
- [§4] The threshold-rank definition for hypergraphs (introduced after the main theorem) would benefit from an explicit comparison table to the graph case in BRS.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for highlighting the need for greater explicitness in the extension of the BRS analysis. We address the major comment below and will incorporate the requested clarifications in the revised version.
read point-by-point responses
-
Referee: [abstract, §1, and the proof of the main theorem] The central claim (abstract and §1) that the BRS spectral analysis extends to k-uniform hypergraphs under the Dinur-Kaufman link-expansion condition γ is load-bearing for both the level bound q^{O(k)}·(k/ε)^{O(1)} and the required γ threshold. The manuscript states the extension but does not exhibit the concrete substitution of the link-expansion parameter for the second singular value inside the key SoS inequalities (e.g., those controlling the pseudoexpectation or the rounding analysis). Without these steps, the claimed dependence on k and q cannot be verified.
Authors: We agree that the current write-up of the proof does not spell out the precise substitution of the Dinur-Kaufman link-expansion parameter γ in place of the second singular value inside the key SoS inequalities that appear in the BRS analysis. In the revised manuscript we will add an explicit subsection (immediately following the statement of the main theorem) that performs this substitution step-by-step: we will show how the hypergraph link-expansion condition is used to bound the relevant pseudo-expectation moments that control the SoS value, and how the same parameter enters the rounding analysis to obtain the additive ε guarantee. The resulting level bound q^{O(k)}·(k/ε)^{O(1)} and the required γ threshold will then be directly verifiable from the displayed inequalities. revision: yes
Circularity Check
No circularity; extension of external BRS SoS analysis presented as new contribution
full rationale
The paper explicitly extends the Barak-Raghavendra-Steurer 2011 result (external citation, different authors) to k-CSPs on Dinur-Kaufman HD expanders and states the level bound as following from that extension plus the spectral parameter γ. No self-citation is load-bearing, no parameter is fitted to the target quantity and renamed as prediction, and no ansatz or uniqueness theorem is smuggled from prior author work. The derivation chain is therefore self-contained against the cited external benchmark.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The sum-of-squares analysis and rounding procedure developed for 2-CSPs on graphs extends to k-CSPs on hypergraphs satisfying the Dinur-Kaufman spectral expansion condition.
- domain assumption High-dimensional expansion is measured by the parameter γ that is the analogue of the second singular value.
invented entities (1)
-
threshold rank for hypergraphs
no independent evidence
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.