alphaFeedback

WorksMathematics

The Exponential Time Hypothesis is False

AI contributions
  • unreleased internal OpenAI model
View details
Ancillary data
Formal proof, 4 proof or workflow links
View

Abstract

We give a deterministic algorithm for exactly counting the satisfying assignments of an arbitrary kk-CNF formula. For every fixed k≥2k\ge2, on a formula with nn variables and mm clauses, our algorithm uses space polynomial in nn and mm and runs in time (n+m)Ok(1)2n/(log⁡n)1/2+o(1)(n+m)^{O_k(1)}2^{n/(\log n)^{1/2+o(1)}}. Our algorithm refutes the Exponential Time Hypothesis (ETH), which postulates that deciding 3-SAT on nn variables requires 2Ω(n)2^{\Omega(n)} time in the worst case.

Introduction

For every fixed k≥3k \ge3, kk-SAT is the canonical NP-complete problem [25], and its exponential-time complexity underlies the Exponential Time Hypothesis (ETH) and the Strong Exponential Time Hypothesis (SETH) [38, 39]. In this paper, we refute ETH by giving, for every fixed k≥2k \ge2, a deterministic algorithm that counts the satisfying assignments of a kk-CNF in subexponential time and polynomial space.

Write the input kk-CNF on nn declared variables with mm input clauses as

F(x1,…,xn)=⋀e=1m[(xie,1⊕be,1)∨⋯∨(xie,k⊕be,k)].F(x_1,\ldots,x_n)=\bigwedge_{e=1}^{m}\left[(x_{i_{e,1}}\oplus b_{e,1})\vee\cdots\vee(x_{i_{e,k}}\oplus b_{e,k})\right].

where ie,j∈{1,…,n}i_{e,j}\in\{1,\ldots,n\} and be,j∈{0,1}b_{e,j}\in\{0,1\} are the variable index and negation bit of the jjth literal in clause ee, and ⊕\oplus denotes addition modulo two. Repeating a literal permits clauses with fewer than kk literals. The indices ie,ji_{e,j} and bits be,jb_{e,j} are fixed by FF; only x1,…,xnx_1,\ldots,x_n vary over assignments. Our aim is to compute the quantity

#F=∣{x∈{0,1}n:F(x)=1}∣.(1)\#F=\left|\left\{x\in\{0,1\}^{n}:F(x)=1\right\}\right|. \tag*{(1)}

Testing #F>0\#F>0 also decides satisfiability. We keep kk fixed as nn grows. Throughout, log⁡\log denotes the natural logarithm.

Theorem 1.1. For each fixed k≥2k \ge2, there exists a deterministic algorithm that, given a kk-CNF FF on n≥20n \ge20 declared variables with mm clauses, computes #F\#F as defined in (1) in

(n+m)Ok(1)2Ok(nlog⁡log⁡n/log⁡n)(n+m)^{O_k(1)}2^{O_k(n\log\log n/\sqrt{\log n})}

bit operations and (n+m)Ok(1)(n+m)^{O_k(1)} bits of space. For each fixed D>0D>0, its running time on inputs with m≤Dnm \le Dn is

(n+m)Ok,D(1)2Ok,D(n/log⁡n).(n+m)^{O_{k,D}(1)}2^{O_{k,D}(n/\sqrt{\log n})}.

The rational interpolation argument in § 6.4 gives the weaker exponent Ok(ρ(n))O_k(\rho(n)), where

ρ(n)=n(log⁡log⁡n)2log⁡n=n(log⁡n)1/2+o(1).\rho(n)=\frac{n(\log\log n)^2}{\sqrt{\log n}}=\frac{n}{(\log n)^{1/2+o(1)}}.

Appendix § 10 proves both bounds in Theorem 1.1 by tensor contraction. When #F>0\#F>0, the standard self-reduction finds a satisfying assignment by fixing one variable at a time and checking that the remaining count is positive. Choosing each bit according to the two conditional counts instead gives an exactly uniform random satisfying assignment, with poly⁡k(n,m)\operatorname{poly}_k(n,m) expected overhead [41 Theorem 3.3(1)].

The theorem also yields arbitrarily accurate subexponential-time approximation algorithms for Max-kk-SAT. The Unique Games Theorem [53 Section 8.1] implies NP-hardness bounds for Max-kk-SAT that match, up to arbitrarily small error in the approximation ratio, the guarantees of the semidefinite-programming algorithm of [56]. Write OPT⁡(F)\operatorname{OPT}(F) for the maximum number of clauses of FF simultaneously satisfied by an assignment.

Corollary 1.2. For every fixed k≥2k \ge2 and ε>0\varepsilon>0, there exists a randomized algorithm that, given a kk-CNF FF on n≥20n \ge20 variables with mm clauses, finds an assignment satisfying at least OPT⁡(F)−εm\operatorname{OPT}(F)-\varepsilon m clauses with probability 1−2−Ω(n)1-2^{-\Omega(n)}, in

(n+m)Ok,ε(1)2Ok,ε(ρ(n))(n+m)^{O_{k,\varepsilon}(1)}2^{O_{k,\varepsilon}(\rho(n))}

time and (n+m)Ok,ε(1)(n+m)^{O_{k,\varepsilon}(1)} space.

Proof. We may assume m>0m>0. Let f(x)f(x) be the fraction of clauses satisfied by xx, and let f^(x)\widehat{f}(x) be that fraction in a sample of O(n/ε2)O(n/\varepsilon^2) clauses chosen independently and uniformly with replacement. Hoeffding’s inequality and a union bound over all 2n2^n assignments give, with probability 1−2−Ω(n)1-2^{-\Omega(n)},

∣f^(x)−f(x)∣≤ε/2for every x∈{0,1}n.\left|\widehat{f}(x)-f(x)\right|\le\varepsilon/2\qquad\text{for every }x\in\{0,1\}^n.

Thus, if x^\widehat{x} maximizes f^\widehat{f}, then f(x^)≥max⁡xf(x)−εf(\widehat{x})\ge\max_x f(x)-\varepsilon. Given an integer threshold bb, a Boolean circuit with at most two inputs per gate and size Ok,ε(n)O_{k,\varepsilon}(n) tests whether an assignment satisfies at least bb sampled clauses. The standard circuit-to-3-CNF reduction [9 Lemmas 15.9–15.10] produces a formula with Ok,ε(n)O_{k,\varepsilon}(n) variables and clauses that is satisfiable exactly when this threshold can be attained. Theorem 1.1, binary search on the threshold, and self-reduction then find an exact sample optimizer within the stated bounds. Truncating rejection sampling after O(n+log⁡(n/ε2))O(n+\log(n/\varepsilon^2)) trials per sample gives worst-case poly⁡(n,m,ε−1)\operatorname{poly}(n,m,\varepsilon^{-1}) sampling time and adds at most 2−Ω(n)2^{-\Omega(n)} to the failure probability. □

Note that runtime bounds of the form 2o(n)2^{o(n)} do not transfer under general polynomial-time reductions (2no(1)2^{n^{o(1)}} would be needed for this), so our result does not imply that general NP problems admit subexponential time algorithms. However we do obtain subexponential time algorithms for counting graph colorings and perfect matchings.

Corollary 1.3. On simple graphs with vv vertices and ee edges, the number of independent sets and, for each fixed q≥2q\ge2, the number of proper qq-colorings can be computed deterministically in 2o(v)2^{o(v)} time and poly⁡q(v,e)\operatorname{poly}_q(v,e) space. The number of perfect matchings can be computed deterministically in 2o(v+e)2^{o(v+e)} time and poly⁡(v,e)\operatorname{poly}(v,e) space.

Proof. For G=(V,E)G=(V,E), introduce a Boolean variable xux_u for each u∈Vu \in V. Satisfying assignments of

⋀{u,w}∈E(¬xu∨¬xw)\bigwedge_{\{u,w\}\in E}(\neg x_u \lor\neg x_w)

correspond bijectively to the independent sets {u∈V:xu=1}\{u \in V : x_u = 1\}. For proper qq-colorings, use one Boolean variable per vertex and color, require exactly one color at each vertex, and forbid equal colors at adjacent vertices. This gives a counting-preserving qq-CNF encoding with qvqv variables and Oq(v+e)O_q(v+e) clauses.

For perfect matchings, use one Boolean variable per edge and a linear-size circuit checking that exactly one selected edge meets each vertex. The standard circuit-to-3-CNF reduction [9 Lemmas 15.9–15.10] gives O(v+e)O(v+e) variables and clauses. The gate variables have unique values once the edge bits are fixed, so this encoding also preserves the count. Theorem 1.1 gives the stated time and space bounds. □

The fixed-density case of Theorem 1.1 gives a circuit lower bound for ENP\mathrm{E}^{\mathrm{NP}}, the class of languages decidable in deterministic time 2O(n)2^{O(n)} with an NP oracle.

Corollary 1.4. Let CL(n)C_L(n) be the minimum number of noninput gates in a circuit computing LL on {0,1}n\{0,1\}^n, allowing arbitrary Boolean gates of fan-in at most two and unrestricted fan-out. There exist a language L∈ENPL \in\mathrm{E}^{\mathrm{NP}} and a constant c>0c > 0 such that

CL(n)>cnlog⁡n(2)C_L(n) > cn\sqrt{\log n} \tag*{(2)}

for infinitely many nn.

Appendix C.1 proves the corollary. Appendix C.2 gives algorithms for inversion and exact preimage counting of Boolean maps with constant output locality.

Related work

We first discuss earlier SAT and counting algorithms and the complexity hypotheses contradicted by Theorem 1.1. We then compare our approach with earlier algebraic algorithms and identify the existing constructions used in our proof, whose roles are developed in the roadmap in Section 2.

SAT algorithms and the exponential-time hypotheses

Schöning’s local-search algorithm and PPSZ are landmarks in the development of exponential-time algorithms for kk-SAT [59, 54]. Schöning’s randomized algorithm starts from a random assignment and repeatedly flips a uniformly chosen variable in an unsatisfied clause. Its bounded-error decision time is

(n+m)O(1)(2−2/k)n(n+m)^{O(1)}(2-2/k)^n

for each fixed k≥3k \ge3 [59 Section 2]. In particular, this gives (n+m)O(1)(4/3)n(n+m)^{O(1)}(4/3)^n time for 3-SAT.

The PPSZ algorithm [54] uses a different mechanism: bounded resolution derives additional clauses, after which variables are assigned in a random order, taking forced values when available and guessing otherwise. For k=3,4k=3,4, its original analysis gave stronger bounds for uniquely satisfiable formulas than for general ones. The unique-SAT guarantees were later extended to general 3-SAT and 4-SAT; for 3-SAT this gave a randomized O(1.308n)O(1.308^n) bound [35]. Hansen, Kaplan, Zamir, and Zwick improved the PPSZ bound for every fixed k≥3k \ge3 by biasing the algorithm’s guesses [34]. Scheder obtained an improvement for the same range of kk by sharpening the analysis of the original PPSZ algorithm [58 Theorem 1.5]. For general 3-SAT, a preprint by Jiang and Cai gives a randomized O∗(1.307031578n)O^*(1.307031578^n) bound [42 Corollary 1.2], where O∗O^* suppresses factors polynomial in the input size. Lius’ deterministic algorithm combines branching with derandomized local search and solves 3-SAT in O(1.32793n)O(1.32793^n) time [48 Theorem 21].

Randomized local search has also produced effective heuristics. The WalkSAT heuristic chooses an unsatisfied clause and flips one of its variables, combining random choices with greedy moves [61]. Experiments on formulas from circuit synthesis and diagnosis demonstrated the practical value of this approach [61 pp. 340–342, Tables 4–5].

Among uniformly random kk-CNFs, instances at the satisfiability threshold were conjectured to be the hardest for deciding satisfiability [68 Section 1]; for fixed k≥3k \ge3 and lower clause densities m/n≤2k/kCm/n \le2^k/k^C, where CC is a universal constant, polynomial-time almost-uniform sampling of satisfying assignments is known with high probability over the formula [CLWYY25, Theorem 1.2]. For a uniformly random formula with polynomially many clauses, conditioned on satisfiability, Vyas and Williams [68 Theorem 3] give a PPZ-based algorithm that finds a solution in 2n(1−Ω(log⁡k/k))2^{n(1-\Omega(\log k/k))} time with high probability over both the formula and the algorithm’s random choices.

The Exponential Time Hypothesis (ETH) asserted that 3-SAT requires 2Ω(n)2^{\Omega(n)} deterministic time in the worst case, and hence so does kk-SAT for every fixed k≥3k \ge3 [IP01, Theorem 1]. The Strong Exponential Time Hypothesis (SETH) made the sharper prediction that kk-SAT requires 2n(1−ok(1))2^{n(1-o_k(1))} time as kk grows. Precisely, for every ϵ∈(0,1)\epsilon\in(0, 1), there is a fixed kk for which no deterministic algorithm solves kk-SAT in 2(1−ϵ)n(n+m)O(1)2^{(1-\epsilon)n}(n+m)^{O(1)} time. The running-time bounds for Schöning’s algorithm and PPSZ helped motivate this prediction: their improvements over exhaustive search diminish as kk grows [IP01, Open Problems, item 2].

The Gap Exponential Time Hypothesis (Gap-ETH) strengthens ETH by postulating constants δ,γ>0\delta, \gamma> 0 for which no O(2γn)O(2^{\gamma n})-time algorithm can distinguish a satisfiable 3-CNF from one in which every assignment violates at least a δ\delta fraction of the clauses, even when m=O(n)m=O(n) [Din16, MR17]. The randomized version rules out an algorithm with the same running time that distinguishes the two cases with probability at least 2/32/3 on every promised input [CCK+20, Conjecture 2.5]. It has been used to prove hardness of approximating Label Cover [29] and dense constraint satisfaction problems [MR17]. It also rules out nontrivial fixed-parameter approximations for Clique and Dominating Set. For Clique, the excluded ratios are o(OPT)o(\mathrm{OPT}), where OPT\mathrm{OPT} is the maximum clique size [CCK+20, Corollaries 5.3 and 5.6].

The Nondeterministic Strong Exponential Time Hypothesis (NSETH) asserts that, for every ϵ>0\epsilon> 0, some fixed kk admits no nondeterministic 2(1−ϵ)n(n+m)O(1)2^{(1-\epsilon)n}(n+m)^{O(1)}-time algorithm for deciding whether a kk-CNF is unsatisfiable, or equivalently whether a kk-DNF is a tautology [CGI+16]. NSETH has been used to establish barriers to deterministic fine-grained reductions from SAT to problems such as 3SUM and All-Pairs Shortest Paths [CGI+16], and to delineate SETH-based lower bounds for approximating directed graph diameter [Li21].

Theorem 1.1 refutes ETH, SETH, Gap-ETH, and NSETH. Indeed, testing whether the exact count is positive or zero decides both satisfiability and unsatisfiability in deterministic 2o(n)(n+m)Ok(1)2^{o(n)}(n+m)^{O_k(1)} time for every fixed kk; deciding satisfiability also solves the Gap-ETH promise problem. The deterministic algorithm also refutes the bounded-error randomized versions of ETH [28 Section 1] and SETH [27 Definition 2.1], and of Gap-ETH. It does not conflict with unconditional exponential lower bounds for restricted proof systems such as regular resolution [BI13]. In 2016, Ryan Williams refuted the Merlin–Arthur version of SETH (MA-SETH) by giving a protocol that certifies kk-CNF unsatisfiability in 2n/2poly⁡(n,m)2^{n/2}\operatorname{poly}(n,m) time [Wil16, Theorem 3.3].

Exact counting and counting complexity

References

  1. [1]Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. 30th ACM–SIAM Symposium on Discrete Algorithms, 2019, 41–57. 5
  2. [2]Amir Abboud and Virginia Vassilevska Williams. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. 55th IEEE Symposium on Foundations of Computer Science, 2014, 434–443. 5arxiv.org/abs/1402.0054
  3. [3]Josh Alman, Yunfeng Guan, and Ashwin Padaki. Smaller Low-Depth Circuits for Kronecker Powers. 34th ACM–SIAM Symposium on Discrete Algorithms, 2023, 4159–4187. 6arxiv.org/abs/2211.05217
  4. [4]Josh Alman and Ryan Williams. Probabilistic Polynomials and Hamming Nearest Neighbors. 56th IEEE Symposium on Foundations of Computer Science, 2015, 136–150. 6DOI
  5. [5]Josh Alman and Ryan Williams. Probabilistic Rank and Matrix Rigidity. 49th ACM Symposium on Theory of Computing, 2017, 641–652. 6arxiv.org/abs/1611.05558
  6. [6]Noga Alon and Yuval Roichman. Random Cayley Graphs and Expanders. Random Structures & Algorithms 5(2), 1994, 271–284. 7DOI
  7. [7]Arturs Backurs and Piotr Indyk. Which Regular Expression Patterns Are Hard to Match? 57th IEEE Symposium on Foundations of Computer Science, 2016, 457–466. 5arxiv.org/abs/1511.07070
  8. [8]Arturs Backurs and Piotr Indyk. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). SIAM Journal on Computing 47(3), 2018, 1087–1097. Conference version in STOC 2015. 5
  9. [9]Boaz Barak. Introduction to Theoretical Computer Science. Online textbook, 2023. Chapter 15, Lemmas 15.9–15.10. Archived 2023 edition (v0.95). 2, 3
  10. [10]Erwin H. Bareiss. Sylvester’s Identity and Multistep Integer-Preserving Gaussian Elimination. Mathematics of Computation 22(103), 1968, 565–578. 50
  11. [12]Richard Beigel and Jun Tarui. On ACC. Computational Complexity 4(4), 1994, 350–366. 36DOI
  12. [13]Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, and Chandra Kanta Mohapatra. Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications. Journal of the ACM 70(6), 2023, 42:1–42:46. Conference version in STOC 2022. 6
  13. [14]Andreas Björklund. Below All Subsets for Some Permutational Counting Problems. 15th Scandinavian Symposium and Workshops on Algorithm Theory, LIPIcs 53, 2016, 17:1–17:11. 5arxiv.org/abs/1211.0391
  14. [16]Karl Bringmann. Why Walking the Dog Takes Time: Fréchet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. 55th IEEE Symposium on Foundations of Computer Science, 2014, 661–670. 5arxiv.org/abs/1404.1448
  15. [17]Karl Bringmann and Marvin Künnemann. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. 56th IEEE Symposium on Foundations of Computer Science, 2015, 79–97. 5
  16. [18]Chris Calabro. The Exponential Complexity of Satisfiability Problems. Ph.D. dissertation, University of California, San Diego, 2009. Chapter 5. 6, 18
  17. [19]Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. A Duality between Clause Width and Clause Density for SAT. 21st IEEE Conference on Computational Complexity, 2006, 252–260. 6, 18, 44DOI
  18. [22]Timothy M. Chan and R. Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov–Smolensky. ACM Transactions on Algorithms 17(1), Article 2, 2021, 1–14. Authors’ manuscript, Theorems 1.6 and 2.5. 4, 36
  19. [25]Stephen A. Cook. The Complexity of Theorem-Proving Procedures. 3rd ACM Symposium on Theory of Computing, 1971, 151–158. 1DOI
  20. [26]Radu Curticapean. Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity. Information and Computation 261, Part 2, 2018, 265–280. Conference version in ICALP 2015. 4
  21. [27]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), Article 41, 2016, 1–24. 4, 5
  22. [28]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), Article 21, 2014, 1–32. 4, 6, 18, 44
  23. [29]Irit Dinur. Mildly Exponential Reduction from Gap 3SAT to Polynomial-Gap Label-Cover. Electronic Colloquium on Computational Complexity, Report TR16-128, 2016. 4
  24. [30]Zeev Dvir and Allen Liu. Fourier and Circulant Matrices are Not Rigid. Theory of Computing 16(20), 2020, 1–48. 6
  25. [31]Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. 3rd edition, Cambridge University Press, 2013. 57, 58, 60DOI
  26. [32]Oded Goldreich. Candidate One-Way Functions Based on Expander Graphs. Electronic Colloquium on Computational Complexity, Report TR00-090, 2000.
  27. [34]Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Faster k-SAT Algorithms Using Biased-PPSZ. 51st ACM Symposium on Theory of Computing, 2019, 578–589.
  28. [35]Timon Hertli. 3-SAT Faster and Simpler—Unique-SAT Bounds for PPSZ Hold in General. SIAM Journal on Computing 43(2), 2014, 718–729. Conference version in FOCS 2011.
  29. [36]Thore Husfeldt. Invitation to Algorithmic Uses of Inclusion-Exclusion. 38th International Colloquium on Automata, Languages, and Programming, Part II, Lecture Notes in Computer Science 6756, 2011, 42–59.arxiv.org/abs/1105.2942
  30. [37]Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A Satisfiability Algorithm for AC⁰. 23rd ACM–SIAM Symposium on Discrete Algorithms, 2012, 961–972. Publisher’s version.
  31. [38]Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences 62(2), 2001, 367–375.DOI
  32. [39]Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences 63(4), 2001, 512–530.
  33. [40]Hamid Jahanjou, Eric Miles, and Emanuele Viola. Local Reductions. Electronic Colloquium on Computational Complexity, Report TR13-099, revision 2, 2013. Conference version in ICALP 2015, 749–760.
  34. [41]Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random Generation of Combinatorial Structures from a Uniform Distribution. Theoretical Computer Science 43(2–3), 1986, 169–188.DOI
  35. [42]Tao Jiang and Shaowei Cai. A Better Analysis For PPSZ For 3-SAT. arXiv:2607.10697, 2026.arxiv.org/abs/2607.10697
  36. [43]Mikko Koivisto. Optimal 2-Constraint Satisfaction via Sum–Product Algorithms. Information Processing Letters 98(1), 2006, 24–28.DOI
  37. [45]Ioannis Koutis and Ryan Williams. Algebraic Fingerprints for Faster Algorithms. Communications of the ACM 59(1), 2016, 98–105.DOI
  38. [48]Sixue Liu. Chain, Generalization of Covering Code, and Deterministic Algorithm for k-SAT. 45th International Colloquium on Automata, Languages, and Programming, LIPIcs 107, 2018, 88:1–88:13.arxiv.org/abs/1804.07901
  39. [49]Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal. ACM Transactions on Algorithms 14(2), Article 13, 2018, 1–30. Conference version in SODA 2011.
  40. [51]Dániel Marx. Can You Beat Treewidth? Theory of Computing 6, 2010, 85–112.
  41. [52]Joseph Naor and Moni Naor. Small-Bias Probability Spaces: Efficient Constructions and Applications. SIAM Journal on Computing 22(4), 1993, 838–856.
  42. [53]OpenAI, The Unique Games Theorem, OpenAI Math Release preprint OAI:The-Unique-Games-Theorem-September-23-2026, 2026.hub.valency.io/works/W_xra45zpr
  43. [54]Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, and Francis Zane. An Improved Exponential-Time Algorithm for k-SAT. Journal of the ACM 52(3), 2005, 337–364. Conference version in FOCS 1998.
  44. [55]Prabhakar Raghavan. Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs. Journal of Computer and System Sciences 37(2), 1988, 130–143.
  45. [56]Prasad Raghavendra. Optimal Algorithms and Inapproximability Results for Every CSP? 40th ACM Symposium on Theory of Computing, 2008, 245–254.DOI
  46. [57]Liam Roditty and Virginia Vassilevska Williams. Fast Approximation Algorithms for the Diameter and Radius of Sparse Graphs. 45th ACM Symposium on Theory of Computing, 2013, 515–524.DOI
  47. [58]Dominik Scheder. PPSZ is better than you think. Theoretics 3, Article 5, 2024, 1–37.
  48. [59]Uwe Schöning. A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. 40th IEEE Symposium on Foundations of Computer Science, 1999, 410–414.
  49. [60]Alexander D. Scott and Gregory B. Sorkin. Polynomial Constraint Satisfaction Problems, Graph Bisection, and the Ising Partition Function. ACM Transactions on Algorithms 5(4), 2009, 45:1–45:27. 5DOI
  50. [61]Bart Selman, Henry A. Kautz, and Bram Cohen. Noise Strategies for Improving Local Search. 12th National Conference on Artificial Intelligence, 1994, 337–343. 3
  51. [62]Michael Sipser and Daniel A. Spielman. Expander Codes. IEEE Transactions on Information Theory 42(6), 1996, 1710–1722. 6, 40
  52. [63]R. Michael Tanner. A Recursive Approach to Low Complexity Codes. IEEE Transactions on Information Theory 27(5), 1981, 533–547. 6, 40DOI
  53. [64]Craig A. Tovey. A Simplified NP-Complete Satisfiability Problem. Discrete Applied Mathematics 8(1), 1984, 85–89. 18DOI
  54. [65]Leslie G. Valiant. Graph-Theoretic Arguments in Low-Level Complexity. Mathematical Foundations of Computer Science 1977, Lecture Notes in Computer Science 53, 1977, 162–176. 6DOI
  55. [67]Virginia Vassilevska Williams. On Some Fine-Grained Questions in Algorithms and Complexity. Proceedings of the International Congress of Mathematicians (ICM 2018), World Scientific, 2019, 3447–3487. 5DOI
  56. [68]Nikhil Vyas and Ryan Williams. On Super Strong ETH. Journal of Artificial Intelligence Research 70, 2021, 473–495. 4
  57. [70]Ryan Williams. A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications. Theoretical Computer Science 348(2–3), 2005, 357–365. 5DOI
  58. [71]Ryan Williams. Improving Exhaustive Search Implies Superpolynomial Lower Bounds. SIAM Journal on Computing 42(3), 2013, 1218–1244. Conference version in STOC 2010. The numbering of Lemma 3.2 and Theorem 6.1 follows the author’s full version. 51
  59. [72]Richard Ryan Williams. The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk). 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, LIPICs 29, 2014, 47–60. 5DOI
  60. [74]David Woodruff and Sergey Yekhanin. A Geometric Approach to Information-Theoretic Private Information Retrieval. SIAM Journal on Computing 37(4), 2007, 1046–1056. 6
  61. [75]Stanislav Žak. A Turing Machine Time Hierarchy. Theoretical Computer Science 26(3), 1983, 327–333. 51DOI

Paper details

vlnc:W_h8uqubsk
v1 · latestHistory (1)

published · Fresh — published within the last 30 days

Usage

views · 82

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

LicenseRef-OpenAI-public

Original source

  • Mathematics

unreleased internal OpenAI model · View statement →

Looking for related papers…
Contents