Graph Isomorphism Algorithm Improved to n^O(log n), Exponent Drops from 2 to 1
fortnow · x · 2026-11-03
MTHajiaghayi's team presents an improved Graph Isomorphism algorithm running in n^O(log n), reducing the best known explicit exponent from 2 to 1, joining parity, mean-payoff and stochastic games in this running-time class. Context: Babai's 2018 full paper had missing proofs and errors with bound exp(O((log n)^O(1))); the team used THEO to formalize recurrences into an explicit exponent. Funded by DARPA expMath.
More from Research
- LLM eval researcher LChoshen joins Weizmann Institute to launch CoLab — LChoshen · 2026-11-03
- Editing 0.016% of weights fixes Qwen reasoning loops, MATH-500 jumps from 7.9% to 48.1% — DeliciousGorilla · 2026-11-03
- MIT's Soft-MTP: one-line fix removes 80% noisy gradient, boosts MTP pre-training for free — kastnerkyle · 2026-11-03
- Aaron Roth shares calibrated multiaccuracy paper with Jiuyao Lu and Georgy Noarov — Aaroth · 2026-11-03
- Multicalibration is often overkill: calibrated multiaccuracy needs fewer samples — Aaroth · 2026-11-03
- MOPD becomes the post-training recipe of the year: TRL now ships multi-teacher on-policy distillation — SergioPaniego · 2026-11-03