Color coding trick yields 2^O(sqrt(n)) depth-3 AC circuits for all symmetric Boolean functions
rrwilliams · x · 2026-09-30
A surprising result in circuit complexity: the Alon-Yuster-Zwick color coding technique can be used to build 2^{O(sqrt(n))}-size depth-3 AC circuits for every symmetric Boolean function.
Ryan Williams calls it the latest exhibit for the idea that "circuit lower bounds are hard to prove because they are false" — upper bounds keep shrinking in ways that defy prior intuition about circuit power.
More from Research
- ReScraper: a 0.6B model replaces heuristic data-cleaning stacks, boosting pretraining up to 4.7% — XiongChenyan · 2026-09-30
- Microsoft Research finds LLMs show Dunning-Kruger-style overconfidence in coding — burkov · 2026-09-30
- PixAI launches anime foundation model Tsubaki.3, open-sources Tagger 1.0 with tech report — Level-Ninja-2492 · 2026-09-30
- Lean creator Leonardo de Moura on AI proofs: the Collatz exploit shows verified checkmarks can lie — Machine Learning Street Talk · 2026-09-30
- LLM-42 Paper at SOSP 2026 Brings Deterministic LLM Inference via Verified Speculation — tianyin_xu · 2026-09-30
- Frontier AI Is a Set, Not a Point: Jagged Capabilities May Be the Steady State — vsikka · 2026-09-30