Pith. sign in

REVIEW 4 major objections 5 minor 57 references

Two cut problems reach their exact hardness limits.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-04 00:43 UTC pith:NC6SW5JF

load-bearing objection A credible proof of two long-open sharp hardness results, held up by numerical certificates that need independent checking. the 4 major comments →

arxiv 2608.00333 v1 pith:NC6SW5JF submitted 2026-07-31 cs.CC math.COmath.PR

Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT

Steven Heilman This is my paper
classification cs.CC math.COmath.PR MSC 68W2765K1068Q32
keywords MAX-3-CUTQuantum MAX-CUTUnique Games ConjecturePlurality is StablestBorell's inequalitynoise stabilitysemidefinite programminghardness of approximation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper claims that, assuming the Unique Games Conjecture, the best polynomial-time approximation algorithms for MAX-3-CUT and for product-state Quantum MAX-CUT are exactly optimal: narrowing the gap by any multiplicative factor epsilon > 0 is NP-hard. The missing ingredients were two Gaussian noise-stability inequalities — the three-set Standard Simplex / Plurality-is-Stablest inequality for correlations in [-1/2, 2/5] and the S^{k-1}-valued Borell inequality for the correlations used by the quantum reductions. The paper proves these inequalities by reducing them to operator-norm bounds on matrices in a radial Laguerre basis, with the final bounds obtained by finite numerical blocks plus analytic tail estimates. A by-product is the best known conditional hardness for MAX-2-LIN(3).

Core claim

Under the Unique Games Conjecture, for every epsilon>0 it is NP-hard to approximate MAX-3-CUT within alpha_3+epsilon (alpha_3≈0.836, the Frieze–Jerrum ratio) and product-state Quantum MAX-CUT within alpha_BOV+epsilon (alpha_BOV≈0.9563, the BOV ratio); the same hardness extends to general Quantum MAX-CUT. The analytic core is a proof of the three-candidate Plurality-is-Stablest / Standard Simplex inequality for correlations in [-1/2,2/5] and the S^{k-1}-valued Borell inequality for the correlations used in the reductions. The extremizing functions are, respectively, three 120-degree sectors in R^2 and the normalized radial map f(x)=x/|x|.

What carries the argument

The proof hinges on two families of Gaussian noise-stability inequalities. For Quantum MAX-CUT, the key object is the operator A_eta^(k) on the radial Laguerre space; the claim that its norm is < 1 (certified via a slightly larger explicit operator V_eta^(k) and a 20x20 finite block with Collatz–Wielandt plus a tail bound) is what makes the vector-valued Borell inequality hold. For MAX-3-CUT, the proof uses a joint arc inequality for three arcs on the circle, sharpened by the first angular Fourier mode, and then integrates over radii to form an integral operator K*. The required bounds are Hilbert–Schmidt norms h_lower < 2 and h_upper < 2, again certified by numerical integration with analyt

Load-bearing premise

The paper's main theorems rest on the correctness of four computer certification programs whose outputs are logged but whose code is not included in the manuscript; the most fragile certificate has a margin of only about 1.8e-4 against the required bound 2, so a small numerical bug in that certificate would invalidate the positive-correlation Standard Simplex inequality (and with it the MAX-2-LIN(3) hardness), while the negative-correlation and quantum certificates have more

What would settle it

Independently recompute the Hilbert–Schmidt bound h_+(rho) at rho≈0.3875, the worst case in the paper's log, using higher-precision arithmetic; if the value exceeds 2, the positive-correlation Standard Simplex inequality is false. Alternatively, search numerically for a partition of R^2 into three equal-measure Gaussian sets whose noise stability at rho=2/5 exceeds that of three 120-degree sectors; any such partition would refute Theorem A.1.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If the Unique Games Conjecture holds, the Frieze–Jerrum SDP gives the optimal polynomial-time approximation ratio for MAX-3-CUT, and the BOV algorithm is optimal for product-state Quantum MAX-CUT.
  • The proved S^{k-1}-valued Borell inequality yields sharp UGC-hardness for rank-k MAX-CUT for every k≥3, not only the k=3 quantum case.
  • The positive-correlation part of the three-candidate Plurality-is-Stablest theorem gives a conditional hardness factor of about 0.8157 for MAX-2-LIN(3), the best known for that problem.
  • Since the optimal quantum correlation rho_BOV,3≈-0.5843 falls inside the proved range [-0.5843, 0.5843], no further analytic work is needed for the quantum hardness.

Where Pith is reading between the lines

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

  • If the Unique Games Conjecture is ever proven, these hardness results become unconditional; the numerical certificates would not need to be changed.
  • The finite-block-plus-tail certification method is a template that could be applied to other Gaussian variational problems, such as the four-set Standard Simplex problem, whose main obstruction is currently the lack of a rearrangement lemma on the sphere.
  • An independent re-implementation of the four certification programs—especially the tight positive-correlation certificate, whose margin against the required 2 is only about 1.8e-4—would be a low-cost way to de-risk the paper's conclusions.
  • Extending the positive-correlation range of the Plurality-is-Stablest theorem beyond 2/5 to roughly 0.615 would immediately improve the MAX-2-LIN(3) hardness factor beyond the value reported here.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proves, under the Unique Games Conjecture, sharp inapproximability results for MAX-3-CUT (factor α_3 ≈ 0.83600811464) and for product-state and general Quantum MAX-CUT (factor α_BOV ≈ 0.9563372685). These hardness results are derived from two new extremal Gaussian inequalities: the three-set Standard Simplex / Plurality-is-Stablest inequality for correlations in [−1/2, 2/5], and the S^{k−1}-valued Borell inequality for correlations in [−0.5843, 0.5843] (k=3) and [−3/5, 3/5] (k>3). The proofs combine radial averaging, Laguerre-basis decompositions, rank-one corrections, and finite-dimensional spectral certificates verified by interval arithmetic. The bulk of the analytic argument is presented in the paper; the decisive numerical bounds are delegated to four Python programs and their printed output.

Significance. If the results are correct, they resolve the 2004 Khot–Kindler–Mossel–O'Donnell conjecture on three-candidate Plurality-is-Stablest in the stated correlation range, prove the conjectured S^{k−1}-valued Borell inequality of Hwang–Neeman–Parekh–Thompson–Wright, and establish that the Frieze–Jerrum and Briet–de Oliveira Filho–Vallentin algorithms are exactly optimal under UGC. These would be major advances in hardness of approximation and Gaussian analysis. The analytic structure is coherent and many spot-checks pass: the stochastic-dominance argument in Lemma 3.3, the centering identities in Lemma 9.1, and the Collatz–Wielandt reduction are internally consistent. The paper also gives exact rational test vectors, analytic tail bounds, and unusually detailed descriptions of the interval-arithmetic certificates, which is commendable. The main risk is not the analytic derivation but the reliance on un-reproduced, AI-generated numerical certificates with small margins.

major comments (4)
  1. [Lemma 9.3 and §1.5] The headline MAX-3-CUT hardness (Theorem 1.4) depends on the certified bound h_upper < 2 in Lemma 9.3. The reported value is h_upper ≈ 1.9656, only about 1.7% below the required threshold. The certificate is produced by plur_cert.py, which is not reproduced in the paper; the GitHub link in §1.5 has no commit hash, and the acknowledgements state the certificates were generated by ChatGPT 5.6. A small enclosure bug or a misimplemented kernel formula could push the value above 2 and invalidate Theorem 1.4. Since this is load-bearing, the paper should include the exact code with a commit hash, and ideally an independent re-certification using a different interval library or a second implementation.
  2. [Propositions 4.1 and 4.3] The Quantum MAX-CUT hardness (Theorem 1.7) relies on Propositions 4.1 and 4.3, which certify ∥A_η∥ < 0.987 (k=3) and < 0.989 (k≥4) with margins of roughly 1.3%. These are verified by certify_quantum_cut.py and certify_rank_k_cut.py, again not reproduced. The paper gives the test vectors and the directed row ratios, but not the full interval-arithmetic code. The proof is valid only if those programs are correct. This is the same class of concern as in Lemma 9.3, but it affects the second set of headline theorems.
  3. [Lemma A.4 and Theorem A.1] The positive-correlation Standard Simplex result (Theorem 1.2 for 0<ρ≤2/5) and the MAX-2-LIN(3) bound (Theorem 1.5) depend on Lemma A.4, where the certified value is h_+ < 1.99982273367, a margin of only about 1.8×10^{-4} below the required 2. The certification output reports 90 accepted slabs out of 150 attempts, with the worst finite slab at [0.38625, 0.3875], indicating the computation is very close to the threshold. A tiny enclosure bug would break Theorem A.1 and hence the full statement of Theorem 1.2. Even though this certificate is not needed for the negative-correlation MAX-3-CUT hardness, it is needed for a stated main theorem, so it must be independently verifiable.
  4. [Overall proof architecture] Four numerical certificates are treated as axioms: the printed outputs of certify_quantum_cut.py, certify_rank_k_cut.py, plur_cert.py, and plur_cert_positive.py. No proof of correctness of these programs is included, nor are the programs themselves. In a proof-oriented manuscript, this is insufficient for the load-bearing steps. I recommend requiring the source code be submitted as supplementary material, with a precise list of dependencies, a commit hash, and an independent check (e.g., a second implementation using a different interval-arithmetic backend) for at least the two most critical certificates (Lemma 9.3 and Proposition 4.1).
minor comments (5)
  1. [Abstract and §1.1] The abstract and the historical discussion refer to the Frieze–Jerrum algorithm as '1995' and '1997' in different places. Please standardize to 1997.
  2. [Lemma 3.3] The displayed density ratio f_B(t)/f_H(t) omits the constant factor that is stated to be 1 from the choice of θ_k. The formula as printed cannot be literally correct without that constant; please include it or state that it is absorbed.
  3. [§9.1] The rank-one correction (u_* ⊗ u_*)/C_* is not an orthogonal projection; the text acknowledges this but it would help to say explicitly that C_* = ⟨1,u_*⟩ is chosen to make R_*1=0, not to make the correction a projection.
  4. [§1.5] The GitHub link gives no commit hash or file listing. The paper says 'Associated codes appear at the following GitHub link'; for reproducibility, please include a specific commit hash and note the versions of the dependencies used (e.g., Arb, Python version).
  5. [Lemma 9.3 text] The sentence 'The identity C_*^{-1} = ... is used instead of integrating C_* directly' is mathematically confusing: C_* is a number, so C_*^{-1} is its reciprocal; the displayed identity is for 1/C_*. Please rephrase.

Circularity Check

0 steps flagged

No circular derivation: the main inequalities are proved directly, and the numerical certificates are external evidence rather than recycled assumptions; code reproducibility is a risk, not circularity.

full rationale

The paper's central content is a direct analytic proof of the Standard Simplex/Plurality-is-Stablest inequality (Theorem 1.2) and the S^{k-1}-valued Borell inequality (Theorem 1.6). These are derived from the definition of noise stability via a radial/spherical decomposition, exact Fourier–Bessel identities, and operator-norm bounds (e.g., Propositions 3.5, 4.5, and Section 9). The correlation ranges [-1/2,2/5] and [-.5843,.5843] are proved for the whole stated interval, not merely at the application values, and the numerical test vectors in Propositions 4.1 and 4.3 are certified a posteriori by exact rational interval arithmetic and Collatz–Wielandt; the bounds hold regardless of how the vectors were obtained. Lemma 9.3 and Lemma A.4 rely on external programs (plur_cert.py, plur_cert_positive.py, certify_quantum_cut.py, certify_rank_k_cut.py), and the acknowledgments state that ChatGPT 5.6 produced the spectral certificates. This is a reproducibility/correctness risk—the margins in Lemma A.4 are thin and the programs are not reproduced—but it is not circularity: the certificates are being used as evidence for inequalities, not as assumptions equivalent to the theorems. The reductions to hardness are imported from prior work ([IM12], [HNP+23], [KKMO07]), and some dimension-reduction steps cite the author's own prior work ([Hei22], [HT21]). These are load-bearing but independent, stated as theorems with their own assumptions; the present paper does not define its target constants in terms of those theorems. No step was found where a defined quantity is identical to a predicted quantity by construction, or where a fitted parameter is renamed as a prediction. The legitimate concern about un-reproduced numerical certificates belongs under correctness/verification risk, not under circularity.

Axiom & Free-Parameter Ledger

3 free parameters · 7 axioms · 0 invented entities

No new physical or mathematical entities are introduced: S^{k-1}-valued maps, the standard simplex partition, and the Laguerre/Ornstein-Uhlenbeck machinery are previously studied objects. The load-bearing assumptions are: (i) UGC; (ii) a chain of reduction/dimension theorems, several from the author's own prior work; (iii) correctness of un-pinned external certificate code; and (iv) standard rearrangement inequalities. Free parameters are limited to certificate choices (test vectors, centering polynomial) that are validated a posteriori, plus correlation endpoints chosen to cover the application values.

free parameters (3)
  • Collatz-Wielandt test vectors v (20 entries; one per certified block) = e.g. 1.0, 0.256858556823, 0.097396033098, ... in Proposition 4.1
    Chosen numerically to drive the ratio (Vv)_i/v_i below the stated bounds. The final bounds are verified by exact rational interval arithmetic, so these are proof certificates rather than fitted constants; listed for completeness.
  • Additive-centering polynomial ell_rho, coefficient matrix C (4x4 of decimals) = Matrix (150) in Appendix A
    Specifies an additive center for the positive-correlation kernel; the paper explicitly says no approximation property is assumed. It affects the numerical value of h_+^2 but is validated a posteriori by the certificate.
  • Correlation-range endpoints (0.5843, 3/5, 2/5, 1/2) = Given in Theorems 1.2/1.6/2.1/2.2/A.1
    Chosen to contain the application values rho_BOV,3 = -0.58426766... and rho = -1/2. The inequalities are certified on the whole stated ranges, so this is target coverage, not data fitting.
axioms (7)
  • domain assumption Unique Games Conjecture
    All hardness theorems (1.4, 1.5, 1.7, 1.8, Cor. 1.9) are conditional on UGC; stated in the abstract and Section 1.
  • domain assumption Standard Simplex Conjecture is equivalent to Plurality is Stablest [IM12, Theorem 1.10]
    Used to bridge Theorem 1.2 to Theorem 1.3 and hence to MAX-3-CUT hardness; imported as a black box (Section 1.1).
  • domain assumption Dimension reduction for S^{k-1}-valued maximizers: dependence on <= k coordinates [HNP+23, Theorem 6.1]
    Used in Proposition 3.5 to pass from R^k to R^n maps in Theorem 2.2.
  • domain assumption Dimension reduction for three-set partitions to R^2 [HT21], refined by [Hei22, Lemma 7.3 and Theorem 7.9]
    Reduces the Standard Simplex problem to planar partitions and to equal-measure pairs (Section 7, proof of Theorem 7.1).
  • domain assumption Hardness reductions from noise stability to UGC hardness [HNP+23, Theorem 11.3 and Theorem C.4]
    Converts Theorems 2.1/2.2 into Theorems 1.7/1.8; the product-state-to-full Quantum MAX-CUT passage is [HNP+23, Theorem 11.3].
  • standard math Circular Riesz rearrangement inequality [BT76, Theorem 2]
    Restricts angular optimizers to circular arcs (Sections 7 and 8.1); stated as a known theorem.
  • ad hoc to paper Correctness of the four certificate programs (certify_quantum_cut.py, certify_rank_k_cut.py, plur_cert.py, plur_cert_positive.py) and their printed outputs
    Lemmas 9.3 and A.4 and Propositions 4.1/4.3 delegate the decisive inequalities to external interval-arithmetic code; no commit hash and the code is not reproduced in the paper.

pith-pipeline@v1.3.0-alltime-deepseek · 40305 in / 23698 out tokens · 196342 ms · 2026-08-04T00:43:07.995978+00:00 · methodology

0 comments
read the original abstract

Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of $\alpha_3+\epsilon$ for every $\epsilon>0$, where $\alpha_3\approx.83600811464$ is the approximation ratio of Frieze-Jerrum's polynomial-time algorithm from 1995. That is, we prove sharp hardness of approximation for MAX-3-CUT. This result resolves a conjecture of Khot-Kindler-Mossel-O'Donnell from 2004 by proving the three candidate Plurality is Stablest Conjecture for correlations in $[-1/2,2/5]$ and generalizes the Majority is Stablest Theorem of Mossel-O'Donnell-Oleszkiewicz [Annals of Math, 2010]. With a similar strategy we prove: assuming the Unique Games Conjecture, it is NP-hard to approximate the product-state value of Quantum MAX-CUT within a multiplicative factor of $\alpha_{\rm BOV}+\epsilon$ for every $\epsilon>0$, where $\alpha_{\rm BOV}\approx 0.9563372685$ is the approximation ratio of the Bri\"et-de Oliveira Filho-Vallentin algorithm. This sharp hardness result completes the conjectured hardness of Hwang-Neeman-Parekh-Thompson-Wright from 2021 by proving their $S^{k-1}$-valued Borell inequality for correlations in $[-.5843,.5843]$ for all $k\geq3$.

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

57 extracted references · 5 linked inside Pith

  1. [1]

    The Quantum PCP conjecture

    Dorit Aharonov, Itai Arad, and Thomas Vidick. The Quantum PCP conjecture. ACM SIGACT News (2013), 44 (2) pp. 47--79

    2013

  2. [2]

    Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

    Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings. Preprint (2025), arXiv:2504.15276 https://arxiv.org/abs/2504.15276

    Pith/arXiv arXiv 2025

  3. [3]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (1998). 45 (3), pp. 501--555

    1998

  4. [4]

    Probabilistic checking of proofs: a new characterization of NP

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM (1998). 45 (1), pp. 70--122

    1998

  5. [5]

    New NP-hardness results for 3-Coloring and 2-to-1 Label Cover

    Per Austrin, Ryan O'Donnell, Li Yang Tan, and John Wright. New NP-hardness results for 3-Coloring and 2-to-1 Label Cover. ACM Transactions on Computation Theory (2014). 6 (1), pp. 2:1--2:20

    2014

  6. [6]

    Alan Taylor, Spherical rearrangements, subharmonic functions, and -functions in n -space, Duke Mathematical Journal (1976)

    Alfred Baernstein II and B. Alan Taylor, Spherical rearrangements, subharmonic functions, and -functions in n -space, Duke Mathematical Journal (1976). 43 (2), pp. 245--268

    1976

  7. [7]

    Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut

    Ainesh Bakshi, Arpon Basu, Pravesh Kothari, and Anqi Li. Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut. Preprint (2026), arXiv:2605.14994 https://arxiv.org/abs/2605.14994

    Pith/arXiv arXiv 2026

  8. [8]

    Free Bits, PCPs, and Nonapproximability---Towards Tight Results

    Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs, and Nonapproximability---Towards Tight Results. SIAM Journal on Computing (1998). 27 (3), pp. 804--915

    1998

  9. [9]

    Derandomised tensor product gap amplification for quantum Hamiltonians

    Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang. Derandomised tensor product gap amplification for quantum Hamiltonians. Preprint (2025), arXiv:2510.01333 https://arxiv.org/abs/2510.01333

    arXiv 2025

  10. [10]

    An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space

    Sergei Bobkov. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space. Annals of Probability (1997). 25 (1), pp. 206--214

    1997

  11. [11]

    Geometric bounds on the Ornstein-Uhlenbeck velocity process

    Christer Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Probability Theory and Related Fields (1985). 70 (1), pp. 1--13

    1985

  12. [12]

    Tight approximability of MAX 2-SAT and relatives, under UGC

    Joshua Brakensiek, Neng Huang, and Uri Zwick. Tight approximability of MAX 2-SAT and relatives, under UGC. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (2024). pp. 1328--1344

    2024

  13. [13]

    Grothendieck inequalities for semidefinite programs with rank constraint

    Jop Bri\"et, Fernando M\'ario de Oliveira Filho, and Frank Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Theory of Computing (2014). 10, pp. 77--105

    2014

  14. [14]

    Comparison theorems for exit times

    Almut Burchard and Michael Schmuckenschl\" a ger. Comparison theorems for exit times. Geometric & Functional Analysis (2001). 11 (4), pp. 651--692

    2001

  15. [15]

    Approximation Algorithms for Quantum Max-d-Cut

    Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, and Stuart Wayland. Approximation Algorithms for Quantum Max-d-Cut. Preprint (2023), arXiv:2309.10957 https://arxiv.org/abs/2309.10957

    Pith/arXiv arXiv 2023

  16. [16]

    A generalization of the Lindeberg principle

    Sourav Chatterjee. A generalization of the Lindeberg principle. Annals of Probability (2006). 34 (6), pp. 2061--2076

    2006

  17. [17]

    On Weighted vs Unweighted Versions of Combinatorial Optimization Problems

    Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan. On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. Information and Computation (2001). 167 (1), pp. 10--26

    2001

  18. [18]

    Complexity classification of local Hamiltonian problems

    Toby Cubitt and Ashley Montanaro. Complexity classification of local Hamiltonian problems. SIAM Journal on Computing (2016). 45 (2), pp. 268--316

    2016

  19. [19]

    Analytical approach to parallel repetition

    Irit Dinur and David Steurer. Analytical approach to parallel repetition. ACM symposium on Theory of computing (2014). pp. 624--633

    2014

  20. [20]

    A two-sided estimate for the gaussian noise stability deficit

    Ronen Eldan. A two-sided estimate for the gaussian noise stability deficit. Inventiones mathematicae (2015). 201 (2), pp. 561--624

    2015

  21. [21]

    A threshold of n for approximating set cover

    Uriel Feige. A threshold of n for approximating set cover. Journal of the ACM (1998). 45 (4), pp. 634--652

    1998

  22. [22]

    On the optimality of the random hyperplane rounding technique for MAX CUT

    Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures & Algorithms (2002). 20 (3), pp. 403--440

    2002

  23. [23]

    Algorithmica (1997)

    Alan Frieze and Mark Jerrum, Improved approximation algorithms for MAX k -CUT and MAX BISECTION. Algorithmica (1997). 18, pp. 67--81

    1997

  24. [24]

    Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

    Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2019)

    2019

  25. [25]

    Goemans and David P

    Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (1995). 42 (6), pp. 1115--1145

    1995

  26. [26]

    Improved inapproximability results for Maximum k -Colorable Subgraph

    Venkatesan Guruswami and Ali Kemal Sinop. Improved inapproximability results for Maximum k -Colorable Subgraph. Theory of Computing (2013). 9 (11), pp. 413--435

    2013

  27. [27]

    Some optimal inapproximability results

    Johan H stad. Some optimal inapproximability results. Journal of the ACM (2001). 48 (4), pp. 798--859

    2001

  28. [28]

    Steven Heilman, Hyperstable Sets with Voting and Algorithmic Hardness Applications, Preprint (2022), arXiv:2209.11216 https://arxiv.org/abs/2209.11216

    Pith/arXiv arXiv 2022

  29. [29]

    Steven Heilman, Three Candidate Plurality is Stablest for Correlations at most 1/10 , Preprint (2023), arXiv:2306.03312 https://arxiv.org/abs/2306.03312

    Pith/arXiv arXiv 2023

  30. [30]

    Sphere valued noise stability and quantum MAX-CUT hardness

    Steven Heilman. Sphere valued noise stability and quantum MAX-CUT hardness. Annals of Probability (2025). 53 (4), pp. 1197--1222

    2025

  31. [31]

    Standard simplices and pluralities are not the most noise stable

    Steven Heilman, Elchanan Mossel, and Joe Neeman. Standard simplices and pluralities are not the most noise stable. Israel Journal of Mathematics, (2016). 213 (1), pp. 33--53

    2016

  32. [32]

    Three candidate plurality is stablest for small correlations, Forum of Mathematics, Sigma (2021)

    Steven Heilman and Alex Tarter. Three candidate plurality is stablest for small correlations, Forum of Mathematics, Sigma (2021). 9, e65

    2021

  33. [33]

    Zur Theorie des Ferromagnetismus

    Werner Heisenberg. Zur Theorie des Ferromagnetismus. Zeitschrift f\" u r Physik (1928). 49 (9--10), pp. 619--636

    1928

  34. [34]

    Hochbaum, David B

    Dorit S. Hochbaum, David B. Shmoys. A Best Possible Heuristic for the k-Center Problem. Mathematics of Operations Research (1985). 10 (2), pp. 180--184

    1985

  35. [35]

    Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality

    Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality. In Proceedings of the Annual ACM--SIAM Symposium on Discrete Algorithms (2023). pp. 1319--1384

    2023

  36. [36]

    Marcus Isaksson and Elchanan Mossel, Maximally stable Gaussian partitions with discrete applications, Israel Journal of Mathematics (2012). 189, pp. 347--396

    2012

  37. [37]

    On the hardness of approximating MAX k -CUT and its dual

    Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi. On the hardness of approximating MAX k -CUT and its dual. Chicago Journal of Theoretical Computer Science (1997). 2, pp. 1--18

    1997

  38. [38]

    Richard M. Karp. Reducibility among Combinatorial Problems. Symposium on Complexity of Computer Computations (1972). pp. 85--103

    1972

  39. [39]

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

    Subhash Khot. On the power of unique 2-prover 1-round games. Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (2002). pp. 767--775

    2002

  40. [40]

    37 (1), pp

    Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell, Optimal inapproximability results for MAX-CUT and other 2 -variable CSPs?, SIAM Journal on Computing (2007). 37 (1), pp. 319--357

    2007

  41. [41]

    Vertex cover might be hard to approximate to within 2-

    Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2- . Journal of Computer and System Sciences (2008). 74 (3), pp. 335--349

    2008

  42. [42]

    On the unique games conjecture

    Subhash Khot. On the unique games conjecture. A nnual IEEE C onference on C omputational C omplexity (2010). pp. 99--121

    2010

  43. [43]

    Sharp kernel clustering algorithms and their associated Grothendieck inequalities

    Subhash Khot and Assaf Naor. Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Random Structures and Algorithms (2013). 42 (3), pp. 269--300

    2013

  44. [44]

    Pseudorandom sets in Grassmann graph have near-perfect expansion

    Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in Grassmann graph have near-perfect expansion. Annals of Mathematics (2023). 198 (1), pp. 1--92

    2023

  45. [45]

    Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space

    Michel Ledoux. Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space. Bull. Sci. Math. (1994). 118 (6), pp. 485--510

    1994

  46. [46]

    Robust optimality of Gaussian noise stability

    Elchanan Mossel and Joe Neeman. Robust optimality of Gaussian noise stability. Journal of the European Mathematics Society (2015). 17 (2), pp. 433--482

    2015

  47. [47]

    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 (2010). 171 (1), pp. 295--341

    2010

  48. [48]

    Reinforced generation of combinatorial structures: Hardness of approximation

    Ansh Nagda, Prabhakar Raghavan, and Abhradeep Thakurta. Reinforced generation of combinatorial structures: Hardness of approximation. Preprint (2025), arXiv:2509.18057 https://arxiv.org/abs/2509.18057

    arXiv 2025

  49. [49]

    F. W. J. Olver (Editor in Chief), D. W. Lozier, R. F. Boisvert, and C. W. Clark. NIST Handbook of Mathematical Functions, Cambridge University Press (2010), New York

    2010

  50. [50]

    Optimization, approximation, and complexity classes

    Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computing and System Sciences (1991). 43, pp. 425--440

    1991

  51. [51]

    The complexity of antiferromagnetic interactions and 2D lattices

    Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2D lattices. Quantum Information and Computation (2017). 17 (7-8), pp. 636--672

    2017

  52. [52]

    Quantum Max-Cut is NP hard to approximate

    Stephen Piddock. Quantum Max-Cut is NP hard to approximate. Preprint (2025), arXiv:2510.07995 https://arxiv.org/abs/2510.07995

    arXiv 2025

  53. [53]

    Optimal algorithms and inapproximability results for every CSP?

    Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP?. Proceedings of the annual ACM symposium on Theory of computing (2008). pp. 245--254

    2008

  54. [54]

    Towards Computing the Grothendieck Constant

    Prasad Raghavendra and David Steurer. Towards Computing the Grothendieck Constant. Symposium on Discrete Algorithms (2009). pp. 525--534

    2009

  55. [55]

    V. I. Rotar'. Limit theorems for polylinear forms. Journal of Multivariate Analysis. 9 (4), pp. 511--530, 1979

    1979

  56. [56]

    P-complete approximation problems

    Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM (1976). 23, pp. 555--565

    1976

  57. [57]

    Sorkin, Madhu Sudan, and David P

    Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing (2000). 29 (6), pp. 2074--2097

    2000