Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP

Yury Makarychev

REVIEW 2 major objections 3 minor 18 references

Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP

T0 review · 2 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read The paper proves that Gaussian rounding for Boolean Max k-CSP achieves a (1-O(log k/k))k/2^k approximation, asymptotically matching known hardness results.

desk verdict A short, clean proof of the conjectured optimal ratio for Boolean Max k-CSP, but the entire result rests on an unverified external theorem. read the letter →

arxiv 2608.07800 v1 pith:ZWJXIWAL submitted 2026-08-07 cs.DS

Yury Makarychev This is my paper · ORCID

classification cs.DS MSC 68W2568Q1790C22

keywords BooleanMaxk-CSPapproximationalgorithmGaussianroundingSDPrelaxationstochasticdominationUniqueGamesConjecturehardnessofrandomassignment

topics P versus NP

open problems P versus NP

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 proves that the Gaussian rounding algorithm for Boolean Max k-CSP, previously known to achieve a constant fraction of k/2^k, actually achieves the asymptotically optimal approximation factor (1 - O(log k/k)) k/2^k. This settles a conjecture from 2017. Because hardness results say no efficient algorithm can beat (1+o(1))k/2^k under the Unique Games Conjecture, the guarantee is the best possible up to lower-order terms. The proof is short and rests on a stochastic domination inequality for correlated Gaussian vectors.

What carries the argument

The central object is Mulgund's stochastic domination theorem: if R is a k-by-k correlation matrix with R - (1/k)J positive semidefinite, then for X ~ N(0,R) and every real t, Pr(X_u <= t for all u) >= F(t)^k, where F is the standard Gaussian CDF. The paper applies this to the Gram matrix Sigma of the SDP vectors for a clause, decomposing Sigma = $\theta$ R + (1-$\theta$) J so that the theorem applies after conditioning on a common Gaussian component. This yields the key estimate Pr(clause satisfied) >= integral of F(c x)^k d gamma(x), where $c^{2}$ = ($beta^{2}$ - 1)/(k - $beta^{2}$) and $\beta$ = $\sqrt$(k ||z_C||^2). The analysis then chooses the threshold $beta_k^{2}$/k = 1 + 4 pi log k / k to make the integral at least $k^{2}$/2^k for all sufficiently large k.

What would settle it

Find a k-by-k correlation matrix R with R - (1/k)J positive semidefinite and a real t such that Pr(X_u <= t for all u) < F(t)^k with X ~ N(0,R); a direct counterexample would disprove the key estimate (2). Alternatively, construct an explicit SDP solution for a small Boolean Max k-CSP instance where the claimed clause-satisfaction probability integral fails, thereby violating Theorem 2.

Watch

Extended reading notes

Core claim

The paper shows that the Gaussian rounding algorithm of Makarychev and Makarychev, when combined with random assignment, satisfies every clause with probability at least alpha_k (k/2^k) ||z_C||^2, where alpha_k = 1 - O(log k/k). Summing over clauses and using the SDP upper bound on OPT gives the approximation guarantee (1 - O(log k/k)) k/2^k. This matches, asymptotically, the hardness results of Austrin–Mossel, De–Mossel, and Chan, which rule out approximations better than (1+o(1))k/2^k under UGC (and, for infinitely many k, unconditionally assuming P != NP).

Load-bearing premise

The argument rests entirely on Mulgund's stochastic domination theorem, which is quoted from a concurrent preprint and used as a black box; if that inequality fails for any correlation matrix satisfying the stated condition, the central approximation guarantee collapses.

Editorial extensions

If this is right

The approximation guarantee becomes (1-o(1))k/2^k, asymptotically matching the hardness lower bounds under the Unique Games Conjecture.
For values of k of the form 2^r - 1, Chan's unconditional hardness shows the approximation constant is optimal under P != NP.
The proof confirms the 2017 conjecture that the earlier algorithm has a much tighter guarantee than the published constant 0.626612.
The algorithm itself is unchanged; the improvement comes entirely from a sharper probabilistic analysis of the Gaussian rounding step.
The lower-order term O(log k/k) is explicitly tied to the threshold at ||z_C||^2 = 1 + 4 pi log k / k, so any sharper bound there would directly improve the guarantee.

Reading between the lines

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

If Mulgund's stochastic domination theorem holds in greater generality, the same decomposition trick could sharpen analyses of other rounding schemes that split SDP vectors into common and residual components, potentially for non-Boolean CSPs.
The proof is conditional on a concurrent unpublished theorem; a careful independent verification of that theorem would remove the main non-black-box risk in the argument.
A direct numerical test of the stochastic domination inequality for small k with random correlation matrices could provide empirical confidence or a counterexample before the full proof is vetted.
The sharp threshold suggests that the clauses that limit the approximation are those with SDP value near 1/k; a tighter analysis of exactly those clauses would be the natural route to improving the O(log k/k) term.

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

The paper does exactly what it says: it takes Makarychev and Makarychev's Gaussian rounding scheme and shows, via Mulgund's stochastic domination theorem, that it achieves (1-o(1)) k/2^k approximation, matching known UGC-hardness. That settles a conjecture from the authors' own survey, and the analysis is a neat piece of work. The Gram matrix decomposition, the reduction to a one-dimensional integral, and the asymptotic estimate in Claim 1 are all careful and I had no trouble following them. The paper is transparent that the only new ingredient is Mulgund's theorem, used as a black box, and that the result is essentially a corollary of [9]. That honesty is welcome.

The soft spot is exactly that dependence. Theorem 1 of Mulgund is nontrivial and comes from a concurrent, unpublished preprint. If it is false or the hypotheses are not met, the key estimate (2) fails and Theorem 2 collapses. This is not a flaw in the paper's internal logic, but it makes the contribution conditional on an external result that the present paper does not prove or independently verify. A referee would need to examine [9] seriously. I would not accept this paper without that verification.

There is also a typesetting error in Claim 1. As printed, it sets β^2/k = 1 + 4π log k/k, which is greater than 1, so the condition ∥z_C∥^2 ≥ β^2/k is impossible for feasible SDP solutions. The following calculation of c_k^2 makes clear the intended threshold is β_k^2 = 1 + 4π log k/k, and the condition is ∥z_C∥^2 ≥ β_k^2/k. This is a minor fix, but as written the proof of the rounding case is vacuous.

Overall, the paper is a good, short note for the approximation-algorithms and CSP community. It shows clear thinking, and the internal math is sound given the black box. I would bring it to a reading group to discuss the application of Mulgund's theorem and the feasibility of the threshold. I would likely cite it once the external theorem is either proved or verified, because settling this conjecture is significant. The paper deserves serious peer review rather than desk rejection. The recommendation is conditional: send it to referees, ask them to check Mulgund's theorem and the Claim 1 fix, and decide accordingly.

Referee Report

2 major / 3 minor

Summary. The paper claims to settle the conjecture that the Makarychev--Makarychev Gaussian rounding algorithm for Boolean Max k-CSP achieves a (1 - O(log k/k)) k/2^k approximation, which asymptotically matches the known Unique Games hardness bounds. The argument reuses the SDP relaxation and rounding from [7] and derives the improved clause-satisfaction bound from Mulgund's Gaussian stochastic domination theorem, used as a black box. The paper is short: after reducing to conjunctions of literals, it decomposes the Gram matrix of the clause vectors, applies the theorem to obtain the key estimate (2), verifies the threshold via an asymptotic computation in Claim 1, and combines rounded and random assignments in Theorem 2.

Significance. If correct, the result is significant: it improves the previous 0.626612 k/2^k approximation for Boolean Max k-CSP to the asymptotically optimal (1-o(1)) k/2^k, matching hardness results under the Unique Games Conjecture and, for an infinite sequence of k, unconditional hardness. The proof is elegant and transparent: the matrix decomposition in Section 3 and the asymptotic estimate in Claim 1 are clean and internally consistent, apart from the threshold typo noted below. The paper is fully honest that its main result is a corollary of Mulgund's theorem, and it does not attempt to hide that dependence. However, that dependence on an unverified concurrent preprint is the central weakness and must be resolved before the paper can be evaluated as a complete proof.

major comments (2)

[Section 2, Theorem 1; Section 3, Eq. (2)] The central estimate (2) is obtained by applying Mulgund's Theorem 1 as a black box, and Theorem 1 is quoted from a concurrent, unpublished preprint [9] rather than proved or independently verified here. Since Claim 1 and Theorem 2 both depend directly on (2), the paper's main claim is conditional on the correctness and applicability of an unrefereed external theorem. The author should either include a self-contained proof of Theorem 1 (or of the special case needed here) or explicitly publish the result as conditional on [9]. As written, the proof is not self-contained, and a referee cannot certify the central claim without access to a verified proof of the domination theorem.
[Section 3, Claim 1] The threshold in Claim 1 is infeasible as printed. The text defines $\beta_k^2/k = 1 + 4\pi \log k/k$, so $\beta_k^2/k > 1$, but every feasible SDP solution satisfies $\|z_C\|^2 \le 1$ by Cauchy-Schwarz applied to $\langle u_i, z_C\rangle = \|z_C\|^2$ with $\|u_i\| \le 1$. Hence the condition $\|z_C\|^2 \ge \beta_k^2/k$ can never hold, and the rounding-case proof is vacuous. The subsequent computation $c_k^2 = (4\pi+o(1))\log k/k^2$ indicates that the intended definition is $\beta_k^2 = 1 + 4\pi \log k/k$. This must be corrected, and the proof re-verified with the corrected threshold.

minor comments (3)

[Section 2, SDP constraints] The condition $\langle u_j, z_C\rangle = 0$ if $(u,i)\in C, j\ne i$ is unambiguous but slightly terse; writing $j \ne i$ for the same variable $u$ would help avoid confusion.
[Section 3, Claim 1 proof] The asymptotic expansion $\log(2F(t)) = a t + O(t^2)$ as $t\to 0$ is standard and correct, but a one-line derivation or reference would improve readability.
[Section 3, Claim 1 proof] The sentence 'The case $\|z_C\|=1$ is immediate' could be expanded: in that case $v_u = z_C$ for all $u$, so the clause is satisfied with probability $1/2$, which is at least $k^2/2^k$ for all sufficiently large $k$.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new result is derived as a corollary of an external Gaussian stochastic domination theorem, and the self-citations to prior work are contextual rather than load-bearing.

full rationale

The derivation chain is linear: Section 2 fixes the SDP relaxation and Gaussian rounding; Section 3 derives the Gram-matrix decomposition Σ = sJ + (1-s)G, rewrites it as Σ = θR + (1-θ)J, and obtains the key estimate (2) by applying Mulgund's Theorem 1 to the correlation matrix R = ((k-1)/k)G + (1/k)J. Claim 1 then estimates the integral in (2), and Theorem 2 sums the per-clause probabilities over the SDP objective. Each step is a mathematical implication; none defines the target approximation ratio into its premises. The citations to the authors' own [7] and [8] are contextual: the SDP and rounding are defined in Section 2 rather than imported as a black box, and the conjecture in [8] is not used as a proof premise. The load-bearing external input is Theorem 1 from [9], an independent result by a different author, whose hypotheses (R is a correlation matrix and R - (1/k)J ⪰ 0) do not mention Max k-CSP or the SDP value. Thus no fitted parameter is renamed as a prediction and no self-citation chain forces the conclusion. The paper's explicit admission that it uses [9] 'as a black box' in Section 1 is an honest statement of verification risk, not circularity. Separately, Claim 1's printed threshold appears infeasible, since feasible SDP vectors satisfy ∥z_C∥² ≤ 1 while the condition ∥z_C∥² ≥ β_k²/k = 1 + 4π log k/k > 1 cannot hold; this is a correctness defect in the current text, not a circular step.

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

The paper introduces no new entities or fitted empirical parameters. The only hand-chosen quantity is the analytic threshold beta_k, which is a proof device. The main load-bearing assumption is Mulgund's theorem, which is external to this paper.

free parameters (1)

beta_k threshold = beta_k^2 = 1 + (4π log k)/k (as intended despite typo)
Chosen by hand in Claim 1 to make the Gaussian integral in equation (2) exceed k^2/2^k. It is a proof device, not an empirical fit.

assumptions (3)

domain assumption Mulgund's Gaussian stochastic domination theorem
Stated as Theorem 1 and used directly to derive the key estimate (2). No proof is included, and the theorem comes from an unreviewed concurrent preprint [9].
standard math SDP relaxation satisfies SDP >= OPT
Standard property of the SDP relaxation introduced in [7], stated without proof in Section 2.
standard math Gaussian tail expansion log(2F(t)) = a t + O(t^2)
Used in Claim 1's asymptotic lower bound; follows from the normal CDF and is standard.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP." pith.science (2026). https://pith.science/paper/ZWJXIWAL

@misc{pith2026260807800,
  author       = {Pith},
  title        = {Pith review of: Sharp Analysis of Gaussian Rounding for Boolean Max k-CSP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZWJXIWAL}},
  note         = {Machine review of arXiv:2608.07800}
}

abstract

In this note, we show that the approximation algorithm for Boolean Max $k$-CSP presented in [Makarychev and Makarychev 2014] yields a $(1-o_k(1))k/2^k$ approximation, as conjectured in [Makarychev and Makarychev 2017]. This improves the previous guarantee of $(0.626612-o_k(1))k/2^k$ from [Makarychev and Makarychev 2014] and asymptotically matches the known hardness results. The result is a short corollary of the Gaussian stochastic domination theorem of Mulgund.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

[9]

Approximation Resistant Predicates from Pairwise Independence

Per Austrin and Elchanan Mossel. Approximation Resistant Predicates from Pairwise Independence. 2009

work page 2009
[7]

More Efficient Queries in PCP s for NP and Improved Approximation Hardness of Maximum CSP

Lars Engebretsen and Jonas Holmerin. More Efficient Queries in PCP s for NP and Improved Approximation Hardness of Maximum CSP

work page
[1]

The Nonapproximability of Non-Boolean Predicates

Lars Engebretsen. The Nonapproximability of Non-Boolean Predicates. SIAM Journal on Discrete Mathematics. 2004. doi:10.1137/S0895480100380458 , publisher =

work page doi:10.1137/s0895480100380458 2004
[2]

A PCP characterization of NP with optimal amortized query complexity

Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. Proc. 32nd STOC. 2000

work page 2000
[3]

Near-optimal algorithms for unique games , year =

Moses Charikar and Konstantin Makarychev and Yury Makarychev , booktitle =. Near-optimal algorithms for unique games , year =

work page
[4]

Gowers uniformity, influence of variables, and PCP s

Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and PCP s. Proc. 38th STOC. 2006. doi:10.1145/1132516.1132519

arXiv 2006
[5]

2009 , doi =

Moses Charikar and Konstantin Makarychev and Yury Makarychev , title =. 2009 , doi =

work page 2009
[6]

Optimal algorithms and inapproximability results for every CSP ?

Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP ?

work page

Show all 18 references

[8]

Constraint Satisfaction over a Non- B oolean Domain: Approximation Algorithms and U nique- G ames Hardness

Venkatesan Guruswami and Prasad Raghavendra. Constraint Satisfaction over a Non- B oolean Domain: Approximation Algorithms and U nique- G ames Hardness
[10]

Approximating

Gustav Hast , booktitle = icalp, pages =. Approximating. 2005 , doi =

2005
[11]

Journal of the American Statistical Association

Rectangular Confidence Regions for the Means of Multivariate Normal Distributions , year =. Journal of the American Statistical Association. doi:10.2307/2283989 , url =

doi
[12]

Algorithmica

Trevisan, Luca , journal = "Algorithmica", volume =. Parallel Approximation Algorithms by Positive Linear Programming , year =
[13]

Journal of the ACM (JACM) , volume=

Approximation resistance from pairwise-independent subgroups , author=. Journal of the ACM (JACM) , volume=. 2016 , publisher=

2016
[14]

Theory of Computing , volume =

Konstantin Makarychev and Yury Makarychev , title =. Theory of Computing , volume =. 2014 , doi =

2014
[15]

The Constraint Satisfaction Problem: Complexity and Approximability , editor =

Konstantin Makarychev and Yury Makarychev , title =. The Constraint Satisfaction Problem: Complexity and Approximability , editor =. 2017 , publisher =. doi:10.4230/DFU.Vol7.15301.287 , url =

2017 doi
[16]

ACM Transactions on Computation Theory (TOCT) , volume=

Explicit Optimal hardness via Gaussian stability results , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2013 , publisher=

2013
[17]

CoRR , volume =

Abhijeet Mulgund , title =. CoRR , volume =. 2026 , note =

2026
[18]

CoRR , volume =

Ainesh Bakshi , title =. CoRR , volume =. 2026 , note =

2026

Pith tools

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

[1] [9]

Approximation Resistant Predicates from Pairwise Independence

Per Austrin and Elchanan Mossel. Approximation Resistant Predicates from Pairwise Independence. 2009

work page 2009

[2] [7]

More Efficient Queries in PCP s for NP and Improved Approximation Hardness of Maximum CSP

Lars Engebretsen and Jonas Holmerin. More Efficient Queries in PCP s for NP and Improved Approximation Hardness of Maximum CSP

work page

[3] [1]

The Nonapproximability of Non-Boolean Predicates

Lars Engebretsen. The Nonapproximability of Non-Boolean Predicates. SIAM Journal on Discrete Mathematics. 2004. doi:10.1137/S0895480100380458 , publisher =

work page doi:10.1137/s0895480100380458 2004

[4] [2]

A PCP characterization of NP with optimal amortized query complexity

Alex Samorodnitsky and Luca Trevisan. A PCP characterization of NP with optimal amortized query complexity. Proc. 32nd STOC. 2000

work page 2000

[5] [3]

Near-optimal algorithms for unique games , year =

Moses Charikar and Konstantin Makarychev and Yury Makarychev , booktitle =. Near-optimal algorithms for unique games , year =

work page

[6] [4]

Gowers uniformity, influence of variables, and PCP s

Alex Samorodnitsky and Luca Trevisan. Gowers uniformity, influence of variables, and PCP s. Proc. 38th STOC. 2006. doi:10.1145/1132516.1132519

arXiv 2006

[7] [5]

2009 , doi =

Moses Charikar and Konstantin Makarychev and Yury Makarychev , title =. 2009 , doi =

work page 2009

[8] [6]

Optimal algorithms and inapproximability results for every CSP ?

Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP ?

work page