What Does the Refutation of the Exponential Time Hypothesis Mean for Learning Theory?

Introduction

The Exponential Time Hypothesis (ETH) of Impagliazzo and Paturi [86] states that 3-SAT on $n$ variables needs time $2^{\Omega(n)}$. For a quarter century it was the standard way to turn NP-hardness into quantitative lower bounds. Its relatives did the same for exact constants (SETH), for approximation (Gap-ETH) and for counting (#ETH). Learning theory used all of them. ETH and Gap-ETH give lower bounds for proper learning of decision trees [96, 95, 97] and for computing the VC and Littlestone dimensions [109, 105]. They also give lower bounds for training neural networks [75, 70], for robust proper learning of halfspaces [65, 66], and for computational–statistical tradeoffs [33]. SETH gives quadratic lower bounds for kernel methods, attention and nearest neighbors [31, 14, 6, 118]. In inference, ETH was the basis of the conclusion that bounded treewidth is necessary for efficient inference [89, 90].

In October 2026, two independent works refuted ETH [113, 55]. Both count the satisfying assignments of a $k$-CNF on $n$ variables in deterministic time $2^{n/(\log n)^{1/2-o(1)}}$, with polynomial dependence on the number of clauses. One works by polynomial interpolation, the other by signed sums of tensor networks contracted in different orders, and both need sparse instances: linearly many constraints of bounded width. SETH, Gap-ETH, #ETH and NSETH each imply ETH, so all of them are false as well. Two forms survive. CNF-SETH states that CNF-SAT with polynomially many clauses of unbounded width needs time $2^{(1-\gamma)n}$, and the Max-3-SAT Hypothesis states the same for the maximum number of satisfiable clauses of a dense 3-CNF (§ 2.5).

This paper determines what the refutation changes in computational learning theory. Which learning problems become subexponential? Which lower bounds survive, and on which hypothesis? We use the new algorithms only through the three statements of § 2.3.

The locality principle

A learning problem is a constraint satisfaction problem. Its variables are the bits of the hypothesis description, and its constraints are the labeled examples. For most classical classes, such as DNF, decision trees and halfspaces on dense data, every example constrains every description bit. The resulting formulas have clauses of width $\Theta(N)$, and the new algorithms do not reach this regime. The dividing line is the following notion.

Definition 1.1 (Informal; see Definition 2.2). A class of hypotheses with $N$-bit descriptions $w \in\{0,1\}^{N}$ is $\kappa$-local if for each example $x$ there is a set $R(x) \subseteq[N]$ of at most $\kappa$ positions such that the label $h_w(x)$ depends only on the bits of $w$ in $R(x)$.

Sparse data make quantized models local. A binarized perceptron $x \mapsto1\langle w,x\rangle\geq0$ with $w \in\{\pm1\}^{n}$ is $\kappa$-local on $\kappa$-sparse inputs, because only the weights on the support of $x$ matter. With $b$-bit weights, and for quantized embedding models and factorization machines on bags of $k$ tokens, the locality is $\kappa= bk$. Two-layer binarized networks with $r$ hidden units are $(rk+r)$-local. A graphical model of bounded degree and arity is local in the same sense: each factor reads a bounded number of variables. Our main finding is a principle.

The new algorithms speed up learning when each labeled example constrains few bits of the hypothesis description. Under CNF-SETH the speed-up ends when examples constrain $\Theta(\log N)$ bits.

Three transitions make the principle precise. Figure 1 summarizes them.

Transition 1: locality. For local classes, the version space of a sample is the solution set of a $\kappa$-CNF, so every computation on it reduces to counting $\kappa$-CNFs. Conversely, a padding gadget embeds $k$-SAT into binarized perceptrons on $2k$-sparse data.

Theorem A (Locality; Theorems 3.2, 3.4, 3.8 and 3.10). $\mathcal{H}$ be a $\kappa$-local class with $N$-bit descriptions.

1. Exact counting and uniform sampling of version spaces, the halving algorithm, and proper PAC learning at every accuracy run in time $\operatorname{poly}(m)\cdot2^{O(\kappa^{2}N\log\log N/\sqrt{\log N})}$. At constant accuracy, proper PAC learning runs in time $2^{O(\kappa N/\sqrt{\log N}+\kappa^{2})}$.

2. At inverse-polynomial accuracy, and up to a factor 2 in the locality, proper learning of $\kappa$-local classes is equivalent to $\kappa$-SAT.

3. Under CNF-SETH, for every $\gamma>0$ there is $K$ such that consistency and proper PAC learning to inverse-polynomial accuracy of binarized perceptrons on $(K\log N)$-sparse data need time $2^{(1-\gamma)N}$.

For constant $\kappa$, the counting part of (1) is Corollary C.2 of [113] in learning terms. New are the uniformity in $\kappa$, the equivalence (2) and the hardness (3). Consistency and learning to inverse-polynomial accuracy are thus subexponential up to locality $(\log N)^{1/4-o(1)}$, and as hard as CNF-SAT at locality $\Theta(\log N)$. Between the two lies the open window of $k$-SAT for $k=(\log N)^{\Theta(1)}$. At constant accuracy the subexponential range extends to $(\log N)^{1/2-o(1)}$.

Transition 2: accuracy. For agnostic learning, the cost depends on the size of the sample, not on $N$. Exact ERM on $m$ examples reads only $\kappa m$ description bits, and it is a sparse weighted constraint problem. We compute its entire error profile, the number of hypotheses with exactly $j errors for every $j$, by tensor contraction over the truncated polynomial ring $(\mathbb{Z}/2^{\ell}\mathbb{Z})[V]/(V^{\ell})$. The lower bounds use a length form of ETH. The hypothesis $\mathrm{ETH}^{\mathrm{len}}_{C}$ states that SAT on CNFs of length $L$ needs time $2^{L/(\log L)^C}$. It is the instance with an explicit rate of the polylog-slack hypotheses of [56]. The new algorithms refute it for $C < 1/2$, and for $C \ge1/2$ it states that they are optimal up to polylogarithmic factors in the exponent.

Theorem B (Accuracy; Theorems 4.1, 4.3, 4.6, 4.9 and 4.12 and Corollaries 4.2 and 4.10). Let $\mathcal{H}$ be a $\kappa$-local class with $N$-bit descriptions and $VC$ dimension $d$.

(1) Exact ERM, the error profile and the exponential mechanism on a sample of size $m \ge\max\{\kappa,2\}$ take time $\operatorname{poly}(N)\cdot2^{O(\kappa m/\sqrt{\log m})}$. For literal disjunctions on 3-sparse data, consistency on $m$ examples needs time $2^{m/(\log m)^{C+o(1)}}$ under $\mathrm{ETH}^{\mathrm{len}}_{C}$.

(2) Proper agnostic learning takes time $\operatorname{poly}(N)\cdot2^{O(\kappa d/(\varepsilon^2\sqrt{\log(2d/\varepsilon)})+\kappa^2)}$ for constant confidence. At a small constant accuracy $\varepsilon_0$, proper learning of literal disjunctions on 3-sparse data, realizable or agnostic, needs time $2^{N/(\log N)^{C+O(1)}}$ under $\mathrm{ETH}^{\mathrm{len}}_{C}$. So at constant accuracy, proper learning of constant-local classes is SAT parameterized by formula length, up to polylogarithmic factors in the exponent.

(3) Under the Max-3-SAT Hypothesis, proper agnostic learning of literal disjunctions on 3-sparse data to accuracy $1/(8N^3)$ needs time $2^{(1-o(1))N}$.

With the quasi-linear PCPs of Dinur and of Ben-Sasson and Sudan [63, 39], $\mathrm{ETH}^{\mathrm{len}}$ replaces Gap-ETH for gap reductions of quasi-linear size, at a polylogarithmic loss in the exponent (Corollary 4.11). At inverse-polynomial accuracy, more data makes exact ERM harder: it is subexponential on samples of size $o(N\sqrt{\log N})$ and needs time $2^{(1-o(1))N}$ on samples of size $\Theta(N^3)$.

Transition 3: treewidth. Exact inference in graphical models is #SAT parameterized by the length of the model, and the textbook algorithms take time exponential in the treewidth.

Theorem C (Treewidth; Theorems 5.1 and 5.5 and Corollaries 5.2, 5.3 and 5.6). Consider Boolean graphical models of bounded degree and arity with small nonnegative integer weights.

(1) On $n$ variables, the partition function, all marginals, and a minimum-energy assignment can be computed exactly in time $2^{O(n/\sqrt{\log n})}$. On bounded-degree expanders, every elimination order and every structured DNNF needs time or size $2^{\Omega(n)}$. Under $\mathrm{ETH}^{\mathrm{len}}_{C}$, deciding whether the partition function is positive needs time $2^{\mathrm{tw}/(\log\mathrm{tw})^{C+o(1)}}\operatorname{poly}(n)$.

(2) Under #CNF-SETH, for every $\gamma> 0$, no algorithm computes partition functions in time $2^{(1-\gamma)\mathrm{tw}}\operatorname{poly}(n)$, already on models with $n \le\mathrm{tw}^{O(1)}$ variables.

The treewidth-based algorithms take time $2^{\Theta(\mathrm{tw})}$. So they are not optimal when the model has $n = O(\mathrm{tw})$ variables, but they are optimal again when $n$ may be polynomially larger than $\mathrm{tw}$. The preprint [55] already notes that its algorithm beats every fixed tree of cuts on expanders; the inference statements and both lower bounds are new. The ETH-based bound of [89, 90] has lost its proof. Part (1) puts a bound of the form $2^{\mathrm{tw}/\operatorname{polylog}\mathrm{tw}}$ on the surviving hypothesis $\mathrm{ETH}^{\mathrm{len}}_{C}$, and the qualitative statement that inference is not polynomial in the treewidth rests on NP not having polynomial-size circuits [CSH08, CC16].

By-products for fine-grained complexity. Three results do not concern learning.

• Exact Max-SAT with $cn$ clauses takes time $2^{O((1+c)n/\sqrt{\log n})}$, so the Sparse Max-SAT Hypotheses of Alman and Vassilevska Williams [17] are false (Corollary 4.5). This also follows from [113 Theorem 1.1] with a threshold circuit; the error profile gives in addition the whole distribution of the number of violated clauses.

• Under CNF-SETH, a #k-SAT algorithm with exponent $k^{\mu n/(\log n)^{\nu}}$ needs $\mu\ge\nu$ (Corollary 3.7). A better rate must come with a worse dependence on $k$.

• CNF-SAT with linearly many clauses of arbitrary width is subexponential (Proposition 6.1). So the hard instances of CNF-SETH have superlinearly many clauses, and the hardness of low-dimensional Orthogonal Vectors no longer follows from a hypothesis about SAT.

What survives. § 6 takes stock of the conditional lower bounds of learning theory. Bounds stated with polynomial slack, such as the hardness of computing the VC dimension [109], survive under Almost-ETH [106], and so under $\mathrm{ETH}_{C}^{\mathrm{len}}$. Bounds from near-linear reductions survive under $\mathrm{ETH}_{C}^{\mathrm{len}}$ with a polylogarithmic loss in the exponent. Bounds whose exponent is only $\Theta(\log\log N)$, such as those for proper learning of decision trees [96] and for partial MCSP [82], keep almost nothing. Bounds that rest on CNF-SETH or on $k$-Clique survive verbatim. Among them is the $n^{k-o(1)}$ bound for juntas, the canonical non-local class. The quadratic SETH-based bounds for attention and kernel density estimation are not contradicted, but they now rest on the low-dimensional OV hypothesis alone. The next obstacle is permutations. On difference vectors $e_i-e_j$, ERM for real-valued halfspaces is weighted Feedback Arc Set (Proposition 8.1), and the new algorithms do not reach it.

What is new. The two preprints [113, 55] contain no statement about learning. Lemma 3.1 is the encoding of [113 Corollary C.2], and the upper bound for counting at constant locality is that corollary. Everything else is new: the locality principle with bounds uniform in $\kappa$, the equivalence with $\kappa$-SAT and the hardness at logarithmic locality, the error-profile algorithms for ERM, agnostic and private learning, the lower bounds at constant and inverse-polynomial accuracy, the results on inference, the by-products above, and the ledger.

Techniques

Version spaces as CNFs. Each example excludes at most $2^\kappa$ patterns of its $\kappa$ relevant bits. So the version space is the solution set of a $\kappa$-CNF with at most $m2^\kappa$ clauses (Lemma 3.1). The algorithm of [55] counts its solutions in time $2^{O(\kappa^2 N\log\log N/\sqrt{\log N})}$ independently of $m$, and sampling, halving and learning follow by self-reducibility. For the converse, a padding gadget turns a clause into a sparse example. Its inner product with a sign vector is $2t-2$, where $t$ is the number of true literals (Lemma 3.3).

The error profile as one contraction. Agnostic learning needs the number of hypotheses with exactly $j$ errors for every $j$. An example contributes the factor $1$ when it is fit and $V$ when it is not, and the contraction theorem of [113] over $(\mathbb{Z}/2^{P}\mathbb{Z})[V]/(V^\ell)$ computes the product sum. Three choices make it exact. We restrict to the $\kappa m$ description bits that the sample reads. We turn the factor graph into a bipartite Boolean tensor network of degree $\max\{\kappa,3\}$ (Lemma B.1). And we choose the precision $P$ and the truncation order $\ell$ so that no coefficient is lost. The cost depends on the total size $\kappa m$ of the sample instead of $\kappa^2N$, which gives sample-sensitive learning, the exponential mechanism, and exact sparse Max-CSP.

Lower bounds that control variables, length and accuracy. For consistency, a quantitative form of Schuler’s width reduction [119, 51] shows that, under CNF-SETH, $k$-SAT with $k=K\log n$ needs time $2^{(1-\gamma)n}$, with solution counts preserved (Lemma 3.5). For constant accuracy, a quasi-linear PCP turns a CNF of length $L$ into an LD$_3$ sample in dimension $L\operatorname{polylog}L$, with perfect completeness and a constant gap (Lemma 4.8). For inference, OR-chains with copied variables turn any CNF into a degree-3 factor graph whose pathwidth is at most the number of variables plus 2 (Lemma 5.4).

Organization

§ 2 fixes the model, imports the new algorithms, builds the engine of all our algorithms, and states the surviving hypotheses. § 3 to § 5 prove the three transitions. § 6 takes stock of the conditional lower bounds of learning theory. § 7 discusses related work, and § 8 isolates the permutation obstacle and lists open problems. The main text gives a proof sketch for each result. Section A explains the appendix, which contains all full proofs in a structured form.

AI disclosure. This paper was written with Claude Opus 5.5 (Anthropic), working as an agent in Claude Code. The author posed the question and directed the presentation. Claude chose the results, proved them, wrote the text and drew the figures. Separate Claude agents searched the literature, audited the proofs and reviewed the paper as referees, and the paper was revised to address their findings. The gadgets and reductions were tested by brute force on small random instances, and the asymptotic estimates were checked symbolically and in exact arithmetic. The author is responsible for the content.

Preliminaries

This section fixes the model, states the new algorithms, builds the computational engine that the rest of the paper uses, and lists the hypotheses that survive.

Notation and the learning model

We write log for $\log_2$ and $[n]$ for $\{1,\ldots,n\}$. For $w \in\{0,1\}^{N}$ and $R \subseteq[N]$, the string $w|_R$ is the restriction of $w$ to $R$. A clause is a nonempty set of literals, and its width is its size. A CNF is a finite set of clauses, and a $k$-CNF has only clauses of width at most $k$. The length $L$ of a CNF is its number of literal occurrences, $L = \sum_{C} |C|$. For a CNF $F$ on declared variables $z_1,\ldots,z_n$, the number $\#F$ counts the satisfying assignments in $\{0,1\}^{n}$, and $\operatorname{SAT}(F)$ is the set of these assignments. We measure time in the word-RAM model, and “polynomial” means polynomial in the input length.

References

1. [2]Scott Aaronson. Podcasts about the topic: Part II. Shtetl-Optimized, October 26, 2026, comment #31 of October 27, 2026. https://scottaaronson.blog/?p=10239, 2026.
2. [3]Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, and Toniann Pitassi. The complexity of properly learning simple concept classes. Journal of Computer and System Sciences, 74(1):16–34, 2008.DOI
3. [4]Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge. Subquadratic high-dimensional hierarchical clustering. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
4. [5]Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart. Connecting knowledge compilation classes and width parameters. Theory of Computing Systems, 64(5):861–914, 2020.DOI
5. [6]Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. Algorithms and hardness for linear algebra on geometric graphs. In 61st IEEE Symposium on Foundations of Computer Science (FOCS), pages 541–552, 2020.arxiv.org/abs/2011.02466
6. [7]Josh Alman, Timothy M. Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In 57th IEEE Symposium on Foundations of Computer Science (FOCS), pages 467–476, 2016.arxiv.org/abs/1608.04355
7. [8]Sanjeev Arora, Rong Ge, Ravi Kannan, and Ankur Moitra. Computing a nonnegative matrix factorization – provably. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 2012.
8. [9]Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor network complexity of multilinear maps. Theory of Computing, 18(16):1–54, 2022.
9. [10]Vikraman Arvind, Johannes Köbler, and Wolfgang Lindner. Parameterized learnability of k-juntas and related problems. In Algorithmic Learning Theory (ALT), Lecture Notes in Computer Science, pages 120–134, 2007.DOI
10. [11]Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow. Training neural networks is ER-complete. In Advances in Neural Information Processing Systems 34 (NeurIPS), pages 18293–18306, 2021.DOI
11. [12]Emmanuel Abbe, Shuangping Li, and Allan Sly. Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster. In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 860–873, 2022.arxiv.org/abs/2111.03084
12. [13]Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In 58th IEEE Symposium on Foundations of Computer Science (FOCS), pages 25–36, 2017.arxiv.org/abs/1706.06407
13. [14]Josh Alman and Zhao Song. Fast attention requires bounded entries. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 63117–63135, 2023.arxiv.org/abs/2302.13214
14. [15]Josh Alman and Zhao Song. The fine-grained complexity of gradient computation for training large language models. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 61419–61454, 2024.arxiv.org/abs/2402.04497
15. [16]Josh Alman and Zhao Song. How to capture higher-order correlations? Generalizing matrix softmax attention to Kronecker computation. In International Conference on Learning Representations (ICLR), pages 4306–4333, 2024.
16. [17]Josh Alman and Virginia Vassilevska Williams. OV graphs are (probably) hard instances. In 11th Innovations in Theoretical Computer Science Conference (ITCS), volume 151 of LIPIcs, pages 83:1–83:18, 2020.DOI
17. [18]Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 377–391, 2016.
18. [19]Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In International Conference on Learning Representations (ICLR), pages 47475–47498, 2025.arxiv.org/abs/2410.04271
19. [20]Karl Bringmann, Alejandro Cassis, Nick Fischer, and Marvin Künnemann. A structural investigation of the approximability of polynomial-time problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 of LIPIcs, pages 30:1–30:20, 2022.
20. [21]Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. A strongly exponential separation of DNNFs from CNF formulas. arXiv:1411.1995, 2014.arxiv.org/abs/1411.1995
21. [22]Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. Knowledge compilation meets communication complexity. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 1008–1013, 2016.
22. [23]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam’s razor. Information Processing Letters, 24(6):377–380, 1987.
23. [24]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik–Chervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989.DOI
24. [25]J. M. Barzdin and R. V. Freivald. On the prediction of general recursive functions. Doklady Akademii Nauk SSSR, 206(3):521–524, 1972. English translation in Soviet Mathematics Doklady 13:1224–1228.
25. [26]Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar, and Saket Saurabh. Exponential-time approximation (schemes) for vertex-ordering problems. In 16th Innovations in Theoretical Computer Science Conference (ITCS), volume 325 of LIPIcs, pages 15:1–15:18, 2025.arxiv.org/abs/2502.10909
26. [27]Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. A note on exact algorithms for vertex ordering problems on graphs. Theory of Computing Systems, 50(3):420–432, 2012.DOI
27. [28]Cornelius Brand, Robert Ganian, and Kirill Simonov. A parameterized theory of PAC learning. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, volume 37, pages 6834–6841, 2023.
28. [29]Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is ∃R-complete. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 36222–36237, 2023.
29. [30]Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The traveling salesman problem in bounded degree graphs. ACM Transactions on Algorithms, 8(2):18:1–18:13, 2012.DOI
30. [31]Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks. In Advances in Neural Information Processing Systems 30 (NIPS), pages 4308–4318, 2017.
31. [32]Andreas Björklund. Determinant sums for undirected Hamiltonicity. SIAM Journal on Computing, 43(1):280–299, 2014.
32. [33]Guy Blanc, Caleb Koch, Carmen Strassle, and Li-Yang Tan. Computational-statistical tradeoffs from NP-hardness. In 66th IEEE Symposium on Foundations of Computer Science (FOCS), pages 512–530, 2025.arxiv.org/abs/2507.13222
33. [34]Guy Blanc, Jane Lange, Mingda Qiao, and Li-Yang Tan. Properly learning decision trees in almost polynomial time. In 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 920–929, 2021.
34. [36]Mitali Bafna, Dor Minzer, Nikhil Vyas, and Zhiwei Yun. Quasi-linear size PCPs with small soundness from HDX. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 45–53, 2025.arxiv.org/abs/2407.12762
35. [37]Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (ITCS), pages 97–110, 2013.arxiv.org/abs/1402.2224
36. [38]Avrim Blum and Ronald L. Rivest. Training a 3-node neural network is NP-complete. Neural Networks, 5(1):117–127, 1992.
37. [39]Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551–607, 2008.
38. [41]Arturs Backurs and Christos Tzamos. Improving Viterbi is hard: better runtimes imply faster clique algorithms. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70 of PMLR, pages 311–321, 2017.arxiv.org/abs/1607.04229
39. [42]Mark Bun and Mark Zhandry. Order-revealing encryption and the hardness of private learning. In Theory of Cryptography (TCC), Lecture Notes in Computer Science, pages 176–206, 2016.DOI
40. [43]Vincent Cohen-Addad, Karthik C. S., David Saulpic, and Chris Schwiegelshohn. Almost-optimal upper and lower bounds for clustering in low dimensional Euclidean spaces. In 42nd International Symposium on Computational Geometry (SoCG), volume 367 of LIPIcs, pages 34:1–34:16, 2026.
41. [44]Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman. The bane of low-dimensionality clustering. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018.
42. [45]Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem. Journal of the ACM, 63(5):40:1–40:65, 2016.
43. [47]Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Transactions on Algorithms, 12(3):41:1–41:24, 2016.
44. [48]Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socała. Tight lower bounds on graph embedding problems. Journal of the ACM, 64(3):18:1–18:22, 2017.arxiv.org/abs/1602.05016
45. [49]Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (ITCS), pages 261–270, 2016.
46. [50]Xiangle Chen. Exact algorithms and complexity of the smallest grammar problem. arXiv:2610.32298v2, October 27, 2026, 2026.arxiv.org/abs/2610.32298
47. [51]Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A duality between clause width and clause density for SAT. In 21st Annual IEEE Conference on Computational Complexity (CCC), pages 252–260, 2006.DOI
48. [52]Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings. Journal of the ACM, 65(3):12:1–12:46, 2018.
49. [53]Clément L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 15676–15688, 2020.DOI
50. [54]Jianer Chen and Yang Liu. An improved SAT algorithm in terms of formula length. In Algorithms and Data Structures (WADS), volume 5664 of Lecture Notes in Computer Science, pages 144–155, 2009.DOI
51. [55]Claude (Anthropic). A 2^{o(n)} time algorithm for 3-SAT. Hexagon preprint hexagon:2610.00577v1, dated October 26, 2026. https://hexagonmath.org/2610.00577v1. Lean development at https://github.com/anthropics/formal-math/tree/main/eth, 2026.
52. [56]Lijie Chen, Ron D. Rothblum, Roei Tell, and Eylon Yogev. On exponential-time hypotheses, derandomization, and circuit lower bounds. Journal of the ACM, 70(4):1–62, 2023.
53. [58]William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. Journal of Artificial Intelligence Research, 10:243–270, 1999.
54. [59]Timothy M. Chan and R. Ryan Williams. Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov–Smolensky. ACM Transactions on Algorithms, 17(1):2:1–2:14, 2021.
55. [60]Huairui Chu, Mingyu Xiao, and Zhe Zhang. An improved upper bound for SAT. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, volume 35, pages 3707–3714, 2021.
56. [61]Jeffrey M. Dudek, Leonardo Dueñas-Osorio, and Moshe Y. Vardi. Efficient contraction of large tensor networks for weighted model counting through graph decompositions. arXiv:1908.04381, 2019.arxiv.org/abs/1908.04381
57. [62]Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Transactions on Algorithms, 10(4):21:1–21:32, 2014.
58. [63]Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM, 54(3):12:1–12:44, 2007.DOI
59. [64]Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), TR16-128, 2016.
60. [65]Ilias Diakonikolas, Daniel M. Kane, and Pasin Manurangsi. Nearly tight bounds for robust proper learning of halfspaces with a margin. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.arxiv.org/abs/1908.11335
61. [66]Ilias Diakonikolas, Daniel M. Kane, and Pasin Manurangsi. The complexity of adversarially robust proper learning of halfspaces with agnostic noise. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 20449–20461, 2020.arxiv.org/abs/2007.15220
62. [67]Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. More data speeds up training time in learning halfspaces over sparse vectors. In Advances in Neural Information Processing Systems 26 (NIPS), 2013.arxiv.org/abs/1311.2271
63. [68]Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 381–390, 2009.
64. [69]Florent Foucaud, Harmender Gahlawat, Fionn Mc Inerney, and Prafullkumar Tale. The parameterized complexity of computing the VC-dimension. Advances in Neural Information Processing Systems 38 (NeurIPS); arXiv:2510.17451, 2025.arxiv.org/abs/2510.17451
65. [70]Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of ReLU network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775–1790, 2022.DOI
66. [71]Jacob Focke, Dániel Marx, and Paweł Rzążewski. Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.
67. [72]Yoav Freund, H. Sebastian Seung, Eli Shamir, and Naftali Tishby. Selective sampling using the query by committee algorithm. Machine Learning, 28(2–3):133–168, 1997.
68. [73]Ran Gilad-Bachrach, Amir Navot, and Naftali Tishby. Query by committee made real. In Advances in Neural Information Processing Systems 18 (NIPS), 2005.
69. [74]Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties on sparse structures with algorithmic applications. ACM Transactions on Algorithms, 15(2), 2019.
70. [75]Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training depth-2 ReLU networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS), volume 185 of LIPics, pages 22:1–22:14, 2021.arxiv.org/abs/2011.13550
71. [76]Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory, Series B, 99(1):218–228, 2009.DOI
72. [77]Sally A. Goldman, Ronald L. Rivest, and Robert E. Schapire. Learning binary relations and total orders. SIAM Journal on Computing, 22(5):1006–1034, 1993.
73. [78]Géza Györgyi. First-order transition to perfect generalization in a neural network with binary synapses. Physical Review A, 41(12):7097–7100, 1990.pubmed.ncbi.nlm.nih.gov/9903140
74. [79]Edward A. Hirsch. New worst-case upper bounds for SAT. Journal of Automated Reasoning, 24(4):397–420, 2000.DOI
75. [80]Shuichi Hirahara. NP-hardness of learning programs and partial MCSP. In 63rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 968–979, 2022.DOI
76. [81]Haym Hirsh, Nina Mishra, and Leonard Pitt. Version spaces and the consistency problem. Artificial Intelligence, 156(2):115–138, 2004.DOI
77. [82]Rahul Ilango. Constant depth formula and partial function versions of MCSP are hard. In 61st IEEE Symposium on Foundations of Computer Science (FOCS), pages 424–433, 2020.
78. [83]Rahul Ilango. The minimum formula size problem is (ETH) hard. In 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 427–432, 2021.
79. [84]Christina Ilvento. Implementing the exponential mechanism with base-2 differential privacy. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 717–742, 2020.arxiv.org/abs/1912.04222
80. [85]Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC⁰. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 961–972, 2012.
81. [86]Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367–375, 2001.DOI
82. [87]Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530, 2001.
83. [88]Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188, 1986.DOI
84. [89]Johan Kwisthout and Hans L. Bodlaender. Conditional lower bounds on the complexity of probabilistic inference. Technical Report UU-CS-2009-018, Department of Information and Computing Sciences, Utrecht University, 2009.
85. [90]Johan Kwisthout, Hans L. Bodlaender, and Linda C. van der Gaag. The necessity of bounded treewidth for efficient inference in Bayesian networks. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI), pages 237–242, 2010.DOI
86. [91]Stefanos Kourtis, Claudio Chamon, Eduardo Mucciolo, and Andrei E. Ruckenstein. Fast counting with tensor networks. SciPost Physics, 7(5):060, 2019.DOI
87. [92]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011.
88. [94]Marek Karpinski and Warren Schudy. Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, pages 3–14, 2010.arxiv.org/abs/1006.4396
89. [95]Caleb Koch, Carmen Strassle, and Li-Yang Tan. Properly learning decision trees with queries is NP-hard. In 64th IEEE Symposium on Foundations of Computer Science (FOCS), pages 2383–2407, 2023.arxiv.org/abs/2307.04093
90. [96]Caleb Koch, Carmen Strassle, and Li-Yang Tan. Superpolynomial lower bounds for decision tree learning and testing. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1962–1994, 2023.arxiv.org/abs/2210.06375
91. [97]Caleb Koch, Carmen Strassle, and Li-Yang Tan. Fast decision tree learning solves hard coding-theoretic problems. In 65th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1893–1910, 2024.arxiv.org/abs/2409.13096
92. [98]Feyza Duman Keles, Pruthuvi Mahesakya Wijewardena, and Chinmay Hegde. On the computational complexity of self-attention. In International Conference on Algorithmic Learning Theory (ALT), volume 201 of PMLR, pages 597–619, 2023.arxiv.org/abs/2209.04881
93. [99]Leslie Lamport. How to write a proof. The American Mathematical Monthly, 102(7):600–608, 1995.DOI
94. [100]Leslie Lamport. How to write a 21st century proof. Journal of Fixed Point Theory and Applications, 11(1):43–63, 2012.DOI
95. [101]Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4):285–318, 1988.
96. [102]Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Transactions on Algorithms, 14(2):13:1–13:30, 2018.
97. [103]Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM Journal on Computing, 47(3):675–702, 2018.
98. [104]Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1236–1252, 2018.arxiv.org/abs/1712.08147
99. [105]Pasin Manurangsi. Improved inapproximability of VC dimension and Littlestone’s dimension via (unbalanced) biclique. In 14th Innovations in Theoretical Computer Science Conference (ITCS), volume 251 of LIPIcs, pages 85:1–85:18, 2023.arxiv.org/abs/2211.01443
100. [106]Pasin Manurangsi. Almost-polynomial ratio Almost-ETH-hardness of approximating densest k-subgraph. arXiv:1611.05991v3, version of October 27, 2026, 2026.
101. [107]Dániel Marx. Can you beat treewidth? Theory of Computing, 6:85–112, 2010.
102. [108]Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense CSPs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP), volume 80 of LIPIcs, pages 78:1–78:15, 2017.arxiv.org/abs/1607.02986
103. [109]Pasin Manurangsi and Aviad Rubinstein. Inapproximability of VC dimension and Littlestone’s dimension. In Proceedings of the 30th Conference on Learning Theory (COLT), volume 65 of PMLR, pages 1432–1460, 2017.arxiv.org/abs/1705.09517
104. [110]Igor L. Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing, 38(3):963–981, 2008.DOI
105. [111]Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th IEEE Symposium on Foundations of Computer Science (FOCS), pages 94–103, 2007.
106. [113]OpenAI. The Exponential Time Hypothesis is false. OpenAI Math Release preprint, dated October 17, 2026, revised October 25, 2026, released October 26, 2026. https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf, 2026.
107. [114]OpenAI. Scope of the Lean formalization for “The Exponential Time Hypothesis is false”. https://github.com/openai/math/blob/main/lean/docs/378.md, 2026.
108. [115]Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM, 35(4):965–984, 1988.DOI
109. [116]Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1065–1075, 2010.
110. [117]Junqiang Peng and Mingyu Xiao. Further improvements for SAT in terms of formula length. Information and Computation, 294:105085, 2023.
111. [118]Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC), pages 1260–1268, 2018.arxiv.org/abs/1803.00904
112. [119]Rainer Schuler. An algorithm for the satisfiability problem of formulas in conjunctive normal form. Journal of Algorithms, 54(1):40–44, 2005.DOI
113. [120]Richard E. Stearns and Harry B. Hunt III. Power indices and easier hard problems. Mathematical Systems Theory, 23:209–225, 1990.DOI
114. [121]H. Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory (COLT), pages 287–294, 1992.
115. [123]Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
116. [124]H. Sebastian Seung, Haim Sompolinsky, and Naftali Tishby. Statistical mechanics of learning from examples. Physical Review A, 45(8):6056–6091, 1992.pubmed.ncbi.nlm.nih.gov/9907706
117. [125]Rodrigo Toro Icarte, León Illanes, Margarita P. Castro, Andre A. Cire, Sheila A. McIlraith, and J. Christopher Beck. Training binarized neural networks using MIP and CP. In Principles and Practice of Constraint Programming (CP), Lecture Notes in Computer Science, pages 401–417, 2019.DOI
118. [126]Jonathan Ullman. Answering n^{2+o(1)} counting queries with differential privacy is hard. SIAM Journal on Computing, 45(2):473–496, 2016.
119. [127]Nikhil Vyas and Ryan Williams. On super strong ETH. Journal of Artificial Intelligence Research, 70:473–495, 2021.
120. [128]Magnus Wahlström. An algorithm for the SAT problem for formulae of linear length. In Algorithms – ESA 2005, volume 3669 of Lecture Notes in Computer Science, pages 107–118, 2005.DOI
121. [129]Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: posterior sampling and stochastic gradient Monte Carlo. In Proceedings of the 32nd International Conference on Machine Learning (ICML), volume 37 of PMLR, pages 2493–2502, 2015.DOI
122. [130]Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2–3):357–365, 2005.DOI