references.bib

@inproceedings{karp1972,
  author    = {Richard M. Karp},
  title     = {Reducibility among Combinatorial Problems},
  booktitle = {Complexity of Computer Computations},
  publisher = {Plenum Press},
  year      = {1972},
  pages     = {85--103}
}

@inproceedings{cook1971,
  author    = {Stephen A. Cook},
  title     = {The Complexity of Theorem-Proving Procedures},
  booktitle = {Proceedings of the Third Annual ACM Symposium on Theory of Computing},
  year      = {1971},
  pages     = {151--158}
}

@book{garey1979,
  author    = {Michael R. Garey and David S. Johnson},
  title     = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
  publisher = {W. H. Freeman},
  year      = {1979}
}

@article{glover2019,
  author  = {Fred Glover and Gary Kochenberger and Yu Du},
  title   = {Quantum Bridge Analytics {I}: a tutorial on formulating and using {QUBO} models},
  journal = {4OR},
  volume  = {17},
  pages   = {335--371},
  year    = {2019},
  doi     = {10.1007/s10288-019-00424-y}
}

@article{lucas2014,
  author  = {Andrew Lucas},
  title   = {Ising formulations of many NP problems},
  journal = {Frontiers in Physics},
  volume  = {2},
  number  = {5},
  year    = {2014}
}

@article{barahona1982,
  author  = {Francisco Barahona},
  title   = {On the computational complexity of Ising spin glass models},
  journal = {Journal of Physics A: Mathematical and General},
  volume  = {15},
  number  = {10},
  pages   = {3241--3253},
  year    = {1982}
}

@article{edmonds1965,
  author  = {Jack Edmonds},
  title   = {Paths, Trees, and Flowers},
  journal = {Canadian Journal of Mathematics},
  volume  = {17},
  pages   = {449--467},
  year    = {1965}
}

@article{whitfield2012,
  author  = {James D. Whitfield and Mauro Faccin and Jacob D. Biamonte},
  title   = {Ground-state spin logic},
  journal = {EPL (Europhysics Letters)},
  volume  = {99},
  number  = {5},
  pages   = {57004},
  year    = {2012}
}

@article{nguyen2023,
  author  = {Minh-Thi Nguyen and Jin-Guo Liu and Jonathan Wurtz and Mikhail D. Lukin and Sheng-Tao Wang and Hannes Pichler},
  title   = {Quantum Optimization with Arbitrary Connectivity Using {R}ydberg Atom Arrays},
  journal = {PRX Quantum},
  volume  = {4},
  pages   = {010316},
  year    = {2023},
  doi     = {10.1103/PRXQuantum.4.010316}
}

@article{xiao2017,
  author  = {Mingyu Xiao and Hiroshi Nagamochi},
  title   = {Exact Algorithms for Maximum Independent Set},
  journal = {Information and Computation},
  volume  = {255},
  pages   = {126--146},
  year    = {2017},
  doi     = {10.1016/j.ic.2017.06.001}
}

@article{robson1986,
  author  = {J. M. Robson},
  title   = {Algorithms for Maximum Independent Sets},
  journal = {Journal of Algorithms},
  volume  = {7},
  number  = {3},
  pages   = {425--440},
  year    = {1986},
  doi     = {10.1016/0196-6774(86)90032-5}
}

@article{robson2001,
  author  = {J. M. Robson},
  title   = {Finding a Maximum Independent Set in Time $O(2^{n/4})$},
  year    = {2001},
  note    = {Technical Report 1251-01, LaBRI, Université Bordeaux I}
}

@article{vanrooij2011,
  author  = {Johan M. M. van Rooij and Hans L. Bodlaender},
  title   = {Exact algorithms for dominating set},
  journal = {Discrete Applied Mathematics},
  volume  = {159},
  number  = {17},
  pages   = {2147--2164},
  year    = {2011},
  doi     = {10.1016/j.dam.2011.07.001}
}

@article{williams2005,
  author  = {Ryan Williams},
  title   = {A new algorithm for optimal 2-constraint satisfaction and its implications},
  journal = {Theoretical Computer Science},
  volume  = {348},
  number  = {2--3},
  pages   = {357--365},
  year    = {2005},
  doi     = {10.1016/j.tcs.2005.09.023}
}

@article{tomita2006,
  author  = {Etsuji Tomita and Akira Tanaka and Haruhisa Takahashi},
  title   = {The worst-case time complexity for generating all maximal cliques and computational experiments},
  journal = {Theoretical Computer Science},
  volume  = {363},
  number  = {1},
  pages   = {28--42},
  year    = {2006},
  doi     = {10.1016/j.tcs.2006.06.015}
}

@article{heldkarp1962,
  author  = {Michael Held and Richard M. Karp},
  title   = {A Dynamic Programming Approach to Sequencing Problems},
  journal = {Journal of the Society for Industrial and Applied Mathematics},
  volume  = {10},
  number  = {1},
  pages   = {196--210},
  year    = {1962},
  doi     = {10.1137/0110015}
}

@article{beigel2005,
  author  = {Richard Beigel and David Eppstein},
  title   = {3-Coloring in Time {$O(1.3289^n)$}},
  journal = {Journal of Algorithms},
  volume  = {54},
  number  = {2},
  pages   = {168--204},
  year    = {2005},
  doi     = {10.1016/j.jalgor.2004.06.008}
}

@inproceedings{wu2024,
  author    = {Pu Wu and Huanyu Gu and Huiqin Jiang and Zehui Shao and Jin Xu},
  title     = {A Faster Algorithm for the 4-Coloring Problem},
  booktitle = {European Symposium on Algorithms (ESA)},
  series    = {LIPIcs},
  volume    = {308},
  pages     = {103:1--103:16},
  year      = {2024},
  doi       = {10.4230/LIPIcs.ESA.2024.103}
}

@inproceedings{zamir2021,
  author    = {Or Zamir},
  title     = {Breaking the {$2^n$} Barrier for 5-Coloring and 6-Coloring},
  booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
  series    = {LIPIcs},
  volume    = {198},
  pages     = {113:1--113:20},
  year      = {2021},
  doi       = {10.4230/LIPIcs.ICALP.2021.113}
}

@article{bjorklund2009,
  author  = {Andreas Bj\"{o}rklund and Thore Husfeldt and Mikko Koivisto},
  title   = {Set Partitioning via Inclusion-Exclusion},
  journal = {SIAM Journal on Computing},
  volume  = {39},
  number  = {2},
  pages   = {546--563},
  year    = {2009},
  doi     = {10.1137/070683933}
}

@article{aspvall1979,
  author  = {Bengt Aspvall and Michael F. Plass and Robert Endre Tarjan},
  title   = {A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas},
  journal = {Information Processing Letters},
  volume  = {8},
  number  = {3},
  pages   = {121--123},
  year    = {1979},
  doi     = {10.1016/0020-0190(79)90002-4}
}

@inproceedings{hansen2019,
  author    = {Thomas Dueholm Hansen and Haim Kaplan and Or Zamir and Uri Zwick},
  title     = {Faster $k$-{SAT} Algorithms Using Biased-{PPSZ}},
  booktitle = {Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC)},
  pages     = {578--589},
  year      = {2019},
  doi       = {10.1145/3313276.3316359}
}

@phdthesis{dadush2012,
  author = {Daniel Dadush},
  title  = {Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation},
  school = {Georgia Institute of Technology},
  year   = {2012}
}

@incollection{lenstra1993,
  author    = {Arjen K. Lenstra and Hendrik W. Lenstra and Mark S. Manasse and John M. Pollard},
  title     = {The Number Field Sieve},
  booktitle = {The Development of the Number Field Sieve},
  publisher = {Springer},
  series    = {Lecture Notes in Mathematics},
  volume    = {1554},
  year      = {1993},
  doi       = {10.1007/BFb0091539}
}

@inproceedings{impagliazzo2001,
  author    = {Russell Impagliazzo and Ramamohan Paturi and Francis Zane},
  title     = {Which Problems Have Strongly Exponential Complexity?},
  booktitle = {Journal of Computer and System Sciences},
  volume    = {63},
  number    = {4},
  pages     = {512--530},
  year      = {2001},
  doi       = {10.1006/jcss.2001.1774}
}

@article{pan2025,
  author  = {Xi-Wei Pan and Huan-Hai Zhou and Yi-Ming Lu and Jin-Guo Liu},
  title   = {Encoding computationally hard problems in triangular {R}ydberg atom arrays},
  journal = {arXiv preprint},
  year    = {2025},
  eprint  = {2510.25249},
  archivePrefix = {arXiv}
}

@article{goemans1995,
  author  = {Michel X. Goemans and David P. Williamson},
  title   = {Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming},
  journal = {Journal of the ACM},
  volume  = {42},
  number  = {6},
  pages   = {1115--1145},
  year    = {1995},
  doi     = {10.1145/227683.227684}
}

@inproceedings{shor1994,
  author    = {Peter W. Shor},
  title     = {Algorithms for Quantum Computation: Discrete Logarithms and Factoring},
  booktitle = {Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {124--134},
  year      = {1994},
  doi       = {10.1109/SFCS.1994.365700}
}

@article{moonmoser1965,
  author  = {J. W. Moon and L. Moser},
  title   = {On cliques in graphs},
  journal = {Israel Journal of Mathematics},
  volume  = {3},
  number  = {1},
  pages   = {23--28},
  year    = {1965},
  doi     = {10.1007/BF02760024}
}

@inproceedings{lenstra1983,
  author    = {Hendrik W. Lenstra},
  title     = {Integer Programming with a Fixed Number of Variables},
  booktitle = {Mathematics of Operations Research},
  volume    = {8},
  number    = {4},
  pages     = {538--548},
  year      = {1983},
  doi       = {10.1287/moor.8.4.538}
}

@article{epping2004,
  author  = {Thomas Epping and Winfried Hochst\"{a}ttler and Peter Oertel},
  title   = {Complexity results on a paint shop problem},
  journal = {Discrete Applied Mathematics},
  volume  = {136},
  number  = {2--3},
  pages   = {217--226},
  year    = {2004},
  doi     = {10.1016/S0166-218X(03)00442-6}
}

@techreport{vanemde1981,
  author      = {Peter van Emde Boas},
  title       = {Another NP-complete Problem and the Complexity of Computing Short Vectors in a Lattice},
  institution = {Mathematisch Instituut, Universiteit van Amsterdam},
  number      = {81-04},
  year        = {1981}
}

@article{kannan1987,
  author  = {Ravi Kannan},
  title   = {Minkowski's Convex Body Theorem and Integer Programming},
  journal = {Mathematics of Operations Research},
  volume  = {12},
  number  = {3},
  pages   = {415--440},
  year    = {1987},
  doi     = {10.1287/moor.12.3.415}
}

@inproceedings{micciancio2010,
  author    = {Daniele Micciancio and Panagiotis Voulgaris},
  title     = {A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on {V}oronoi Cell Computations},
  booktitle = {Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC)},
  pages     = {351--358},
  year      = {2010},
  doi       = {10.1145/1806689.1806739}
}

@inproceedings{aggarwal2015,
  author    = {Divesh Aggarwal and Daniel Dadush and Noah Stephens-Davidowitz},
  title     = {Solving the Closest Vector Problem in $2^n$ Time -- The Discrete {G}aussian Strikes Again!},
  booktitle = {Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS)},
  pages     = {563--580},
  year      = {2015},
  doi       = {10.1109/FOCS.2015.41}
}

@article{shannon1956,
  author  = {Claude E. Shannon},
  title   = {The zero error capacity of a noisy channel},
  journal = {IRE Transactions on Information Theory},
  volume  = {2},
  number  = {3},
  pages   = {8--19},
  year    = {1956},
  doi     = {10.1109/TIT.1956.1056798}
}