HEXAGONbeta

Some exposition of “The Exponential Time Hypothesis Is False”

Primarily AI-generated textHuman understanding: no partscs.CC — Computational Complexity

Contributed by Ryan O'Donnell ↗

Version 1 / Oct 27, 2026 / CC BY 4.0

Abstract

This is an exposition of the paper "The Exponential Time Hypothesis Is False" by OpenAI [Oct. 26, 2026], produced through discussion with an LLM. Among other things, it tries to highlight the approximating polynomial for parity, and writes the matrix version of this polynomial using (a light amount of) quantum language.

Provenance statement

This was obtained through interaction with ChatGPT6, after uploading the original OpenAI paper.

Tools used

OpenAI
ChatGPTVersion 6

References

  1. Josh Alman and Ryan Williams. Probabilistic Polynomials and Hamming Nearest Neighbors. In 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , 2015. Lemma 3.1. https://arxiv.org/abs/1507.05106.link
  2. Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton. Symmetric Polynomials over Zm\mathbb Z_m and Simultaneous Communication Protocols. Journal of Computer and System Sciences 72(2):252--285, 2006. https://doi.org/10.1016/j.jcss.2005.06.007.DOI
  3. Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra. Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications. Journal of the ACM 70(6), Article 42, 2023. Lemmas 4.10 and 6.2. https://doi.org/10.1145/3625226.DOI
  4. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Trimmed Möbius Inversion and Graphs of Bounded Degree. In STACS 2008 , pages 85--96, 2008. https://doi.org/10.4230/LIPIcs.STACS.2008.1336.DOI
  5. Ying Liu and Shiteng Chen. Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs. In 41st Symposium on Theoretical Aspects of Computer Science (STACS) , LIPIcs 289, 49:1--49:18, 2024. Theorem 11. https://doi.org/10.4230/LIPIcs.STACS.2024.49.DOI
  6. OpenAI. The Exponential Time Hypothesis Is False . Manuscript dated October 17, 2026; revised October 25, 2026. Sections 2--4 and Appendix B.
  7. Viresh Patel and Guus Regts. Approximate Counting Using Taylor's Theorem: A Survey. Bulletin of the EATCS , 2022. https://arxiv.org/abs/2212.08143.link
  8. Srikanth Srinivasan. On Improved Degree Lower Bounds for Polynomial Approximation. In FSTTCS 2013 , LIPIcs 24, pages 201--212, 2013. Lemma 14. https://doi.org/10.4230/LIPIcs.FSTTCS.2013.201.DOI
  9. Emanuele Viola. On the Power of Small-Depth Computation. Foundations and Trends in Theoretical Computer Science 5(1):1--72, 2009. Section 1.2.3, including an argument communicated by Avi Wigderson. https://doi.org/10.1561/0400000033.DOI

Version history

  1. v1Submitted by Ryan O'DonnellInitial depositCurrentOct 27, 2026