MathsClub Problems, proofs & good company

← 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.

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.