Kevin Pratt claims a randomized algorithm breaks the $2^n$ barrier for graph k-coloring
rrwilliams · x · 2026-08-04
A new randomized algorithm beats the long-standing $2^n$ barrier for graph $k$-coloring
Kevin Pratt’s arXiv paper claims that for every $k$, graph $k$-coloring can be solved by a randomized one-sided-error algorithm in time $O((2-\varepsilonk)^n)$.
- This breaks the classic $2^n\cdot\mathrm{poly}(n)$ barrier for the problem.
- Before this work, exponential improvements over that baseline were only known for $k \le 6.
- The paper also notes independent concurrent work by Zamir.
More from Research
- Free app teaches LLM basics and trains a small model locally on Apple MLX — dr_cintas · 2026-08-04
- Pure VLAs may not need long-horizon planning if VLMs can cover it — m_wulfmeier · 2026-08-04
- New CCN poster finds LLM-brain alignment scales differently across cortical systems — neuranna · 2026-08-04
- ThursdAI explores whether Codex and multi-agent math can solve Erdős problems — thursdai_pod · 2026-08-04
- New IC-based fMRI encoding models predict functional brain networks during stories — neuranna · 2026-08-04
- Benchmark scores may be mostly explained by one factor, says a new compute argument — nabeelqu · 2026-08-04