References

All works cited in the paper. Each section page also lists the works it cites at its end.

Adler, Robert J., and Jonathan E. Taylor. 2007. Random Fields and Geometry. Springer Monographs in Mathematics. Springer. https://doi.org/10.1007/978-0-387-48116-6.

Alon, Noga. 1997. “On the Edge-Expansion of Graphs.” Combinatorics, Probability and Computing 6 (2): 145–52. https://doi.org/10.1017/S096354839700299X.

Amanov, Alimzhan, Maxim van den Berg, and Jeroen Zuiddam. 2026. “Multiplying Matrices via Polynomials: Exposition and Barriers.” arXiv:2610.30054. https://arxiv.org/abs/2610.30054.

Backhausz, Ágnes, Balázs Szegedy, and Bálint Virág. 2015. “Ramanujan Graphings and Correlation Decay in Local Algorithms.” Random Structures & Algorithms 47 (3): 424–35. https://doi.org/10.1002/RSA.20562.

Balitskiy, Alexey, Roman Karasev, and Alexander Tsigler. 2017. “Optimality of Codes with Respect to Error Probability in Gaussian Noise.” https://arxiv.org/abs/1701.07986v1.

Berendsohn, Benjamin Aram, László Kozma, and Dániel Marx. 2021. “Finding and Counting Permutations via CSPs.” Algorithmica 83 (8): 2552–77. https://doi.org/10.1007/S00453-021-00812-Z.

Björklund, Andreas, Thore Husfeldt, and Mikko Koivisto. 2009. “Set Partitioning via Inclusion-Exclusion.” SIAM Journal on Computing 39 (2): 546–63. https://doi.org/10.1137/070683933.

Bodlaender, Hans L. 1998. “A Partial k-Arboretum of Graphs with Bounded Treewidth.” Theoretical Computer Science 209 (1-2): 1–45. https://doi.org/10.1016/S0304-3975(97)00228-4.

Bodlaender, Hans L., Marek Cygan, Stefan Kratsch, and Jesper Nederlof. 2015. “Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth.” Information and Computation 243: 86–111. https://doi.org/10.1016/J.IC.2014.12.008.

Bojikian, Narek, Vera Chekan, Falko Hegerfeld, and Stefan Kratsch. 2022. “Tight Bounds for Connectivity Problems Parameterized by Cutwidth.” https://arxiv.org/abs/2212.12385v1.

Bojikian, Narek, Vera Chekan, and Stefan Kratsch. 2025. “Tight Bounds for Some Classical Problems Parameterized by Cutwidth.” https://arxiv.org/abs/2502.15884v1.

Bonnet, Édouard, Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik. 2019. “Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP.” In 27th Annual European Symposium on Algorithms, ESA 2019, Munich/Garching, Germany, September 9-11, 2019, edited by Michael A. Bender, Ola Svensson, and Grzegorz Herman, 144:23:1–14. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ESA.2019.23.

Böröczky, Károly, Jr. 2004. Finite Packing and Covering. Vol. 154. Cambridge Tracts in Mathematics. Cambridge University Press. https://doi.org/10.1017/CBO9780511546587.

Claude. 2026. “A \(2^{o(n)}\) Time Algorithm for 3-SAT.” Anthropic preprint, dated 26 October 2026, with a Lean 4 formalization, in the folder eth of the repository. https://github.com/anthropics/formal-math.

Croce, Federico Della, and Vangelis Th. Paschos. 2012. “Efficient Algorithms for the max \(k\)-vertex cover Problem.” In Theoretical Computer Science - 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, the Netherlands, September 26-28, 2012. Proceedings, edited by Jos C. M. Baeten, Thomas Ball, and Frank S. de Boer, 7604:295–309. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-33475-7_21.

Csóka, Endre, Balázs Gerencsér, Viktor Harangi, and Bálint Virág. 2015. “Invariant Gaussian Processes and Independent Sets on Regular Graphs of Large Girth.” Random Structures & Algorithms 47 (2): 284–303. https://doi.org/10.1002/RSA.20547.

Curticapean, Radu, Holger Dell, and Dániel Marx. 2017. “Homomorphisms Are a Good Basis for Counting Small Subgraphs.” In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, edited by Hamed Hatami, Pierre McKenzie, and Valerie King, 210–23. ACM. https://doi.org/10.1145/3055399.3055502.

Cygan, Marek, Łukasz Kowalik, and Arkadiusz Socała. 2019. “Improving TSP Tours Using Dynamic Programming over Tree Decompositions.” ACM Transactions on Algorithms 15 (4): 54:1–19. https://doi.org/10.1145/3341730.

Cygan, Marek, Stefan Kratsch, and Jesper Nederlof. 2012. “Fast Hamiltonicity Checking via Bases of Perfect Matchings.” https://arxiv.org/abs/1211.1506v1.

Cygan, Marek, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. 2011. “Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.” https://arxiv.org/abs/1103.0534v1.

De Ita Luna, Guillermo, J. Raymundo Marcial-Romero, Pedro Bello López, and Meliza Contreras González. 2026. “An Exact Algorithm for Counting the Number of Independent Sets of a Graph.” Mathematics 14 (2): 275. https://doi.org/10.3390/math14020275.

Diaz, Joaquin B., and Frederic T. Metcalf. 1963. “Stronger Forms of a Class of Inequalities of G. Pólya–G. Szegő, and L. V. Kantorovich.” Bulletin of the American Mathematical Society 69 (3): 415–18. https://doi.org/10.1090/S0002-9904-1963-10953-2.

Dı́az, Josep, Jordi Petit, and Maria J. Serna. 2002. “A Survey of Graph Layout Problems.” ACM Computing Surveys 34 (3): 313–56. https://doi.org/10.1145/568522.568523.

Dublois, Louis, Michael Lampis, and Vangelis Th. Paschos. 2022. “Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation.” Theoretical Computer Science 923: 271–91. https://doi.org/10.1016/J.TCS.2022.05.013.

Edwards, Keith J. 2016. “A Faster Polynomial-Space Algorithm for Max 2-CSP.” Journal of Computer and System Sciences 82 (3): 536–50. https://doi.org/10.1016/J.JCSS.2015.11.013.

Edwards, Keith, and Eric McDermid. 2015. “A General Reduction Theorem with Applications to Pathwidth and the Complexity of MAX 2-CSP.” Algorithmica 72 (4): 940–68. https://doi.org/10.1007/s00453-014-9883-7.

Ellis, John A., Ivan Hal Sudborough, and Jonathan S. Turner. 1994. “The Vertex Separation and Search Number of a Graph.” Information and Computation 113 (1): 50–79. https://doi.org/10.1006/INCO.1994.1064.

Erdős, Paul, and John L. Selfridge. 1973. “On a Combinatorial Game.” Journal of Combinatorial Theory, Series A 14 (3): 298–301. https://doi.org/10.1016/0097-3165(73)90005-8.

Feige, Uriel. 2000. “Approximating the Bandwidth via Volume Respecting Embeddings.” Journal of Computer and System Sciences 60 (3): 510–39. https://doi.org/10.1006/JCSS.1999.1682.

Fejes Tóth, László. 1950. “Extremum Properties of the Regular Polyhedra.” Canadian Journal of Mathematics 2: 22–31. https://doi.org/10.4153/CJM-1950-003-x.

Fomin, Fedor V., Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. 2009. “On Two Techniques of Combining Branching and Treewidth.” Algorithmica 54 (2): 181–207. https://doi.org/10.1007/s00453-007-9133-3.

Fomin, Fedor V., Fabrizio Grandoni, and Dieter Kratsch. 2005. “Some New Techniques in Design and Analysis of Exact (Exponential) Algorithms.” Bulletin of the EATCS 87: 47–77.

Fomin, Fedor V., and Kjartan Høie. 2006. “Pathwidth of Cubic Graphs and Exact Algorithms.” Information Processing Letters 97 (5): 191–96. https://doi.org/10.1016/j.ipl.2005.10.012.

Fomin, Fedor V., Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan M. M. van Rooij, and Ryan Williams. 2008. “08431 Open Problems – Moderately Exponential Time Algorithms.” In Moderately Exponential Time Algorithms, 19.10.–24.10.2008, edited by Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. Vol. 8431. Dagstuhl Seminar Proceedings. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany. https://doi.org/10.4230/DagSemProc.08431.3.

Fomin, Fedor V., and Dieter Kratsch. 2010. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer. https://doi.org/10.1007/978-3-642-16533-7.

Ganian, Robert, Ronald de Haan, Iyad A. Kanj, and Stefan Szeider. 2016. “On Existential MSO and Its Relation to ETH.” In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, 58:42:1–14. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2016.42.

Gaspers, Serge. 2010. Exponential Time Algorithms: Structures, Measures, and Bounds. VDM Verlag Dr. Müller.

———. 2026. “Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms: Code and Formal Proofs.” Companion website. https://doi.org/10.5281/zenodo.23883489.

Gaspers, Serge, and Edward J. Lee. 2016. “Faster Graph Coloring in Polynomial Space.” https://arxiv.org/abs/1607.06201v2.

———. 2023. “Faster Graph Coloring in Polynomial Space.” Algorithmica 85 (2): 584–609. https://doi.org/10.1007/S00453-022-01034-7.

Gaspers, Serge, and Gregory B. Sorkin. 2012. “A Universally Fastest Algorithm for Max 2-Sat, Max 2-CSP, and Everything in Between.” Journal of Computer and System Sciences 78 (1): 305–35. https://doi.org/10.1016/J.JCSS.2011.05.010.

———. 2014. “Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.” https://arxiv.org/abs/1404.0753v2.

———. 2017. “Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.” ACM Transactions on Algorithms 13 (4): 44:1–36. https://doi.org/10.1145/3111499.

Goemans, Michel X., and David P. Williamson. 1995. “Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming.” Journal of the ACM 42 (6): 1115–45. https://doi.org/10.1145/227683.227684.

Golovnev, Alexander, and Konstantin Kutzkov. 2014. “New Exact Algorithms for the 2-Constraint Satisfaction Problem.” Theoretical Computer Science 526: 18–27. https://doi.org/10.1016/J.TCS.2014.01.010.

Gowda, Kishen N., Aditya Lonkar, Fahad Panolan, Vraj Patel, and Saket Saurabh. 2024. “Improved FPT Algorithms for Deletion to Forest-Like Structures.” Algorithmica 86 (5): 1657–99. https://doi.org/10.1007/s00453-023-01206-z.

Harangi, Viktor, and Bálint Virág. 2015. “Independence Ratio and Random Eigenvectors in Transitive Graphs.” The Annals of Probability 43 (5): 2810–40. https://doi.org/10.1214/14-AOP952.

Impagliazzo, Russell, and Ramamohan Paturi. 2001. “On the Complexity of k-SAT.” Journal of Computer and System Sciences 62 (2): 367–75. https://doi.org/10.1006/JCSS.2000.1727.

Impagliazzo, Russell, Ramamohan Paturi, and Francis Zane. 2001. “Which Problems Have Strongly Exponential Complexity?” Journal of Computer and System Sciences 63 (4): 512–30. https://doi.org/10.1006/JCSS.2001.1774.

Johansson, Fredrik. 2017. “Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic.” IEEE Transactions on Computers 66 (8): 1281–92. https://doi.org/10.1109/TC.2017.2690633.

Kesten, Harry. 1959. “Symmetric Random Walks on Groups.” Transactions of the American Mathematical Society 92 (2): 336–54. https://doi.org/10.1090/S0002-9947-1959-0109367-6.

Kinnersley, Nancy G. 1992. “The Vertex Separation Number of a Graph Equals Its Path-Width.” Information Processing Letters 42 (6): 345–50. https://doi.org/10.1016/0020-0190(92)90234-M.

Kneis, Joachim, Daniel Mölle, Stefan Richter, and Peter Rossmanith. 2009. “A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms.” SIAM Journal on Discrete Mathematics 23 (1): 407–27. https://doi.org/10.1137/080715482.

Kowalik, Łukasz, and Konrad Majewski. 2020. “The Asymmetric Travelling Salesman Problem in Sparse Digraphs.” https://arxiv.org/abs/2007.12120v2.

Li, W. V., and Q.-M. Shao. 2001. “Gaussian Processes: Inequalities, Small Ball Probabilities and Applications.” In Stochastic Processes: Theory and Methods, 19:533–97. Handbook of Statistics. Elsevier. https://doi.org/10.1016/S0169-7161(01)19019-X.

Lichev, Lyuben, and Dieter Mitsche. 2023. “On the Minimum Bisection of Random 3-Regular Graphs.” The Electronic Journal of Combinatorics 30 (2): P2.40. https://doi.org/10.37236/11085.

Liu, Yuxi, and Mingyu Xiao. 2026. “Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than \(3^k\).” Information and Computation 309: 105406. https://doi.org/10.1016/J.IC.2026.105406.

Louis, Anand, Prasad Raghavendra, and Santosh S. Vempala. 2013. “The Complexity of Approximating Vertex Expansion.” In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Berkeley, CA, USA, October, 26-29, 2013, 360–69. IEEE Computer Society. https://doi.org/10.1109/FOCS.2013.46.

Lyons, Russell. 2017. “Factors of IID on Trees.” Combinatorics, Probability and Computing 26 (2): 285–300. https://doi.org/10.1017/S096354831600033X.

Makedon, Fillia, and Ivan Hal Sudborough. 1989. “On Minimizing Width in Linear Layouts.” Discrete Applied Mathematics 23 (3): 243–65. https://doi.org/10.1016/0166-218X(89)90016-4.

Monien, Burkhard, and Robert Preis. 2006. “Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs.” Journal of Discrete Algorithms 4 (3): 475–98. https://doi.org/10.1016/J.JDA.2005.12.009.

Mulgund, Abhijeet. 2026. “Stochastic Domination of Gaussian Maxima by the Regular Simplex.” https://arxiv.org/abs/2609.28452v2.

Nederlof, Jesper, Johan M. M. van Rooij, and Thomas C. van Dijk. 2014. “Inclusion/Exclusion Meets Measure and Conquer.” Algorithmica 69 (3): 685–740. https://doi.org/10.1007/S00453-013-9759-2.

Nilli, A. 1991. “On the Second Eigenvalue of a Graph.” Discrete Mathematics 91 (2): 207–10. https://doi.org/10.1016/0012-365X(91)90112-F.

OpenAI. 2026a. “An Upper Bound of \(9/4\) for the Matrix Multiplication Exponent.” OpenAI Math Release preprint, dated 2 October 2026, in the folder preprints/Matrix-Multiplication-Nine-Fourths-October-2-2026 of the repository. https://github.com/openai/math.

———. 2026b. “The Exponential Time Hypothesis Is False.” OpenAI Math Release preprint, dated 17 October 2026, revised 25 October 2026, in the folder preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026 of the repository. https://github.com/openai/math.

Owen, Donald B. 1956. “Tables for Computing Bivariate Normal Probabilities.” The Annals of Mathematical Statistics 27 (4): 1075–90. https://doi.org/10.1214/aoms/1177728074.

Pass, Rafael. 2026. “Matrix Multiplication from Polynomial Packings: A Constructive and Elementary Proof of \(\omega\le9/4\).” arXiv:2610.28627. https://arxiv.org/abs/2610.28627.

Plackett, R. L. 1954. “A Reduction Formula for Normal Multivariate Integrals.” Biometrika 41 (3-4): 351–60. https://doi.org/10.1093/biomet/41.3-4.351.

PVC (Research Infrastructure), UNSW Sydney. 2010. “Katana.” UNSW, Sydney. https://doi.org/10.26190/669X-A286.

Raghavan, Prabhakar. 1988. “Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs.” Journal of Computer and System Sciences 37 (2): 130–43. https://doi.org/10.1016/0022-0000(88)90003-7.

Rooij, Johan M. M. van. 2011. “Exact Exponential-Time Algorithms for Domination Problems in Graphs.” PhD thesis, Utrecht University. https://dspace.library.uu.nl/handle/1874/205442.

Rooij, Johan M. M. van, and Hans L. Bodlaender. 2012. “Exact Algorithms for Edge Domination.” Algorithmica 64 (4): 535–63. https://doi.org/10.1007/S00453-011-9546-X.

Rooij, Johan M. M. van, Hans L. Bodlaender, and Peter Rossmanith. 2009. “Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.” In Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, edited by Amos Fiat and Peter Sanders, 5757:566–77. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-04128-0_51.

Scott, Alexander D., and Gregory B. Sorkin. 2007. “Linear-Programming Design and Analysis of Fast Algorithms for Max 2-CSP.” Discrete Optimization 4 (3-4): 260–87. https://doi.org/10.1016/J.DISOPT.2007.08.001.

———. 2009. “Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function.” ACM Transactions on Algorithms 5 (4): 45:1–27. https://doi.org/10.1145/1597036.1597049.

Sheppard, W. F. 1899. “On the Application of the Theory of Error to Cases of Normal Distribution and Normal Correlation.” Philosophical Transactions of the Royal Society of London. Series A 192: 101–67. https://doi.org/10.1098/rsta.1899.0003.

Slepian, David. 1962. “The One-Sided Barrier Problem for Gaussian Noise.” Bell System Technical Journal 41 (2): 463–501. https://doi.org/10.1002/j.1538-7305.1962.tb02419.x.

Sullivan, Blair D., and Andrew van der Poel. 2016. “A Fast Parameterized Algorithm for Co-Path Set.” In 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, Aarhus, Denmark, August 24-26, 2016, edited by Jiong Guo and Danny Hermelin, 63:28:1–13. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.IPEC.2016.28.

Virtanen, Pauli, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, et al. 2020. “SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.” Nature Methods 17 (3): 261–72. https://doi.org/10.1038/s41592-019-0686-2.

Wahlström, Magnus. 2008. “A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances.” In Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings, edited by Martin Grohe and Rolf Niedermeier, 5018:202–13. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-540-79723-4_19.

Wikipedia contributors. 2026a. “Cubic Graph.” Wikipedia, The Free Encyclopedia, revision 1346173041. https://en.wikipedia.org/w/index.php?oldid=1346173041.

———. 2026b. “List of Unsolved Problems in Mathematics.” Wikipedia, The Free Encyclopedia, revision 1382281920. https://en.wikipedia.org/w/index.php?oldid=1382281920.

———. 2026c. “Pathwidth.” Wikipedia, The Free Encyclopedia, revision 1369812266. https://en.wikipedia.org/w/index.php?oldid=1369812266.

Williams, Ryan. 2005. “A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications.” Theoretical Computer Science 348 (2-3): 357–65. https://doi.org/10.1016/j.tcs.2005.09.023.

Woess, Wolfgang. 2000. Random Walks on Infinite Graphs and Groups. Vol. 138. Cambridge Tracts in Mathematics. Cambridge University Press. https://doi.org/10.1017/CBO9780511470967.

Yannakakis, Mihalis, and Fanica Gavril. 1980. “Edge Dominating Sets in Graphs.” SIAM Journal on Applied Mathematics 38 (3): 364–72. https://doi.org/10.1137/0138030.