The approximation constant for Boolean Max-k-CSP
the constant in the best proved approximation for Boolean Max--CSP
- steps
- 2
- by AI
- 0
- since
- 2009
The line is the frontier over time, climbing as the bound goes up: higher is better here. Filled dots are steps that moved it; muted dots are results that did not. Orange dots are catalog entries, results with AI in the loop. Hollow dots are candidates under review and never move the line.Grey dots along the bottom edge are results from before the quantity had a number, placed at the worst end because they have no value on this axis. Dots that would overlap are nudged sideways a few pixels. Hover a dot for its value and attribution.
About this frontier
Boolean Max--CSP asks for an assignment satisfying as many constraints as possible, where each constraint is an arbitrary predicate on at most bits. A constraint may accept only one of its local assignments, so a random assignment already gives ; Samorodnitsky and Trevisan showed that is the right scale, and Charikar, Makarychev and Makarychev showed that the factor is always available. The live question is the constant in front. Raghavendra's theorem says a semidefinite program achieves the optimal ratio for every CSP under the Unique Games Conjecture, but it is existential: it names no constant and no rounding. This frontier tracks the constant, which has moved twice since 2009 and now stands at , where the conditional hardness ceiling also sits.
Every step, newest first
| Date | Value | Who | Model | Status | Source |
|---|---|---|---|---|---|
| 5 Aug 2026 | A clean k / 2^k, removing the constant factor. The technical ingredient is an extension of the Gaussian comparison inequality used to resolve the weak simplex conjecture. This sits at the conditional ceiling: under Unique Games the constant cannot pass 1 asymptotically. Days-old preprint, no review: a candidate. | Ainesh Bakshi, with GPT-5.6 Sol Max on the computations | GPT-5.6 Sol Max | candidate unreviewed | entry |
| 2012 | best APPROX 2012, stated as a (0.626612 - o_k(1)) k / 2^k approximation. The record for fourteen years. | Konstantin Makarychev and Yury Makarychev | – | historical | source ↗ |
| 2009 | Near-optimal algorithms for maximum constraint satisfaction problems, ACM Transactions on Algorithms 5(3). The step that makes the constant a meaningful axis: the first proof that a factor of order k over the random assignment is always available, at c = 0.44. | Moses Charikar, Konstantin Makarychev and Yury Makarychev | – | historical | source ↗ |
All three rows, the hardness results and the scale come from the introduction and references of Bakshi's paper (arXiv:2608.05331), read here; years are as that list gives them, so Charikar-Makarychev-Makarychev is dated to the 2009 journal version, not the conference one. The ceiling is not drawn as a row because it is conditional on the Unique Games Conjecture and carries $o_k(1)$ terms: Austrin and Mossel (2009) give $(1+o_k(1))k/2^k$ and De and Mossel (2013) sharpen it to the $(k+1)/2^k$ and $(k+2)/2^k$ statements. Reaching the ceiling is why this frontier is close to complete.