{"id":"a26379ac-15df-43eb-b80b-d58f78820e83","arxiv_id":"2608.07800","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A Gaussian rounding algorithm for Boolean Max k-CSP is shown to achieve a (1 - o(1)) k/2^k approximation, matching known hardness bounds.","lead":"This paper proves that a known algorithmic approach for the Boolean Max k-CSP problem achieves the best possible approximation factor, settling a conjecture. The result shows the algorithm is asymptotically optimal, so it clarifies the boundary between what can and cannot be approximated efficiently for these constraint satisfaction problems.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim rests on an unproven black-box stochastic domination theorem; if it is false, the result collapses. Additionally, Claim 1's printed threshold is infeasible, so the current text needs correction before the proof is valid.","rationale":"The reader's weakest-assumption analysis correctly identifies Mulgund's Theorem 1 as the main unproven ingredient, and I agree that the paper's contribution is conditional on it. I partially disagree with the characterization of the Claim 1 issue as a minor typesetting ambiguity: the printed threshold β_k^2/k = 1 + 4π log k/k is not merely ambiguous but infeasible, since every feasible SDP solution has ∥z_C∥^2 ≤ 1. Taken literally, the rounding case in Theorem 2's proof can never fire, and the guarantee reduces to random assignment. The subsequent c_k^2 computation shows the intended threshold is β_k^2 = 1 + 4π log k/k, which is a plausible typo. If corrected, the proof still depends entirely on the black-box stochastic domination theorem. I therefore do not see a reason to change the conditional verdict, but the revision must include a self-contained proof or a citation to a verified proof of Theorem 1, and must fix the Claim 1 threshold. A numerical counterexample search for small k is a concrete way to test the theorem's validity; if no counterexample is found, the concern is reduced though not eliminated.","tokens_in":4066,"tokens_out":19635,"duration_ms":168942,"concrete_test":"Independently test Mulgund's Theorem 1 for k = 3, 4, 5 by numerical search: sample many correlation matrices R satisfying R - (1/k)J ⪰ 0, evaluate the Gaussian orthant probability Pr(X_1,...,X_k ≤ t) by high-precision quasi-Monte Carlo, and compare it with F(t)^k over a fine grid of t. If any negative gap is found, the theorem is false and the paper's key estimate (2) collapses; if no counterexample appears over a large sample, the black-box assumption is supported but still needs a proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The key estimate (2) in Section 3 is obtained by applying Mulgund's Theorem 1 to the correlation matrix R = ((k-1)/k)G + (1/k)J. This theorem is quoted from a concurrent, unpublished preprint ([9]) and is not proved or independently verified here. If Theorem 1 is false or its hypotheses are not met, the key estimate fails and Theorem 2 does not follow. The theorem is nontrivial: it asserts a lower bound on Gaussian orthant probabilities for every correlation matrix R with R - (1/k)J ⪰ 0, for every t in R. The paper provides no proof of this and no independent verification. Separately, Claim 1 as printed is internally inconsistent: it sets β_k^2/k = 1 + 4π log k/k > 1, but for every feasible SDP solution ∥z_C∥^2 ≤ 1 (by Cauchy-Schwarz, since ⟨u_i,z_C⟩ = ∥z_C∥^2 and ∥u_i∥ ≤ 1), so the condition ∥z_C∥^2 ≥ β_k^2/k can never hold. The following line's c_k^2 ≈ 4π log k/k^2 indicates the intended threshold is β_k^2 = 1 + 4π log k/k, not β_k^2/k = 1 + ..., but as written the proof of Theorem 2 is vacuous in the rounding case. Both issues must be resolved: the black-box theorem must be proved or replaced, and Claim 1's threshold must be corrected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":4333,"tokens_out":8117,"duration_ms":66830,"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":[{"comment":"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":"Section 2, Theorem 1; Section 3, Eq. (2)"},{"comment":"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.","section":"Section 3, Claim 1"}],"minor_comments":[{"comment":"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":"Section 2, SDP constraints"},{"comment":"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":"Section 3, Claim 1 proof"},{"comment":"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\\).","section":"Section 3, Claim 1 proof"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's main result is a direct corollary of a nontrivial theorem from a concurrent, unrefereed preprint. If the journal's policy requires proofs to be self-contained or to rely only on published results, this dependence alone may be disqualifying. The editor may also wish to consider the relationship to the concurrent work [2], which reportedly settles the same conjecture; the present note's contribution would then be primarily the concise derivation and the explicit asymptotic constant. These considerations are outside the technical soundness of the derivation, which, modulo the two issues in the major comments, is sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nThere 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.\n\nOverall, 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.","headline":"A short, clean proof of the conjectured optimal ratio for Boolean Max k-CSP, but the entire result rests on an unverified external theorem.","tokens_in":4890,"tokens_out":2914,"would_cite":true,"duration_ms":23743,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q17","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Boolean Max k-CSP","approximation algorithm","Gaussian rounding","SDP relaxation","stochastic domination","Unique Games Conjecture","hardness of approximation","random assignment"],"falsifier":"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.","tokens_in":3822,"feed_emoji":"🎯","tokens_out":3508,"duration_ms":30979,"temperature":0.7,"pith_summary":"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.","feed_headline":"Rounding algorithm matches optimal k/2^k barrier for Max k-CSP","feed_subtitle":"Sharp Gaussian analysis proves the 2017 conjecture and meets known hardness bounds.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the SDP relaxation, the Gaussian rounding algorithm, and the previous 0.626612 guarantee that the paper sharpens.","marker":"[7]"},{"why":"States the stochastic domination theorem used as a black box to derive the key integral estimate.","marker":"[9]"},{"why":"Formulates the conjecture that the algorithm achieves a (1-o_k(1))k/2^k approximation, which this paper settles.","marker":"[8]"},{"why":"Gives the Unique Games Conjecture hardness bound (k+O(k^0.525))/2^k, establishing that the new guarantee is asymptotically optimal.","marker":"[1]"},{"why":"Improves hardness to (k+1)/2^k for odd k and (k+2)/2^k for even k, matching the k/2^k target up to lower-order terms.","marker":"[5]"},{"why":"Provides unconditional hardness for k = 2^r - 1, making the constant optimal under P != NP for an infinite sequence of k.","marker":"[3]"}],"fun_headline_variants":["Gaussian rounding attains asymptotic optimum for Max k-CSP","Rounding matches hardness: Max k-CSP is asymptotically tight","Gaussian rounding proven optimal for Boolean Max k-CSP","Max k-CSP: Gaussian rounding reaches hardness limit","Asymptotic optimality: Gaussian rounding solves 2017 conjecture"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Gaussian rounding attains asymptotic optimum for Max k-CSP","Rounding matches hardness: Max k-CSP is asymptotically tight","Gaussian rounding proven optimal for Boolean Max k-CSP","Max k-CSP: Gaussian rounding reaches hardness limit","Asymptotic optimality: Gaussian rounding solves 2017 conjecture"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000541,"raw_usage":{"total_tokens":2509,"prompt_tokens":776,"completion_tokens":1733,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":392,"completion_tokens_details":{"reasoning_tokens":1649}},"tokens_in":392,"tokens_out":1733,"duration_ms":10265,"temperature":1.0,"reasoning_tokens":1649,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:13:01.237522+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"More Efficient Queries in PCP s for NP and Improved Approximation Hardness of Maximum CSP","cited_arxiv_id":null,"evidence_quote":"Supplies the SDP relaxation, the Gaussian rounding algorithm, and the previous 0.626612 guarantee that the paper sharpens."},{"cited_title":"Approximation Resistant Predicates from Pairwise Independence","cited_arxiv_id":null,"evidence_quote":"States the stochastic domination theorem used as a black box to derive the key integral estimate."},{"cited_title":"Constraint Satisfaction over a Non- B oolean Domain: Approximation Algorithms and U nique- G ames Hardness","cited_arxiv_id":null,"evidence_quote":"Formulates the conjecture that the algorithm achieves a (1-o_k(1))k/2^k approximation, which this paper settles."},{"cited_title":"The Nonapproximability of Non-Boolean Predicates","cited_arxiv_id":null,"evidence_quote":"Gives the Unique Games Conjecture hardness bound (k+O(k^0.525))/2^k, establishing that the new guarantee is asymptotically optimal."},{"cited_title":"2009 , doi =","cited_arxiv_id":null,"evidence_quote":"Improves hardness to (k+1)/2^k for odd k and (k+2)/2^k for even k, matching the k/2^k target up to lower-order terms."},{"cited_title":"Near-optimal algorithms for unique games , year =","cited_arxiv_id":null,"evidence_quote":"Provides unconditional hardness for k = 2^r - 1, making the constant optimal under P != NP for an infinite sequence of k."}],"review_version":1}