HEXAGONbeta

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

Primarily AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithmscs.AI — Artificial Intelligencecs.CC — Computational Complexity

Contributed by Xiaoyu Li ↗

Version 1 / Oct 29, 2026 / CC BY 4.0

Abstract

Two recent works by OpenAI and Anthropic refuted the Exponential Time Hypothesis (ETH). They count the satisfying assignments of a kk-CNF on nn variables in time 2n/(log⁡n)1/2−o(1)2^{n/(\log n)^{1/2-o(1)}}. Many fine-grained lower bounds in learning theory rest on ETH and its relatives. We determine what the refutation changes for learning. The answer is a locality principle: the new algorithms speed up learning when each labeled example constrains few bits of the hypothesis, and under the CNF form of the Strong Exponential Time Hypothesis, which survives, the speed-up ends at Θ(log⁡N)\Theta(\log N) bits. Three transitions make the principle precise. Locality. Call a class with NN-bit descriptions κ\kappa-local if each label depends on at most κ\kappa description bits, as for quantized models on sparse data. Then proper PAC learning, exact version-space counting and sampling, and the halving algorithm run in time poly(m)⋅2o(N)\mathrm{poly}(m)\cdot 2^{o(N)} on samples of size mm for κ=o((log⁡N)1/4/log⁡log⁡N)\kappa=o((\log N)^{1/4}/\sqrt{\log\log N}), and proper PAC learning at constant accuracy does so for κ=o(log⁡N)\kappa=o(\sqrt{\log N}). At inverse-polynomial accuracy, proper learning of κ\kappa-local classes is equivalent to κ\kappa-SAT, up to a factor 22 in the locality. Under CNF-SETH, consistency for binarized perceptrons on O(log⁡N)O(\log N)-sparse data needs time 2(1−γ)N2^{(1-\gamma)N} for every γ>0\gamma>0. Accuracy. Exact empirical risk minimization, proper agnostic learning and the exponential mechanism reduce to tensor contractions over a truncated polynomial ring. As a consequence, the Sparse Max-SAT Hypotheses of Alman and Vassilevska Williams are false. At constant accuracy, proper learning is SAT parameterized by formula length. With quasi-linear PCPs this gives a 2N/polylog N2^{N/\mathrm{polylog}\,N} lower bound under a length form of ETH, which replaces Gap-ETH for reductions of quasi-linear size. At accuracy N−3/8N^{-3}/8, the Max-3-SAT Hypothesis forces time 2(1−o(1))N2^{(1-o(1))N}. Treewidth. Exact inference in graphical models of bounded degree and arity takes time 2O(n/log⁡n)2^{O(n/\sqrt{\log n})}. On expanders this beats every elimination order and every structured DNNF. Under #\#CNF-SETH, time 2(1−γ)tw2^{(1-\gamma)\mathrm{tw}} is again necessary once a model may have twO(1)\mathrm{tw}^{O(1)} variables. We also take stock of the conditional lower bounds of learning theory: which ones fall, and which ones survive on which hypothesis. The next obstacle is a permutation problem. On difference vectors ei−eje_i-e_j, empirical risk minimization for real-valued halfspaces is weighted Feedback Arc Set, which the new algorithms do not reach.

Provenance statement

This work was produced on 28–29 October 2026 with Claude Opus 5.5 (Anthropic), working as an agent in Claude Code. The submitting contributor posed the question of what the refutation of the Exponential Time Hypothesis means for learning theory, directed the presentation, and chose the title. Claude chose the results, proved them, wrote the text and drew the figures. Separate Claude agents searched the literature and checked the citations, audited the proofs, and reviewed the paper as referees; the paper was revised after each audit. The constructions were tested by brute force on small random instances, and the elementary asymptotic estimates were checked with SymPy. The paper uses the algorithms of the two refutations, by OpenAI and by Anthropic, as black boxes, quoted as Imported Theorems.

Tools used

Anthropic
Claude OpusVersion 5.5

References

  1. Amol Aggarwal and Josh Alman. Optimal-degree polynomial approximations for exponentials and G aussian kernel density estimation. In 37th Computational Complexity Conference (CCC) , volume 234 of LIPIcs , pages 22:1--22:23, 2022.
  2. Scott Aaronson. Podcasts about the topic: P art II . Shtetl-Optimized, October 26, 2026, comment #31 of October 27, 2026. https://scottaaronson.blog/?p=10239, 2026.link
  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.
  4. Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge. Subquadratic high-dimensional hierarchical clustering. In Advances in Neural Information Processing Systems 32 (NeurIPS) , 2019.
  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.
  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.
  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.
  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.
  9. Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor network complexity of multilinear maps. Theory of Computing , 18(16):1--54, 2022.
  10. Vikraman Arvind, Johannes K ö bler, and Wolfgang Lindner. Parameterized learnability of kk-juntas and related problems. In Algorithmic Learning Theory (ALT) , Lecture Notes in Computer Science, pages 120--134, 2007.
Show all 130 referencesShow fewer references
  1. 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.
  2. 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.
  3. 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.
  4. Josh Alman and Zhao Song. Fast attention requires bounded entries. In Advances in Neural Information Processing Systems 36 (NeurIPS) , pages 63117--63135, 2023.
  5. 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.
  6. Josh Alman and Zhao Song. How to capture higher-order correlations? G eneralizing matrix softmax attention to K ronecker computation. In International Conference on Learning Representations (ICLR) , pages 4306--4333, 2024.
  7. 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.
  8. 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.
  9. Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In International Conference on Learning Representations (ICLR) , pages 47475--47498, 2025.
  10. 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.
  11. Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. A strongly exponential separation of DNNF s from CNF formulas. arXiv:1411.1995, 2014.arXiv
  12. 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.
  13. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam's razor. Information Processing Letters , 24(6):377--380, 1987.
  14. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the V apnik-- C hervonenkis dimension. Journal of the ACM , 36(4):929--965, 1989.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber. Training fully connected neural networks is ∃R\exists\mathbb{R}-complete. In Advances in Neural Information Processing Systems 36 (NeurIPS) , pages 36222--36237, 2023.
  20. 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.
  21. 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.
  22. Andreas Bj ö rklund. Determinant sums for undirected H amiltonicity. SIAM Journal on Computing , 43(1):280--299, 2014.
  23. 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.
  24. 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.
  25. Paul Beame, Jerry Li, Sudeepa Roy, and Dan Suciu. Lower bounds for exact model counting and applications in probabilistic databases. In Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence (UAI) , pages 52--61, 2013.
  26. 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.
  27. 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.
  28. Avrim Blum and Ronald L. Rivest. Training a 3-node neural network is NP -complete. Neural Networks , 5(1):117--127, 1992.
  29. Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing , 38(2):551--607, 2008.
  30. Teodora Baluta, Shiqi Shen, Shweta Shinde, Kuldeep S. Meel, and Prateek Saxena. Quantitative verification of neural networks and its security applications. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (CCS) , pages 1249--1264, 2019.
  31. Arturs Backurs and Christos Tzamos. Improving V iterbi 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.
  32. 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.
  33. Vincent Cohen-Addad, Karthik C. S. , David Saulpic, and Chris Schwiegelshohn. Almost-optimal upper and lower bounds for clustering in low dimensional E uclidean spaces. In 42nd International Symposium on Computational Geometry (SoCG) , volume 367 of LIPIcs , pages 34:1--34:16, 2026.
  34. 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.
  35. Chandra Chekuri and Julia Chuzhoy. Polynomial bounds for the grid-minor theorem. Journal of the ACM , 63(5):40:1--40:65, 2016.
  36. Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan. From Gap-Exponential Time Hypothesis to fixed parameter tractable inapproximability: C lique, D ominating S et, and more. SIAM Journal on Computing , 49(4):772--810, 2020.
  37. 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.
  38. 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.
  39. 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.
  40. Xiangle Chen. Exact algorithms and complexity of the smallest grammar problem. arXiv:2610.32298v2, October 27, 2026, 2026.arXiv
  41. 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.
  42. Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast H amiltonicity checking via bases of perfect matchings. Journal of the ACM , 65(3):12:1--12:46, 2018.
  43. Cl é ment L. Canonne, Gautam Kamath, and Thomas Steinke. The discrete G aussian for differential privacy. In Advances in Neural Information Processing Systems 33 (NeurIPS) , pages 15676--15688, 2020.
  44. 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.
  45. Claude (Anthropic) . A 2o(n)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.hexagon
  46. 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.
  47. Venkat Chandrasekaran, Nathan Srebro, and Prahladh Harsha. Complexity of inference in graphical models. In Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence (UAI) , pages 70--78, 2008.
  48. William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. Journal of Artificial Intelligence Research , 10:243--270, 1999.
  49. Timothy M. Chan and R. Ryan Williams. Deterministic APSP , orthogonal vectors, and more: quickly derandomizing R azborov-- S molensky. ACM Transactions on Algorithms , 17(1):2:1--2:14, 2021.
  50. 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.
  51. 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
  52. Holger Dell, Thore Husfeldt, D á niel Marx, Nina Taslaman, and Martin Wahl é n. Exponential time complexity of the permanent and the T utte polynomial. ACM Transactions on Algorithms , 10(4):21:1--21:32, 2014.
  53. Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM , 54(3):12:1--12:44, 2007.
  54. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (ECCC), TR16-128, 2016.
  55. 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.
  56. 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.
  57. 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.
  58. 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.
  59. 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
  60. 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.
  61. 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.
  62. 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.
  63. Ran Gilad-Bachrach, Amir Navot, and Naftali Tishby. Query by committee made real. In Advances in Neural Information Processing Systems 18 (NIPS) , 2005.
  64. 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.
  65. 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.
  66. Martin Grohe and D á niel Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory, Series B , 99(1):218--228, 2009.
  67. 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.
  68. 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.
  69. Edward A. Hirsch. New worst-case upper bounds for SAT . Journal of Automated Reasoning , 24(4):397--420, 2000.
  70. Shuichi Hirahara. NP -hardness of learning programs and partial MCSP . In 63rd IEEE Symposium on Foundations of Computer Science (FOCS) , pages 968--979, 2022.
  71. Haym Hirsh, Nina Mishra, and Leonard Pitt. Version spaces and the consistency problem. Artificial Intelligence , 156(2):115--138, 2004.
  72. 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.
  73. Rahul Ilango. The minimum formula size problem is ( ETH ) hard. In 62nd IEEE Symposium on Foundations of Computer Science (FOCS) , pages 427--432, 2021.
  74. 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.
  75. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC 0^0. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 961--972, 2012.
  76. Russell Impagliazzo and Ramamohan Paturi. On the complexity of kk- SAT . Journal of Computer and System Sciences , 62(2):367--375, 2001.
  77. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512--530, 2001.
  78. 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.
  79. 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.
  80. Johan Kwisthout, Hans L. Bodlaender, and Linda C. van der Gaag. The necessity of bounded treewidth for efficient inference in B ayesian networks. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI) , pages 237--242, 2010.
  81. Stefanos Kourtis, Claudio Chamon, Eduardo Mucciolo, and Andrei E. Ruckenstein. Fast counting with tensor networks. SciPost Physics , 7(5):060, 2019.
  82. 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.
  83. Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2o~(n1/3)2^{\tilde{o}(n^{1/3})}. Journal of Computer and System Sciences , 68(2):303--318, 2004.
  84. Marek Karpinski and Warren Schudy. Faster algorithms for feedback arc set tournament, K emeny rank aggregation and betweenness tournament. In Algorithms and Computation (ISAAC) , Lecture Notes in Computer Science, pages 3--14, 2010.
  85. 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.
  86. 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.
  87. 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.
  88. 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.
  89. Leslie Lamport. How to write a proof. The American Mathematical Monthly , 102(7):600--608, 1995.
  90. Leslie Lamport. How to write a 21st century proof. Journal of Fixed Point Theory and Applications , 11(1):43--63, 2012.
  91. Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning , 2(4):285--318, 1988.
  92. 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.
  93. Daniel Lokshtanov, D á niel Marx, and Saket Saurabh. Slightly superexponential parameterized problems. SIAM Journal on Computing , 47(3):675--702, 2018.
  94. 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.
  95. Pasin Manurangsi. Improved inapproximability of VC dimension and L ittlestone's dimension via (unbalanced) biclique. In 14th Innovations in Theoretical Computer Science Conference (ITCS) , volume 251 of LIPIcs , pages 85:1--85:18, 2023.
  96. Pasin Manurangsi. Almost-polynomial ratio Almost-ETH -hardness of approximating densest kk-subgraph. arXiv:1611.05991v3, version of October 27, 2026, 2026.arXiv
  97. D á niel Marx. Can you beat treewidth? Theory of Computing , 6:85--112, 2010.
  98. 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.
  99. Pasin Manurangsi and Aviad Rubinstein. Inapproximability of VC dimension and L ittlestone's dimension. In Proceedings of the 30th Conference on Learning Theory (COLT) , volume 65 of PMLR , pages 1432--1460, 2017.
  100. Igor L. Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing , 38(3):963--981, 2008.
  101. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 94--103, 2007.
  102. Nina Narodytska, Shiva Kasiviswanathan, Leonid Ryzhyk, Mooly Sagiv, and Toby Walsh. Verifying properties of binarized deep neural networks. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence , 2018.
  103. OpenAI . The E xponential T ime H ypothesis 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.link
  104. OpenAI . Scope of the L ean formalization for `` T he E xponential T ime H ypothesis is false''. https://github.com/openai/math/blob/main/lean/docs/378.md, 2026.link
  105. Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM , 35(4):965--984, 1988.
  106. 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.
  107. Junqiang Peng and Mingyu Xiao. Further improvements for SAT in terms of formula length. Information and Computation , 294:105085, 2023.
  108. 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.
  109. Rainer Schuler. An algorithm for the satisfiability problem of formulas in conjunctive normal form. Journal of Algorithms , 54(1):40--44, 2005.
  110. Richard E. Stearns and Harry B. Hunt III . Power indices and easier hard problems. Mathematical Systems Theory , 23:209--225, 1990.
  111. 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.
  112. Marko Samer and Stefan Szeider. Algorithms for propositional model counting. Journal of Discrete Algorithms , 8(1):50--64, 2010.
  113. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms . Cambridge University Press, 2014.
  114. H. Sebastian Seung, Haim Sompolinsky, and Naftali Tishby. Statistical mechanics of learning from examples. Physical Review A , 45(8):6056--6091, 1992.
  115. 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.
  116. Jonathan Ullman. Answering n2+o(1)n^{2+o(1)} counting queries with differential privacy is hard. SIAM Journal on Computing , 45(2):473--496, 2016.
  117. Nikhil Vyas and Ryan Williams. On super strong ETH . Journal of Artificial Intelligence Research , 70:473--495, 2021.
  118. 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.
  119. Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: posterior sampling and stochastic gradient M onte C arlo. In Proceedings of the 32nd International Conference on Machine Learning (ICML) , volume 37 of PMLR , pages 2493--2502, 2015.
  120. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science , 348(2--3):357--365, 2005.

Version history

  1. v1Submitted by Xiaoyu LiInitial depositCurrentOct 28, 2026