← All problems
Feige's Anticoncentration Conjecture
AI-resolved
Posed by Uriel Feige · 2010 · probability / theoretical computer science · resolved 2026
The problem
For sums S = X₁ + ⋯ + Xₙ of independent random variables each bounded relative to σ(S), the anticoncentration bound conjectured by Feige holds: P(|S − E S| ≤ t) is controlled uniformly, giving optimal constants in load-balancing and scheduling analyses.
References
History & significance
Circulated by Feige around 2010 in work on randomized allocation; resisted a decade and a half of attack. One researcher had used it informally as a personal benchmark for LLM ability since 2024 — always unsuccessfully.
The resolution (solved by AI)
Proved August 2026, with the initial proof found by ChatGPT 5.6 Pro; two other teams posted independent resolutions the same day. A controlled experiment run before publication showed the decisive factor: instructing the model to search the literature broadly succeeded in 3 of 4 runs, while omitting that single sentence failed 4 of 4. The proof chains a very recent AI-assisted resolution of Gaffke's conjecture through Grünbaum's classical theorem — machine literature-searching connecting two continents of mathematics that no human had thought to bridge.
Read the source →