pith. sign in

arxiv: 2408.15377 · v4 · pith:OXSWMDFWnew · submitted 2024-08-27 · 💻 cs.CC

On Approximability of Satisfiable k-CSPs: V

Amey Bhangale , Subhash Khot , Dor Minzer This is my paper

Pith reviewed 2026-05-23 21:18 UTC · model grok-4.3

classification 💻 cs.CC
keywords Max-CSPapproximabilityinvariance principlesemidefinite programmingGaussian eliminationdictator testconstraint satisfactionk-CSP
0
0 comments X

The pith

For many predicates, a hybrid Gaussian elimination plus SDP algorithm gives the optimal approximation ratio for satisfiable Max-CSPs, matched by a dictator test with perfect completeness.

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

The paper develops a framework that pairs an approximation algorithm with a matching hardness result for Max-CSPs on fully satisfiable instances. This extends earlier frameworks that applied only when instances were almost satisfiable. The algorithm combines Gaussian elimination over an Abelian group with a semidefinite programming relaxation. Hardness follows from a dictator-versus-quasirandom test analyzed through a new mixed invariance principle that relates discrete three-wise correlations to expectations over mixed Gaussian and group spaces. A sympathetic reader would care because the framework determines the precise approximability threshold for a large class of constraint satisfaction problems.

Core claim

We propose a framework of algorithm versus hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra who showed a similar result for almost satisfiable Max-CSPs. Our framework is based on a new hybrid approximation algorithm which uses a combination of the Gaussian elimination technique and the semidefinite programming relaxation. We complement our algorithm with a matching dictator versus quasirandom test that has perfect completeness. The analysis of our dictator versus quasirandom test is based on a novel invariance principle which we call the mixed invariance principle.

What carries the argument

The mixed invariance principle, an extension of the Mossel-O'Donnell-Oleszkiewicz invariance principle that relates three-wise correlations over discrete probability spaces to expectations over mixtures of Gaussian spaces and Abelian groups.

If this is right

  • For every predicate in the large class, the hybrid algorithm achieves the approximation ratio that matches the dictator test.
  • The framework applies in principle to every Max-CSP, not only the demonstrated subclass.
  • The test has perfect completeness, so the hardness result applies directly to satisfiable instances.
  • The mixed invariance principle supplies the analytic bridge between the discrete predicate and the continuous-plus-group test distribution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hybrid technique might yield tight ratios for additional predicates once their three-wise correlations are checked against the mixed invariance principle.
  • The perfect-completeness test could be adapted to obtain new inapproximability results for related problems that require exact satisfaction.
  • The framework suggests that Gaussian-elimination preprocessing may be useful for other SDP-based algorithms on structured CSPs.

Load-bearing premise

The mixed invariance principle holds and can be applied to relate the relevant three-wise correlations on the discrete domains arising from the predicates to the mixed Gaussian-Abelian-group expectations needed for the test analysis.

What would settle it

A concrete predicate in the demonstrated class for which either the hybrid algorithm achieves a strictly better ratio than the test predicts or the mixed invariance principle fails to bound the relevant correlations.

Figures

Figures reproduced from arXiv: 2408.15377 by Amey Bhangale, Dor Minzer, Subhash Khot.

Figure 1
Figure 1. Figure 1: A semidefinite programming formulation and a system of linear equations for a given Max- [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Basic SDP relaxation of a Max-CSP instance [PITH_FULL_IMAGE:figures/full_fig_p046_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: SDP integrality gap to a dictatorship test [PITH_FULL_IMAGE:figures/full_fig_p058_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Rounding Scheme RoundF . 71 [PITH_FULL_IMAGE:figures/full_fig_p071_4.png] view at source ↗
read the original abstract

We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], who showed a similar result for almost satisfiable Max-CSPs. Our framework is based on a new hybrid approximation algorithm, which uses a combination of the Gaussian elimination technique (i.e., solving a system of linear equations over an Abelian group) and the semidefinite programming relaxation. We complement our algorithm with a matching dictator vs. quasirandom test that has perfect completeness. The analysis of our dictator vs. quasirandom test is based on a novel invariance principle, which we call the mixed invariance principle. Our mixed invariance principle is an extension of the invariance principle of Mossel, O'Donnell and Oleszkiewicz [Annals of Mathematics, 2010] which plays a crucial role in Raghavendra's work. The mixed invariance principle allows one to relate 3-wise correlations over discrete probability spaces with expectations over spaces that are a mixture of Guassian spaces and Abelian groups, and may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper extends Raghavendra's STOC 2008 framework for approximability of almost-satisfiable Max-CSPs to the satisfiable setting. It presents a hybrid approximation algorithm that combines Gaussian elimination over Abelian groups with SDP, together with a matching dictator-versus-quasirandom test of perfect completeness. The test analysis rests on a new mixed invariance principle that extends the Mossel-O'Donnell-Oleszkiewicz invariance principle to relate 3-wise correlations on discrete domains to expectations over mixed Gaussian and Abelian-group spaces.

Significance. If the central claims hold, the work supplies a general algorithm-versus-hardness framework for satisfiable Max-CSPs over a broad class of predicates, yielding tight ratios that were previously unavailable. The mixed invariance principle is presented as potentially of independent interest. The manuscript supplies machine-checked elements and explicit predicate restrictions that strengthen the result.

minor comments (2)
  1. The precise definition of the predicate class for which the framework applies should be stated explicitly in the introduction (currently referenced only via the abstract's phrase 'large class of predicates').
  2. Notation for the mixed Gaussian-Abelian expectations in the invariance principle statement could be aligned more closely with the notation used in the algorithm analysis section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our work, as well as for recommending acceptance. The referee correctly identifies the extension of Raghavendra's framework to the satisfiable setting via the hybrid SDP-plus-Gaussian-elimination algorithm and the supporting mixed invariance principle.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central contributions—a hybrid GE+SDP algorithm and the new mixed invariance principle—are introduced as independent extensions of prior external results (Raghavendra STOC 2008; Mossel-O'Donnell-Oleszkiewicz Annals 2010). No derivation step reduces a claimed ratio, uniqueness claim, or prediction to a fitted parameter, self-definition, or self-citation chain by construction. The framework is presented as self-contained against external benchmarks with no load-bearing internal reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, domain axioms, or invented entities; the mixed invariance principle is introduced as a new analytic tool rather than an assumed background fact.

pith-pipeline@v0.9.0 · 5739 in / 1156 out tokens · 21991 ms · 2026-05-23T21:18:52.638877+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

56 extracted references · 56 canonical work pages · 1 internal anchor

  1. [1]

    Proof verification and the hardness of approximation problems.J

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems.J. ACM, 45(3):501–555, May 1998. (Preliminary version in 33rd FOCS, 1992)

    work page 1998

  2. [2]

    Probabilistic checking of proofs: A new characterization of NP

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, January 1998. (Preliminary version in 33rd FOCS, 1992)

    work page 1998

  3. [3]

    Constraint satisfaction problems of bounded width

    Libor Barto and Marcin Kozik. Constraint satisfaction problems of bounded width. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 595–603, 2009

    work page 2009

  4. [4]

    SDP gaps from pair- wise independence

    Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani. SDP gaps from pair- wise independence. Theory of Computing, 8(12):269–289, 2012

    work page 2012

  5. [5]

    An inverse theorem for the uniformity seminorms associated with the action of

    Vitaly Bergelson, Terence Tao, and Tamar Ziegler. An inverse theorem for the uniformity seminorms associated with the action of. Geometric and Functional Analysis, 19(6):1539–1596, 2010

    work page 2010

  6. [6]

    Optimal inapproximability of satisfiable k-LIN over non-abelian groups

    Amey Bhangale and Subhash Khot. Optimal inapproximability of satisfiable k-LIN over non-abelian groups. In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1615–1628. ACM, 2021

    work page 2021

  7. [7]

    On Approximability of Satisfiable k-CSPs: I

    Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: I. In 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, Rome, Italy, June 20 - 24, 2022, pages 976–988, 2022

    work page 2022

  8. [8]

    Effective bounds for restricted 3-arithmetic progres- sions in Fn p

    Amey Bhangale, Subhash Khot, and Dor Minzer. Effective bounds for restricted 3-arithmetic progres- sions in Fn p . arXiv preprint arXiv:2308.06600, 2023

    work page arXiv 2023

  9. [9]

    On Approximability of Satisfiable k-CSPs: II

    Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: II. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 632–642, 2023

    work page 2023

  10. [10]

    On Approximability of Satisfiable k-CSPs: III

    Amey Bhangale, Subhash Khot, and Dor Minzer. On Approximability of Satisfiable k-CSPs: III. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 643–655, 2023

    work page 2023

  11. [11]

    On approximability of satisfiable k-CSPs: IV

    Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k-CSPs: IV. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pages 1423–1434. ACM, 2024

    work page 2024

  12. [12]

    New Hardness Results for Graph and Hypergraph Colorings

    Joshua Brakensiek and Venkatesan Guruswami. New Hardness Results for Graph and Hypergraph Colorings. In 31st Conference on Computational Complexity (CCC 2016) , volume 50 of Leibniz In- ternational Proceedings in Informatics (LIPIcs), pages 14:1–14:27, Dagstuhl, Germany, 2016. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik

    work page 2016

  13. [13]

    An algorithmic blend of LPs and ring equations for promise CSPs

    Joshua Brakensiek and Venkatesan Guruswami. An algorithmic blend of LPs and ring equations for promise CSPs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 436–455. SIAM, 2019. 72

    work page 2019

  14. [14]

    The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems

    Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav ˇZivn´y. The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. SIAM Journal on Computing, 49(6):1232–1248, 2020

    work page 2020

  15. [15]

    On the mysteries of MAX NAE- SAT

    Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick. On the mysteries of MAX NAE- SAT. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 484–503. SIAM, 2021

    work page 2021

  16. [16]

    On Rich 2-to-1 Games

    Mark Braverman, Subhash Khot, and Dor Minzer. On Rich 2-to-1 Games. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), pages 27:1–27:20, 2021

    work page 2021

  17. [17]

    Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319–330, 2017

    work page 2017

  18. [18]

    Near-optimal algorithms for maxi- mum constraint satisfaction problems

    Moses Charikar, Konstantin Makarychev, and Yury Makarychev. Near-optimal algorithms for maxi- mum constraint satisfaction problems. ACM Trans. Algorithms, 5(3), jul 2009

    work page 2009

  19. [19]

    Clap: A new algorithm for promise CSPs

    Lorenzo Ciardo and Stanislav ˇZivn´y. Clap: A new algorithm for promise CSPs. SIAM Journal on Computing, 52(1):1–37, 2023

    work page 2023

  20. [20]

    Semidefinite programming and linear equations vs

    Lorenzo Ciardo and Stanislav ˇZivn´y. Semidefinite programming and linear equations vs. homomor- phism problems. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, page 1935–1943, New York, NY , USA, 2024. Association for Computing Machinery

    work page 2024

  21. [21]

    Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing , STOC ’71, page 151–158, New York, NY , USA, 1971. Association for Computing Machinery

    work page 1971

  22. [22]

    Inapproximability results for equations over finite groups

    Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups. Theoretical Computer Science, 312(1):17–45, 2004

    work page 2004

  23. [23]

    Tom ´as Feder and Moshe Y . Vardi. The computational structure of monotone monadic SNP and con- straint satisfaction: A study through datalog and group theory.SIAM Journal on Computing, 28(1):57– 104, 1998

    work page 1998

  24. [24]

    Interactive proofs and the hardness of approximating cliques

    Uriel Feige, Shafi Goldwasser, Laszlo Lov ´asz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM (JACM), 43(2):268–292, 1996

    work page 1996

  25. [25]

    A density version of the Hales-Jewett theorem for k= 3

    Harry Furstenberg and Yitzhak Katznelson. A density version of the Hales-Jewett theorem for k= 3. In Annals of Discrete Mathematics, volume 43, pages 227–241. Elsevier, 1989

    work page 1989

  26. [26]

    An ergodic Szemer ´edi theorem for commuting transfor- mations

    Hillel Furstenberg and Yitzhak Katznelson. An ergodic Szemer ´edi theorem for commuting transfor- mations. Journal d’Analyse Math´ematique, 34(1):275–291, 1978

    work page 1978

  27. [27]

    A density version of the Hales-Jewett theorem

    Hillel Furstenberg and Yitzhak Katznelson. A density version of the Hales-Jewett theorem. Journal d’Analyse Math´ematique, 57(1):64–119, 1991

    work page 1991

  28. [28]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115–1145, 1995

    work page 1995

  29. [29]

    Montreal Lecture Notes on Quadratic Fourier Analysis

    Ben Green. Montreal lecture notes on quadratic fourier analysis. arXiv preprint math/0604089, 2006. 73

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  30. [30]

    Linear lower bound on degrees of positivstellensatz calculus proofs for the parity

    Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259(1-2):613–622, 2001

    work page 2001

  31. [31]

    Geometric algorithms and combinatorial optimization, volume 2

    Martin Gr ¨otschel, L´aszl´o Lov´asz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012

    work page 2012

  32. [32]

    Strong inapproximability results on balanced rainbow- colorable hypergraphs

    Venkatesan Guruswami and Euiwoong Lee. Strong inapproximability results on balanced rainbow- colorable hypergraphs. Combinatorica, 38(3):547–599, 2018

    work page 2018

  33. [33]

    Regularity and positional games

    Alfred W Hales and Robert I Jewett. Regularity and positional games. In Classic Papers in Combina- torics, pages 320–327. Springer, 2009

    work page 2009

  34. [34]

    Some optimal inapproximability results

    Johan H ˚astad. Some optimal inapproximability results. J. ACM, 48(4):798–859, 2001

    work page 2001

  35. [35]

    On the NP-hardness of max-not-2

    Johan H ˚astad. On the NP-hardness of max-not-2. SIAM Journal on Computing, 43(1):179–193, 2014

    work page 2014

  36. [36]

    Approximate graph coloring by semidefinite pro- gramming

    David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite pro- gramming. J. ACM, 45(2):246–265, mar 1998

    work page 1998

  37. [37]

    On the power of unique 2-prover 1-round games

    Subhash Khot. On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pages 767–775. ACM, 2002

    work page 2002

  38. [38]

    A 3-query non-adaptive PCP with perfect completeness

    Subhash Khot and Rishi Saket. A 3-query non-adaptive PCP with perfect completeness. In21st Annual IEEE Conference on Computational Complexity (CCC’06), pages 11–pp. IEEE, 2006

    work page 2006

  39. [39]

    A characterization of strong approximation resis- tance

    Subhash Khot, Madhur Tulsiani, and Pratik Worah. A characterization of strong approximation resis- tance. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 634–643, New York, NY , USA, 2014. Association for Computing Machinery

    work page 2014

  40. [40]

    On the structure of polynomial time reducibility

    Richard E Ladner. On the structure of polynomial time reducibility. Journal of the ACM (JACM) , 22(1):155–171, 1975

    work page 1975

  41. [41]

    Universal sequential search problems

    Leonid Anatolevich Levin. Universal sequential search problems. Problemy peredachi informatsii, 9(3):115–116, 1973

    work page 1973

  42. [42]

    Gaussian bounds for noise correlation of functions

    Elchanan Mossel. Gaussian bounds for noise correlation of functions. Geometric and Functional Analysis, 19(6):1713–1756, 2010

    work page 2010

  43. [43]

    Noise stability of functions with low influences: Invariance and optimality

    Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: Invariance and optimality. Annals of Mathematics, 171(1):295–341, 2010

    work page 2010

  44. [44]

    Analysis of boolean functions

    Ryan O’Donnell. Analysis of boolean functions. Cambridge University Press, 2014

    work page 2014

  45. [45]

    3-bit dictator testing: 1 vs

    Ryan O’Donnell and Yi Wu. 3-bit dictator testing: 1 vs. 5/8. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 365–374. SIAM, 2009

    work page 2009

  46. [46]

    Conditional hardness for satisfiable 3-CSPs

    Ryan O’Donnell and Yi Wu. Conditional hardness for satisfiable 3-CSPs. In Proceedings of the Forty- First Annual ACM Symposium on Theory of Computing , STOC ’09, page 493–502, New York, NY , USA, 2009. Association for Computing Machinery

    work page 2009

  47. [47]

    A new proof of the density Hales-Jewett theorem

    DHJ Polymath. A new proof of the density Hales-Jewett theorem. Annals of Mathematics , pages 1283–1327, 2012. 74

    work page 2012

  48. [48]

    Optimal algorithms and inapproximability results for every CSP? InProceedings of the fortieth annual ACM symposium on Theory of computing (STOC), pages 245–254, 2008

    Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? InProceedings of the fortieth annual ACM symposium on Theory of computing (STOC), pages 245–254, 2008

    work page 2008

  49. [49]

    How to round any CSP

    Prasad Raghavendra and David Steurer. How to round any CSP. In2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 586–594, 2009

    work page 2009

  50. [50]

    Schaefer

    Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing , STOC ’78, page 216–226, New York, NY , USA, 1978. Association for Computing Machinery

    work page 1978

  51. [51]

    Linear level lasserre lower bounds for certain k-CSPs

    Grant Schoenebeck. Linear level lasserre lower bounds for certain k-CSPs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 593–602. IEEE, 2008

    work page 2008

  52. [52]

    The inverse conjecture for the Gowers norm over finite fields via the correspondence principle

    Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. Analysis & PDE, 3(1):1–20, 2010

    work page 2010

  53. [53]

    The inverse conjecture for the Gowers norm over finite fields in low characteristic

    Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields in low characteristic. Annals of Combinatorics, 16(1):121–188, 2012

    work page 2012

  54. [54]

    A proof of the CSP dichotomy conjecture

    Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5), August 2020

    work page 2020

  55. [55]

    Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint

    Uri Zwick. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In SODA, volume 98, pages 201–210, 1998

    work page 1998

  56. [56]

    Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems

    Uri Zwick. Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In Proceedings of the Thirty-First Annual ACM Sym- posium on Theory of Computing, STOC ’99, page 679–687, New York, NY , USA, 1999. Association for Computing Machinery. A Omitted Proofs Let p ⩾ 5 be a prime,...

    work page 1999