How AI impacts theoretical computer science

OpenAI, 2026-10-26: The Exponential Time Hypothesis is False. Source

Anthropic, 2026-10-27: A 2^{o(n)} Time Algorithm for 3-SAT. Source

Russell Impagliazzo, Ramamohan Paturi, Ryan Williams, 2026-10-26: Their open letter says participation is not certification and asks the community for independent scrutiny, explanations and follow-up study of the claim. Source

Ryan Williams, 2026-10-26: Says the three organizers signed no NDAs, receive no pay, and will share findings publicly; says OpenAI agreed to release materials and sponsor a conference. Source

Ryan Williams (to TechCrunch), 2026-10-27: Called some proof parts perhaps routine and two or three alien-looking; does not think OpenAI's algorithm can be the best achievable. Source

Ryan Williams, 2026-10-27: Conditional on correctness, every computer scientist should raise their P=NP credence somewhat, by varying amounts. Source

Lance Fortnow, 2026-10-28: States he has not checked the proof himself yet considers it safe to assume ETH is finished; notes Lean covers a slightly weaker bound. Source

Scott Aaronson, 2026-10-26: Reported the claim as roughly exp(n/√log(n)) for 3SAT, and moved his personal P=NP probability from 3% to 5%. Source

Emanuele Viola, 2026-10-27: Wrote that the manuscript shows ETH and strong ETH false, said he is not shocked, and hopes conditional results get recalibrated. Source

Ben Recht, 2026-10-28: Calls OpenAI's algorithm galactic, running an exponential-time subroutine when variables number below 10^10,000,000,000,000,000,000,000,000. Source

Ryan O'Donnell, 2026-10-30: LLM-assisted exposition recasting OpenAI's approach through sparse permanents; deterministic sparse case, with a randomized appendix for arbitrary 3-CNFs. Source

Shiva Kintali, 2026-10-26: Posted a simplified exposition of OpenAI's proof, developed with Claude and ChatGPT then expanded by hand, aiming only at basic ETH. Source

Mark Sellke (Member of Technical Staff at OpenAI, per his homepage), 2026-10-29: Slides outline OpenAI's 2^{o(n)} k-SAT algorithm, credit the theorem to OpenAI/Anthropic 2026, and skip quantitative optimizations. Source

Francis Zane, 2026-10-30: Reports people compiling the Lean proofs locally; opens a replication thread, suggesting a non-author should probably check though not everyone needs to repeat it. Source

Alman, Vassilevska Williams, 2026-10-05: Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs. Source

Anthropic (Lean), 2026-10-06: Truly Subquadratic 3SUM and Truly Subcubic APSP: a Lean 4 formalization. Source

Scott Aaronson, 2026-10-07: Said the preprint refutes half-century-old conjectures, credited an Anthropic model with the crucial idea, and contrasted digested release with OpenAI's raw one. Source

Virginia Vassilevska Williams (co-author), 2026-10-13: Co-author says the proof came from an internal Anthropic model, not the authors; argues, from one run each, her group's 2023 notes plus two prompts would have sufficed. Source

Emanuele Viola, 2026-10-06: Reacted with surprise and added the paper to his book's growing list of disproved conjectures. Source

Sankeerth Rao Karingula (Agentin AI), Shachar Lovett (UC San Diego), 2026-10-11: Give a simplified proof of polynomial 3SUM and APSP improvements with weaker exponents, using selected-entry matrix multiplication; disclose an Agentin AI agent swarm, ChatGPT and Codex. Source

Ruhollah Majdoddin, 2026-10-12: Extends the matrix theorem to D <= N^0.172 and claims deterministic 3SUM in n^{1.9945+o(1)}, citing the original exponent as 1.9992. Source

Nick Fischer, 2026-10-23: Treats the 3SUM Hypothesis as recently refuted, says geometric lower bounds lost their foundation, and recovers many under the k-AP Hypothesis. Source

Alman, Vassilevska Williams, 2026-10-05: Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs. Source

Anthropic (Lean), 2026-10-06: Truly Subquadratic 3SUM and Truly Subcubic APSP: a Lean 4 formalization. Source

Scott Aaronson, 2026-10-07: Reported APSP at O(n^2.9995), said this refutes a half-century-old conjecture, and credited an Anthropic model with the crucial idea. Source

Virginia Vassilevska Williams (co-author), 2026-10-13: Co-author says the proof came from an internal Anthropic model, not the authors; argues, from one run each, her group's 2023 notes plus two prompts would have sufficed. Source

Sankeerth Rao Karingula (Agentin AI), Shachar Lovett (UC San Diego), 2026-10-11: Give a simplified proof of polynomial 3SUM and APSP improvements with weaker exponents, using selected-entry matrix multiplication; disclose an Agentin AI agent swarm, ChatGPT and Codex. Source

Ruhollah Majdoddin, 2026-10-12: Claims n^{2.9945+o(1)} for Exact Triangle, (min,+)-product and APSP, citing the original APSP exponent as 2.99942. Source

Barna Saha, Christopher Ye, 2026-10-14: Claim deterministic (min,+) product in Õ(N^{2.9964}), improving the O(N^{2.9995}) they attribute to Anthropic via Alman and Vassilevska Williams, using its thin matrix theorem. Source

OpenAI, 2026-10-06: The Unique Games Theorem. Source

Scott Aaronson (UT Austin), 2026-10-07: Says he and others are fairly sure it is a proof, citing a Lean certificate, but apparently almost no human has understood these proofs yet. Source

Dana Moshkovitz (UT Austin), texts relayed by Scott Aaronson, 2026-10-07: Her early texts, relayed by Aaronson, call the writeup unreadable without AI help and describe a strange new recursive code, unlike long or short codes. Source

Dana Moshkovitz, relayed by Scott Aaronson (comment #2), 2026-10-07: Aaronson relays her view that the conjecture is true, its famous corollaries did not need it, and understanding the proof's mechanism will take time. Source

Dana Moshkovitz (UT Austin; talk abstract), 2026-10-30: Her talk abstract offers a mental map of the proof, viewing its innovation as a new code, Hadamard with a noise test; says the writeup reads poorly for humans. Source

Scott Aaronson (post and comment #9), 2026-10-31: Says Moshkovitz, his wife, studied the proof closely with Khot, Håstad and Minzer and gave two Simons talks; says they can understand the new code once shown it. Source

Lance Fortnow (former founding dean of computing, Illinois Tech), 2026-10-07: Presents the release as proofs not yet fully verified, and makes his assessment of its significance conditional on whether they hold up. Source

Rares-Darius Buhai, Suprovat Ghoshal, Neng Huang, Pravesh Kothari, Euiwoong Lee, Konstantin Makarychev, Yury Makarychev, 2026-10-19: Their Max-Cut paper uses it conditionally: if OpenAI's proof is correct, one of their hardness results would need only NP not in BPP. Source

Mark Braverman (Princeton), quoted by Quanta, 2026-10-07: Speaking in September about the rumors, he criticized announcing mathematics through press releases, yet said an AI proof could open directions if its key assumptions are extracted. Source

Dor Minzer (MIT), quoted by Quanta, 2026-10-07: Told Quanta that AI tools remove the value of failing and may deter long projects; the article reports no verdict from him on the proof's correctness. Source

Bill Gasarch (University of Maryland), 2026-10-18: On the whole release: warns a Lean check can certify a mis-encoded theorem, and expects humans to read, understand and, where needed, repair these proofs over time. Source

OpenAI, 2026-10-06: Perfect completeness for 2-to-1 games. Source

OpenAI, 2026-10-06: Exact Derandomization of Logarithmic Space: L = RL = BPL. Source

Scott Aaronson (UT Austin), 2026-10-07: Lists L = BPL among results he will watch, calling it a major derandomization conjecture whose truth was not seriously doubted; says humans have barely begun digesting these proofs. Source

Omer Reingold, relayed by Scott Aaronson, 2026-10-07: In a remark Aaronson shared with permission, he jokes that the RL versus L result was when things turned serious for him; a reaction, not an assessment. Source

Lance Fortnow (former founding dean of computing, Illinois Tech), 2026-10-07: Lists a full derandomization of randomized log space, without the Lean tag given to two neighbours, and says these proofs have not been fully verified. Source

Lance Fortnow (former founding dean of computing, Illinois Tech), 2026-10-15: Wrote that complexity results are hard to formalize, then updated to say OpenAI had released what he terms a claimed Lean proof of L = RL = BPL. Source

Kuan Cheng, Shengtang Huang, Ruiyang Wu, 2026-10-19: Their paper says OpenAI announced BPL = L and argues their L-AC^1 result still offers multiplicative error 2^{-poly log n}; it does not assess OpenAI's proof. Source

OpenAI, 2026-10-06: An Upper Bound of 9/4 for the Matrix Multiplication Exponent. Source

Steven Strogatz (Cornell), 2026-10-06: Singled out the 2.25 exponent as especially striking, put the earlier record near 2.37, and likened the leap to Bob Beamon's long jump. Source

Scott Aaronson (UT Austin), 2026-10-07: Highlights an n^{9/4+o(1)}-time matrix multiplication result, noting a rational exponent and a completely different approach from earlier bounds. Source

Lance Fortnow (former founding dean of computing, Illinois Tech), 2026-10-07: Lists n^{2.25+ε} time, tagged as formalized in Lean, while cautioning that the release's proofs have not been fully verified. Source

Bill Gasarch (University of Maryland), 2026-10-25: Restates ω(C) ≤ 2.25 and the every-field bound as Lean-formalized, compares the drop to Beamon's jump, and says he has not checked the third-party every-field project. Source

Rafael Pass, 2026-10-20: Says OpenAI claimed the bound via non-constructive spectral arguments; gives an explicit integer-arithmetic algorithm reaching it, with the main ideas his own and Codex used extensively. Source

Alimzhan Amanov, Maxim van den Berg, Jeroen Zuiddam (University of Amsterdam), 2026-10-21: Expound OpenAI's proof, give a version valid for every field, and prove a barrier: current degeneration ingredients cannot improve these bounds. They disclose LLM use. Source

Amir Shpilka (Tel Aviv University), 2026-10-27: States OpenAI's manuscript proves ω ≤ 9/4, gives a self-contained explicit version following its ideas, and says he verified all arguments in his exposition, disclosing AI assistance. Source

Sela Navot, 2026-10-07: Repository reports an extension of the bound to arbitrary fields, found with GPT-6 Astra and GPT-6.1 Sol. Source

Houxi Lü, 2026-10-12: Preprint addresses matrix multiplication in arbitrary characteristic. Source

OpenAI, 2026-10-06: Subset Sum in Time $O(2^{0.49n})$. Source

Lance Fortnow, 2026-10-07: Batch-level remark: Fortnow wrote the release's proofs had not been fully verified and framed his assessment as conditional on them holding up; he does not name this result. Source

Lance Fortnow, 2026-10-28: Fortnow wrote the ETH-refuting algorithm adds nothing for Subset Sum, whose best algorithms he described as still taking roughly 2^{n/2}; the post body does not mention the 0.49 manuscript. Source

Lance Fortnow (blog comment), 2026-10-29: Replying to a commenter who pointed to OpenAI's 2^{0.49n} claim, Fortnow called it impressive but not 2^{o(n)}; he does not say he checked it. Source

Lixi Ye and Baitian Li, 2026-10-07: Ye and Li note OpenAI released a similar-type result and report their own O(2^{0.499999n}) algorithm, developed independently by another route; they do not assess OpenAI's proof. Source

Ce Jin and Xiao Mao, 2026-10-14: They cite both OpenAI Subset Sum manuscripts among references on exponential-time and average-case work, offering no assessment of their correctness. Source

OpenAI, 2026-10-06: Deterministic Polynomial Factorization over Prime Fields. Source

Pierre-Jean Spaenlehauer, 2026-10-23: Spaenlehauer treats the factoring result as OpenAI's claim, resting on a companion zero-free preprint; he writes the community had not reviewed or validated it and no formalized proof existed. Source

Scott Aaronson, 2026-10-07: Aaronson listed GRH-free deterministic factoring among results he expected to watch most; he reported no check and said it appeared humans had understood almost none of these proofs yet. Source

Lance Fortnow, 2026-10-07: Batch-level remark: Fortnow wrote the release's proofs had not been fully verified and framed his assessment as conditional on them holding up; he does not name this result. Source

Jizhou Guo, 2026-10-08: Guo's AI-compiled note derives deterministic irreducible-polynomial construction conditional on family 142 Theorem 1.1 and family 029 Theorem 1.2, adding that neither family lists a Lean formalization; it verifies neither. Source

OpenAI, 2026-10-06: The PCP-for-PPAD conjecture: a quasilinear reduction. Source

Panagiotis Kanellopoulos and Themistoklis Melissourgos, 2026-10-19: A footnote describes the manuscript as generated with an OpenAI model and claiming the quasilinear version; the authors know of no independent verification so far. Source

Ioannis Panageas, Avi Shein, Shayan Taherijam and Vijay V. Vazirani, 2026-10-26: The authors say they have not independently verified OpenAI's claimed proof and keep their constant-error hardness result conditional on PCP for PPAD. Source

Xiaotie Deng, Ningyuan Li, Zihe Wang and Jie Zhang, 2026-10-19: They say the OpenAI preprint reports a proof of the conjecture, giving no assessment; their own conditional hardness rests on Rubinstein's theorem and PPAD-ETH instead. Source

Lance Fortnow, 2026-10-07: Batch-level remark: Fortnow wrote the release's proofs had not been fully verified and framed his assessment as conditional on them holding up; he does not name this result. Source

Nagda, Raghavan, Thakurta, 2025-09-22: Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory. Source

Nagda, Raghavan, Thakurta, 2025-11-20: Reinforced Generation of Combinatorial Structures: Applications to Complexity Theory (arXiv v5, first version stating the TSP bound). Source