On Approximability of Satisfiable $k$-CSPs: VII

Amey Bhangale; Dor Minzer; Subhash Khot; Yang P. Liu

REVIEW 2 major objections 5 minor 1 cited by

On Approximability of Satisfiable $k$-CSPs: VII

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that a k-variable distribution with no Abelian embedding forces any k-tuple of 1-bounded, high-degree functions to have vanishing correlation, confirming the inverse conjecture for satisfiable k-CSPs for every k; the…

desk verdict Likely-true extension of the k=3 inverse theorem to all k, but the written proof has a demonstrable false step in the Section 3.3 decomposition that needs repair. read the letter →

arxiv 2411.15136 v1 pith:SWIWLUDJ submitted 2024-11-22 cs.CC math.CO

Amey Bhangale , Subhash Khot , Yang P. Liu , Dor Minzer This is my paper · ORCID

classification cs.CCmath.CO MSC 68Q1768Q25

keywords constraintsatisfactionsatisfiableCSPsAbelianembeddingsinversetheoremsnoisestabilityk-wisecorrelationdictatorshiptestsdensityHales-Jewett

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper settles an analytic question at the heart of approximating satisfiable constraint satisfaction problems: when does an n-fold product distribution erase all correlation among tuples of functions that depend on many coordinates? Its central theorem says the only obstacle is an Abelian embedding, a system of maps into an Abelian group, not all constant, whose sum vanishes on every supported tuple. If no such embedding exists, then any k functions whose product correlation is at least ε must each have a positive amount of low-frequency, noise-stable mass; equivalently, functions that genuinely depend on many coordinates cannot correlate. Because the parameters depend only on the alphabet size, the minimum atom probability, and ε, the result transfers to dictatorship tests with perfect completeness, giving evidence that natural SDP relaxations are optimal even for fully satisfiable instances.

What carries the argument

The proof is an induction on k whose inductive step is a Cauchy-Schwarz reduction to a (k−1)-ary instance, followed by re-encoding the remaining correlation as a 3-wise correlation over an auxiliary pairwise-connected distribution ξ on Σ×Σ×(Σ×Σ∪{⋆}). A 3-ary local inverse theorem, applied after a random restriction, converts that correlation into local product structure; then a lattice-based lemma about product functions under no-Abelian-embedding distributions upgrades the local structure to noise stability. The quantitative engine is a recursive bound on the stability parameter δ_k, ultimately giving δ_k ≥ exp(−exp(⋯exp($ε^{{−O_α(1)}}$))) with $k^{{O(k)}}$ iterated exponentials.

What would settle it

A concrete disproof of Theorem 1 would be a tuple of 1-bounded functions, on a distribution with no Abelian embedding and atom probabilities at least α, whose product correlation is at least ε on $μ^{{⊗n}}$ but with Stab_{1−δ}(f_i)<δ for the δ claimed in the theorem. A more local falsifier lives inside the proof: for the specific distribution ξ constructed in Section 3.3, exhibit a value of ζ<1 for which no distribution ξ' with the same support and all atom probabilities at least α² exists; that would falsify the inductive step as written.

Watch

Extended reading notes

Core claim

The paper establishes Conjecture 1.2 in full generality: for a distribution μ over Σ_1×⋯×Σ_k with every atom of probability at least α and with no Abelian embedding, and for 1-bounded functions f_i:Σ_i^n→C, if |E_{(x_1,…,x_k)∼$μ^{{⊗n}}$}[∏_i f_i(x_i)]| ≥ ε, then Stab_{1−δ}(f_i) ≥ δ for every i, where δ depends only on k, α, and ε. In other words, any tuple whose product correlates must have each coordinate function supported on low-degree Fourier structure. The paper also proves local inverse theorems under milder assumptions, a global inverse theorem that correlates f_1 with a low-degree function times a product function, and a dictatorship-test consequence for predicates with no Abelian embedding.

Load-bearing premise

The load-bearing premise is that the auxiliary pairwise-connected distribution ξ in Section 3.3 splits as ζξ'+(1−ζ)ξ'' with ξ' having the same support as ξ and all atoms at least α²; for ζ<1 this is not automatic, and proving it, together with the correctness of the companion paper's 3-ary inverse theorem, is what the induction actually depends on.

Editorial extensions

If this is right

Conjecture 1.2 is confirmed for all arities: only Abelian embeddings allow nonvanishing k-wise correlation between high-degree functions.
Predicates satisfying the no-Abelian-embedding and integrality-gap conditions acquire dictatorship tests with perfect completeness and soundness s+ε, so the natural SDP relaxation with rounding is optimal up to ε for satisfiable instances.
The local inverse theorem under the milder μ_{−k} condition yields a global inverse theorem: nonvanishing correlation implies f_1 correlates with a low-degree function times a product function.
The k=4 case of Lemma 1.5 leads to improved quantitative bounds for the density Hales-Jewett theorem on {0,1,2}^n, where density Ω((log log log log n)^{−c}) suffices to force a combinatorial line.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extending the paper's lattice argument, one would expect that once Abelian embeddings exist, all nonvanishing k-wise correlations are carried by characters of the ambient Abelian group, which is exactly the structure used in Gowers-norm inverse theorems over finite fields.
If Lemma 1.5's single-exponential dependence is tight, density bounds for higher-arity Hales-Jewett-type statements should follow a similar hierarchy, losing roughly one log per additional coordinate.
If the Section 3.3 decomposition cannot be supplied as stated, the theorem might still hold through a different auxiliary distribution; a repair would likely require an explicit high-mass subset argument rather than renormalizing the entire support.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version. This paper likely proves the right theorem, but the written proof has a real gap. The main result—verifying Conjecture 1.2 for all arity k—is a genuine advance over the k=3 case, and the induction via Cauchy-Schwarz followed by a 3-ary inverse theorem is a substantial technical contribution. The exposition is clear and the quantitative bounds are explicit. The local and global inverse theorems in Section 1.4 look like useful tools for the series.

The soft spot is Section 3.3. The proof asserts that the auxiliary distribution ξ can be written as ζξ' + (1−ζ)ξ'' with ζ ≥ α^2 δ_{k−1}, where ξ' has the same support as ξ and every atom of ξ' has probability at least α^2. That is impossible in general, because it forces |supp(ξ')| ≤ α^{−2}. I checked a concrete valid instance: k=4, α=0.1, Σ1={1,...,10}, Σ2=Σ3=Σ4 singletons, µ uniform on {(i,c,d,z)}. Following the construction gives |supp(ξ)| = 110 > 100 = α^{−2}, so no such ξ' exists. This is not a missing detail; it is a false statement. A related small error: the claim that every atom of ξ has mass at least α^2 δ_{k−1} is too strong; the ⋆ atoms have mass α^2 δ_{k−1} μ1(x), which can be as small as α^3 δ_{k−1}.

The good news is that the gap looks repairable. Applying Theorem 5 directly to ξ with the correct atom bound (α^3 δ_{k−1}, or a high-mass connected subset) would likely carry the induction through, at the cost of slightly worse quantitative bounds. The paper also depends on Theorem 5 from the unpublished companion BKLM24a; that is a real dependency, but it is a separate result, not a circular one.

Bottom line: important result, likely true, but not ready for acceptance. It deserves a serious referee and a major revision. I would not cite the main theorem in my own work until the inductive step is fixed.

Referee Report

2 major / 5 minor

Summary. The paper proves a k-ary inverse theorem for distributions over finite alphabets with no Abelian embeddings: whenever k bounded functions have k-wise correlation at least epsilon under the n-fold product of such a distribution, every function has noise stability at least delta at parameter 1 - delta, with delta a tower-type function of k, alpha, and epsilon. The authors also prove local inverse theorems under the milder assumption of pairwise connectivity, a global inverse theorem, and corollaries for dictatorship tests and hardness of approximating satisfiable CSPs. The proof is by induction on k, using the k = 3 theorem of [BKM23a] and a 3-ary local inverse theorem of the unpublished companion [BKLM24a] as black boxes.

Significance. If correct, Theorem 1 confirms Conjecture 1.2 for all k and answers the analytic question from [BKM22], giving the first k-ary inverse theorem for distributions without Abelian embeddings. The paper also contains useful extensions: Lemma 1.4, Lemma 1.5, and Theorem 3, together with explicit tower-type quantitative bounds, and the advertised consequences for the density Hales-Jewett theorem and for CSP hardness. The high-level induction strategy is natural, and the paper is clearly written. However, the proof of the inductive step contains a concrete false decomposition, so the manuscript in its present form does not establish the main theorem.

major comments (2)

[Section 3.3] The proof that Theorem 1 for k-1 implies Lemma 1.4 for k contains the assertion: 'we may write xi = zeta xi' + (1 - zeta) xi'' where zeta >= alpha^2 delta_{k-1}, the probability of each atom in xi' is at least alpha^2 and xi' has the same support as xi.' This is false in general. If xi' has the same support S and every atom has mass at least alpha^2, then 1 = sum_{a in S} xi'(a) >= |S| alpha^2, so |S| <= alpha^{-2} is necessary. The construction of xi does not enforce this bound. Concretely, take k = 4, alpha = 0.1, Sigma_1 = {1,...,10}, Sigma_2 = {c}, Sigma_3 = {d}, Sigma_4 = {z}, and mu uniform on {(i,c,d,z) : i = 1,...,10}; this distribution is pairwise-connected and mu_{-4} has no Abelian embedding, yet the construction in Sections 3.2-3.3 gives a support of size 110 > alpha^{-2} = 100, so no distribution on the same support can have all atoms at least alpha^2. This invalidates the inductive step as written. Separately, the same passage states that all atoms of xi have mass at least alpha^2 delta_{k-1}; this also does not follow, since the (x,x,star) atoms have mass alpha^2 mu_1(x) delta_{k-1}, which is smaller than alpha^2 delta_{k-1} whenever mu_1(x) < 1. The central theorem may still be true, and the gap may be repairable by applying Theorem 5 directly to xi with a correct atom lower bound or by passing to a high-mass subset, but that repair is not supplied.
[Section 3.3] The proof invokes Theorem 5 of [BKLM24a] as a black box at the decisive point of the induction. That companion paper is listed as unpublished ('2024+') and its theorem is not stated in this manuscript. Since the conclusion of the induction depends on the exact quantitative form and hypotheses of Theorem 5, the current submission is not self-contained and cannot be fully verified independently. The authors should either include a proof of the needed 3-ary local inverse theorem or provide the precise statement and a publicly available version of [BKLM24a].

minor comments (5)

[Section 3.3 / Observation 4] The notation nu_1 appears in Section 3.3 and in Observation 4 without definition; it presumably means the distribution nu from Section 3.2. Please define it or use a consistent symbol.
[Observation 4] Observation 4 writes the random subset as I ~ 1-alpha [n], but the preceding derivation in Eq. (2) uses I ~ 1-alpha^2 [n]. This is likely a typo and should be corrected.
[Remark after Theorem 1] The remark says 'The condition that Stab_{1-delta}(f_i) <= delta serves as a convenient proxy for the condition that the function f_i is essentially of high degree,' but the theorem's conclusion is Stab_{1-delta}(f_i) >= delta. The displayed inequality in the remark is inconsistent with the theorem and should be changed to >= delta if the intended proxy is for low-degree structure.
[Lemma 3.4] In the derivation of Eq. (7), the text asserts that E_{x ~ mu_1, y ~ 1-gamma x} P_1^{(j)}(x) overline{P_1^{(j)}(y)} is a real number. For complex-valued 1-bounded functions this need not be true; the argument should be written with the real part of the expectation.
[Corollary 3.2] The statement contains a duplicated word: '1-bounded functions functions f_i'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the inductive proof imports separate prior theorems rather than restating the target result, and the Section 3.3 decomposition flaw is a correctness gap, not a circular reduction.

full rationale

Theorem 1 is proved by induction: the k=3 base case is taken from the prior theorem of [BKM23a], and the inductive step applies the 3-ary local inverse theorem from [BKLM24a]. Both are separate statements with their own proofs; neither is defined in terms of the present theorem, and no equation in the paper identifies a predicted quantity with a fitted input. The only load-bearing step that is vulnerable is the assertion in Section 3.3 that xi can be decomposed as xi = zeta xi' + (1-zeta) xi'' with xi' supported on all of supp(xi) and atom probabilities at least alpha^2; as written, this is not generally true, since the support size can exceed alpha^{-2}. But an invalid intermediate claim is a correctness problem, not a circularity: it does not make the conclusion an input by construction. The same-author citations are ordinary dependencies on prior published or companion work, so under the stated rules they do not raise the circularity score.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters are fitted; delta is derived from alpha and epsilon. The proof rests on three external inverse theorems, two from the same authors' series. These are not circular in the sense of assuming the target result, but they must be correct for the induction to go through.

assumptions (3)

domain assumption Theorem 4 (BKM23a): the k=3 case of the inverse theorem for distributions with no Abelian embedding is correct.
Used as base case for the induction; quoted from prior work without proof in this paper.
domain assumption Theorem 5 (BKLM24a): local inverse theorem for pairwise-connected 3-ary distributions is correct.
Used in the inductive step to extract product-function correlation from the constructed distribution xi; the companion paper is unpublished (2024+).
standard math Lemma 2.3 (Mossel, Lemma 6.2): connected distributions satisfy the noise-stability inverse theorem with quantitative bound delta >= (epsilon * alpha)^{O(1)}.
Used in the proof of Lemma 1.5; published result taken as background.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Approximability of Satisfiable $k$-CSPs: VII." pith.science (2026). https://pith.science/paper/SWIWLUDJ

@misc{pith2026241115136,
  author       = {Pith},
  title        = {Pith review of: On Approximability of Satisfiable $k$-CSPs: VII},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SWIWLUDJ}},
  note         = {Machine review of arXiv:2411.15136}
}

abstract

Let $\Sigma_1,\ldots,\Sigma_k$ be finite alphabets, and let $\mu$ be a distribution over $\Sigma_1 \times \dots \times \Sigma_k$ in which the probability of each atom is at least $\alpha$. We prove that if $\mu$ does not admit Abelian embeddings, and $f_i: \Sigma_i \to \mathbb{C}$ are $1$-bounded functions (for $i=1,\ldots,k$) such that \[ \left|\mathbb{E}_{(x_1,\dots,x_k) \sim \mu^{\otimes n}}\Big[f_1(x_1) \dots f_k(x_k)\Big]\right| \geq \varepsilon, \] then there exists $L\colon \Sigma_1^n\to\mathbb{C}$ of degree at most $d$ and $\|L\|_2\leq 1$ such that $|\langle f_1, L\rangle|\geq \delta$, where $d$ and $\delta>0$ depend only on $k, \alpha$ and $\varepsilon$. This answers the analytic question posed by Bhangale, Khot, and Minzer (STOC 2022). We also prove several extensions of this result that are useful in subsequent applications.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Biased Linearity Testing in the 1% Regime
cs.CC 2025-02 conditional novelty 7.0 of 10

For the p-biased hypercube, a k-query linearity test works in the 1% regime if and only if k is at least 1 + 1/min{p,1-p}, up to an odd-k boundary case involving cyclic characters.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages · cited by 1 Pith paper

[2]

[BK21] Amey Bhangale and Subhash Khot

(Preliminary version in 33rd FOCS, 1992). [BK21] Amey Bhangale and Subhash Khot. Optimal Inapproxima bility of Satisﬁable k-LIN over Non- Abelian Groups. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC) , page 1615–1628,

work page 1992
[5]

On appr oximability of satisﬁable k -csps: I

[BKM22] Amey Bhangale, Subhash Khot, and Dor Minzer. On appr oximability of satisﬁable k -csps: I. In STOC 2022 , pages 976–988. ACM,

work page 2022
[6]

On app roximability of satisﬁable k-csps: II

[BKM23a] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisﬁable k-csps: II. In STOC 2023 , pages 632–642. ACM,

work page 2023
[8]

On app roximability of satisﬁable k-csps: IV

[BKM24a] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisﬁable k-csps: IV. In STOC 2024 , pages 1423–1434. ACM,

work page 2024
[11]

A quantitative inverse theorem for the U 4 norm over ﬁnite ﬁelds

[GM17] WT Gowers and Luka Milićević. A quantitative inverse theorem for the U 4 norm over ﬁnite ﬁelds. arXiv preprint arXiv:1712.00241 ,

arXiv
[1989]

[FK91] H

Graph theory and combinatorics (C ambridge, 1988). [FK91] H. Furstenberg and Y. Katznelson. A density version o f the Hales-Jewett theorem. J. Anal. Math., 57:64–119,

1988
[1998]

[AS98] Sanjeev Arora and Shmuel Safra

(Preliminary version in 33rd FOCS, 1992). [AS98] Sanjeev Arora and Shmuel Safra. Probabilistic check ing of proofs: A new characterization of NP. Journal of the ACM , 45(1):70–122, January

work page 1992
[2001]

[Kho02] Subhash Khot

(Preliminary version in 29th STOC , 1997). [Kho02] Subhash Khot. On the power of unique 2-prover 1-roun d games. In Proceedings of the 34th Annual ACM symposium on Theory of computing (STOC) , pages 767–775. ACM,

work page 1997

Show all 12 references

[2021]

An invariance principle for the multi-slice, with applications

[BKLM22] Mark Braverman, Subhash Khot, Noam Lifshitz, and D or Minzer. An invariance principle for the multi-slice, with applications. In FOCS 2022 , pages 228–236,

2022
[2022]

Liu, and Dor M inzer

[BKLM24a] Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor M inzer. On approximability of satisﬁable k-csps: VI. 2024+. [BKLM24b] Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor M inzer. Reasonable bounds for combi- natorial lines of length three. 2024+. [BKM21] Mark Braver...

2024
[2023]

On app roximability of satisﬁable k-csps: III

[BKM23b] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisﬁable k-csps: III. In STOC 2023 , pages 643–655. ACM,

2023
[2024]

On app roximability of satisﬁable k-csps: V

[BKM24b] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisﬁable k-csps: V. CoRR, abs/2408.15377,

arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [2]

[BK21] Amey Bhangale and Subhash Khot

(Preliminary version in 33rd FOCS, 1992). [BK21] Amey Bhangale and Subhash Khot. Optimal Inapproxima bility of Satisﬁable k-LIN over Non- Abelian Groups. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC) , page 1615–1628,

work page 1992

[2] [5]

On appr oximability of satisﬁable k -csps: I

[BKM22] Amey Bhangale, Subhash Khot, and Dor Minzer. On appr oximability of satisﬁable k -csps: I. In STOC 2022 , pages 976–988. ACM,

work page 2022

[3] [6]

On app roximability of satisﬁable k-csps: II

[BKM23a] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisﬁable k-csps: II. In STOC 2023 , pages 632–642. ACM,

work page 2023

[4] [8]

On app roximability of satisﬁable k-csps: IV

[BKM24a] Amey Bhangale, Subhash Khot, and Dor Minzer. On app roximability of satisﬁable k-csps: IV. In STOC 2024 , pages 1423–1434. ACM,

work page 2024

[5] [11]

A quantitative inverse theorem for the U 4 norm over ﬁnite ﬁelds

[GM17] WT Gowers and Luka Milićević. A quantitative inverse theorem for the U 4 norm over ﬁnite ﬁelds. arXiv preprint arXiv:1712.00241 ,

arXiv

[6] [1989]

[FK91] H

Graph theory and combinatorics (C ambridge, 1988). [FK91] H. Furstenberg and Y. Katznelson. A density version o f the Hales-Jewett theorem. J. Anal. Math., 57:64–119,

1988

[7] [1998]

[AS98] Sanjeev Arora and Shmuel Safra

(Preliminary version in 33rd FOCS, 1992). [AS98] Sanjeev Arora and Shmuel Safra. Probabilistic check ing of proofs: A new characterization of NP. Journal of the ACM , 45(1):70–122, January

work page 1992

[8] [2001]

[Kho02] Subhash Khot

(Preliminary version in 29th STOC , 1997). [Kho02] Subhash Khot. On the power of unique 2-prover 1-roun d games. In Proceedings of the 34th Annual ACM symposium on Theory of computing (STOC) , pages 767–775. ACM,

work page 1997