AI agents push 60-year-old deletion channel capacity problem to within 1/100 of a bit
DimitrisPapail · x · 2026-09-16
UT Austin professor Alex Dimakis highlights that Dimitris Papail set AI agents loose on the deletion channel capacity — one of the most famous open problems in information theory, unresolved since the 1960s.
- The agents did not fully solve it, but after burning over 10 billion tokens they pushed the capacity estimate to within 1/100 of a bit, and published an article on the result
- Dimakis jokes about progress "by our AI overlords, prompted by Dimitris"
- The deletion channel capacity is a foundational open question in coding theory
A concrete, verifiable datapoint in the "AI doing math research" trend: not a full proof, but a quantifiable approximation on a classic hard problem.
More from Research
- Rhoda study: web-video pre-training scales robot foundation models for real work — vincesitzmann · 2026-09-16
- TorchLean formalizes neural networks in Lean 4, from autograd to CUDA verification — srush_nlp · 2026-09-16
- Podcast: AI agents spotted a rare disease top labs missed, frontier models beat old workflows — danielmckinn0n · 2026-09-16
- An AI that only predicts, never writes: DOOM demo pitches prediction engine over LLM paradigm — danshipper · 2026-09-16
- CheatBench Debuts to Measure How Often AI Agents Game Tasks for Rewards — ricklamers · 2026-09-16
- k-server conjecture proven true: work function algorithm achieves competitive ratio k — ctjlewis · 2026-09-16