HEXAGONbeta

On counting satisfying assignments via polynomial separation

A mix of human-written and AI-generated textHuman understanding: some partscs.CC — Computational Complexitycs.DS — Data Structures and Algorithms

Contributed by Scott Kominers ↗

Version 1 / Oct 27, 2026 / CC BY-SA 4.0

Abstract

We give a preliminary exposition of a qualitative form of the main result of OpenAI's preprint "The Exponential Time Hypothesis is false": for every fixed ε>0\varepsilon>0, 33-SAT on nn variables with mm clauses can be decided in time Oε(2εn(n+m)O(1))O_\varepsilon(2^{\varepsilon n}(n+m)^{O(1)}) and polynomial space. We separate the general counting procedure from the construction that supplies its input. The procedure deforms the clause inputs so that, at designated points, the count factors into local sums, from which Hermite interpolation recovers the original count; the construction builds such deformations from coordinate swaps in a tensor basis, leveraging a parity interpolation in the spirit of Alman and Williams.

Provenance statement

This note was developed in the process of navigating, reading, and attempting to distill the arguments in OpenAI's "The Exponential Time Hypothesis is false" with the assistance of GPT-6 Astra and Claude Opus 5.5 (accessed in part via Poe with the support of Quora, where I am an advisor). This draft is highly preliminary and heavily LLMathed; I expect to refine it further. I have read and understood each component individually, but I am still far from having fully "grokked" the argument as a whole.

Tools used

OpenAI
ChatGPTVersion 6 Astra
Anthropic
Claude OpusVersion 5.5
Quora
Poe

References

  1. J. Alman and R. Williams, Probabilistic polynomials and Hamming nearest neighbors , Proc. 56th IEEE Symposium on Foundations of Computer Science (2015), 136--150. Section, theorem, and lemma numbering follows the full version, July 18, 2015: https://people.csail.mit.edu/rrw/polys-hamming.pdf.link
  2. J. Alman and R. Williams, Probabilistic rank and matrix rigidity , Proc. 49th ACM Symposium on Theory of Computing (2017), 641--652. Lemma numbering follows arXiv:1611.05558v2 (https://arxiv.org/abs/1611.05558v2).arXiv
  3. C. Calabro, R. Impagliazzo, and R. Paturi, A duality between clause width and clause density for SAT , Proc. 21st IEEE Conference on Computational Complexity (2006), 252--260.
  4. R. Impagliazzo and R. Paturi, On the complexity of kk-SAT , J. Comput. System Sci. 62 (2001), no. 2, 367--375.
  5. R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity? , J. Comput. System Sci. 63 (2001), no. 4, 512--530.
  6. OpenAI, The Exponential Time Hypothesis is false , Math Release Preprint, October 25, 2026 version (https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf).link
  7. J. von zur Gathen and J. Gerhard, Modern Computer Algebra , 3rd ed., Cambridge University Press, 2013.

Version history

  1. v1Submitted by Scott KominersInitial depositCurrentOct 27, 2026