Pith. sign in

REVIEW 3 major objections 3 minor 1 cited by

Learning-Augmented Algorithms for Boolean Satisfiability

T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A random sample of an optimal assignment provably shrinks the worst-case exponent of k-SAT and MAX-SAT algorithms.

desk verdict The PPSZ-with-advice analysis is clever and correct for Unique-k-SAT, but the jump to general k-SAT is not justified; the stress-test's disjoint-clauses counterexample doesn't hold, yet the underlying lifting concern is real. read the letter →

arxiv 2505.06146 v2 pith:DH64GLH7 submitted 2025-05-09 cs.DS cs.CCcs.LG

Idan Attias , Xing Gao , Lev Reyzin This is my paper · ORCID
classification cs.DScs.CCcs.LG MSC 68Q2568W2068W40
keywords learning-augmentedalgorithmswithpredictionsBooleansatisfiabilityk-SATPPSZMAX-SATsubsetadvicelabel
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that if an algorithm is given a random sample of an optimal assignment—each variable independently revealed with probability $\epsilon$—the standard randomized algorithms for $k$-SAT can be accelerated by a multiplicative factor of $2^{-\epsilon_k n}$ in the base of the exponent, where $\epsilon_k$ is a positive correction depending on $\epsilon$ and $k$. For 3-SAT, the PPSZ base constant improves from $2^{2\ln 2-1+o(1)}$ to $2^{\epsilon/(1-\epsilon)+2\ln(2-2\epsilon)-1+o(1)}$ for $\epsilon<1/2$, and becomes $2^{o(n)}$ once $\epsilon\ge 1/2$. On the optimization side, the same subset advice turns any $\alpha$-approximation for MAX-SAT variants into an $\alpha+(1-\alpha)\epsilon$-approximation, and noisy label advice gives near-optimal guarantees for MAX-2-SAT instances with large average degree. The significance is that even imperfect, partial information about an optimal solution yields provable worst-case improvements rather than only heuristic or average-case help.

What carries the argument

The load-bearing object is the critical-clause fixed point $R_k$: the smallest nonnegative solution $R$ to $R=(r+(1-r)R)^{k-1}$, where $r$ is the random arrival time of a variable in a random permutation and $R$ is the probability that a variable is forced. Subset advice weights each branch of this recursion by $(1-\epsilon)$ unless the branch variable is already revealed, and the change of variables $u=\epsilon+(1-\epsilon)r$ sends the advised equation exactly onto the original one, yielding the positive saving $\epsilon_k=\epsilon-\int_0^\epsilon R_k(r)\,dr$. This identity is what turns the qualitative idea of giving partial advice into a quantitative improvement of the exponent, and it is also what makes the threshold $\epsilon\ge(k-2)/(k-1)$ produce sub-exponential time.

What would settle it

For $k=3$ with $\epsilon=1/2$, run the advised PPSZ algorithm on a satisfiable 3-CNF formula with a unique satisfying assignment, track the expected number of guessed variables over the random permutation and random advice, and compare it to $o(n)$; an expectation of at least $cn$ for a constant $c>0$ would refute the sub-exponential claim.

Watch

Extended reading notes

Core claim

The core discovery is that subset advice can be folded directly into the random-restriction recursion of the PPZ and PPSZ algorithms. When a variable is not in the advice set, the advised variables in its critical clause are already fixed, which cuts branches of the analysis tree; in PPSZ's fixed-point equation $R=(r+(1-r)R)^{k-1}$ for the smallest nonnegative forcing probability $R_k(r)$, the substitution $u=\epsilon+(1-\epsilon)r$ maps the advised recursion back onto the original equation and produces a saving $\epsilon_k=\epsilon-\int_0^\epsilon R_k(r)\,dr$. The paper proves that for $0<\epsilon<(k-2)/(k-1)$ the improved PPSZ exponent is $c_k\cdot 2^{-\epsilon_k}$, strictly better than the advice-free base constant, and that for $\epsilon\ge(k-2)/(k-1)$ the running time is $O^*(2^{o(n)})$; for 3-SAT the threshold is $\epsilon=1/2$. It also proves that fixing the advised variables and then running any $\alpha$-approximation yields an $\alpha+(1-\alpha)\epsilon$-approximation for MAX-SAT variants, and it adapts a quadratic-programming rounding scheme to show that label advice achieves a $(1-O(1/(\epsilon\sqrt{\Delta})))$-approximation for MAX-2-SAT once the average degree $\Delta$ is $\Omega(1/\epsilon^2)$.

Load-bearing premise

The paper's general $k$-SAT claims depend on a known reduction from arbitrary satisfiable formulas to formulas with a unique satisfying assignment, and on that reduction preserving the promised advice-dependent speedup; if the speedup fails on the reduced formulas, the stated exponents do not follow.

Editorial extensions

If this is right

  • Every positive advice probability strictly improves the worst-case exponent of PPSZ for $k$-SAT, because $0<\epsilon_k<\epsilon$ throughout the range $0<\epsilon<(k-2)/(k-1)$.
  • For 3-SAT with $\epsilon\ge1/2$, the PPSZ running time becomes sub-exponential, so if ETH is true the oracle providing such advice cannot be simulated in polynomial time.
  • For any MAX-SAT variant, the black-box upgrade $\alpha+(1-\alpha)\epsilon$ is monotone in both $\alpha$ and $\epsilon$, so future approximation improvements translate directly into better advice-assisted guarantees.
  • With label advice, MAX-2-SAT instances of average degree $\Delta=\Omega(1/\epsilon^2)$ admit a near-optimal polynomial-time approximation whose error decays like $O(1/(\epsilon\sqrt{\Delta}))$, extending the known phenomena for MAX-CUT and MAX-2-LIN.
  • The ETH- and Gap-ETH-based hardness results imply that, for small advice probabilities, the speedups and approximation improvements cannot be turned into polynomial-time algorithms.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the change of variables $u=\epsilon+(1-\epsilon)r$ should be a general template, so any future PPSZ-style algorithm whose forcing probability is governed by a fixed-point equation of the same shape would inherit the same $2^{-\epsilon_k n}$ saving with the corresponding saving $\epsilon_k$.
  • Editorial extension: the black-box approximation result suggests an optimization not explored in the paper: instead of a random sample, an oracle that reveals the most load-bearing variables of the optimal assignment could be worth more than $(1-\alpha)\epsilon$, as long as the conditioning on $S$ keeps the remaining formula tractable.
  • Editorial extension: the sub-exponential PPSZ guarantee at $\epsilon=1/2$ for 3-SAT implies, under ETH, that subset advice revealing half the optimal assignment must be computationally expensive to obtain; quantifying that cost could connect the advice model to the hardness of assignment recovery in random 3-CNF formulas.
  • Editorial extension: the label-advice algorithm is proved only for MAX-2-SAT, but the same quadratic-programming framework plausibly extends to non-symmetric MAX-2-CSPs, going beyond the symmetric MAX-CUT and MAX-2-LIN cases treated in prior work.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper introduces learning-augmented algorithms for SAT and MAX-SAT under two advice models: subset advice (a random epsilon-fraction of the variables of an optimal assignment, with their true values) and label advice (a noisy prediction of every variable of an optimal assignment). For k-SAT, it claims that subset advice improves the exponential base of the PPZ and PPSZ algorithms, and that for PPSZ with epsilon at least (k-2)/(k-1) the running time becomes sub-exponential. These claims are derived for Unique-k-SAT and then asserted to lift to general k-SAT via Hertli's theorem. For MAX-SAT, the paper shows a black-box improvement from alpha to alpha + (1-alpha)epsilon using subset advice, giving concrete corollaries for MAX-2-SAT, MAX-3-SAT, and MAX-SAT. For MAX-2-SAT with label advice, it presents an algorithm based on the GMM25 quadratic-programming approach and claims a near-optimal approximation when the average degree is large. It also proves conditional hardness results for 3-SAT and MAX-3-SAT under ETH and Gap-ETH.

Significance. If the PPSZ-with-advice result were correct, it would be a striking beyond-worst-case statement: a random epsilon-fraction of an optimal assignment would yield a multiplicative 2^{-epsilon_k n} saving in the exponent and even sub-exponential time at epsilon = 1/2. The MAX-SAT subset-advice result is simple, elegant, and appears correct. The label-advice MAX-2-SAT section extends the GMM25 framework to a non-symmetric CSP and is potentially interesting. The paper is clearly written, and the change-of-variable computation in the PPSZ recursion is internally consistent under the Unique-SAT assumption. However, the central decision-problem claim for general k-SAT is false: a concrete counterexample shows that the Hertli-style lifting does not preserve the advice-specific saving when the reduced formula has multiple satisfying assignments. Because the headline claim is refuted, the current version cannot be accepted.

major comments (3)
  1. [Section 2.2, Theorem 2.2 and Eq. (2)] The theorem is stated for general k-SAT, but the proof analyzes only the Unique-k-SAT case, and the invocation of Hertli's lifting does not preserve the advice-specific saving. This is not merely a missing proof: the general-k-SAT statement is false. Let F_m = \wedge_{j=1}^m (x_{3j-2} \vee x_{3j-1} \vee x_{3j}) with n = 3m and x* = 1^n, and take epsilon = 1/2 (so k=3 and epsilon >= (k-2)/(k-1)). After fixing the advice, a clause remains active iff none of its three variables is in S, which occurs independently with probability 1/8. Since the clauses are disjoint and all literals are positive, no variable is forced by D-bounded resolution, so the per-iteration success probability of PPSZ is E[(7/8)^K] = (63/64)^m = 2^{-Omega(n)}. The expected number of iterations is therefore exponential, contradicting the claimed O*(2^{o(n)}) running time. The per-variable forcing bound in the proof requires that every variable of the target assignment lie in a critical clause; this fails when the reduced formula has multiple satisfying assignments. The Hertli-type lifting guarantees that PPSZ finds some satisfying assignment with the unique-case probability, not that it finds the particular assignment x* that generated the advice, and the counterexample shows that the advice-specific saving does not lift.
  2. [Section 2.1, Theorem 2.1] The proof of the PPZ-with-advice theorem also assumes that each variable x_i has a critical clause C_{x_i}, which is stated explicitly as following from the uniqueness assumption. The theorem, however, is claimed for general k-SAT. For the same disjoint-clauses formula, after fixing the advice, no variable has a critical clause with respect to the true assignment x*, because every clause is satisfied by three true literals under x*. Hence the claimed PPZ improvement for general k-SAT is not established by the given proof. Theorem 2.1 should be restricted to Unique-k-SAT or supplied with a proof that does not rely on the unique-assignment critical-clause structure.
  3. [Appendix B, Theorem 3.6 and Algorithm 2] The proof of Theorem 3.6 begins with the assertion f(y_hat) <= f(y), where y_hat is obtained by rounding the QP solution y coordinate-by-coordinate, and attributes this to the same argument as in [GMM25]. That argument is not reproduced, and the MAX-2-SAT objective differs from the MAX-2-LIN setting of [GMM25] by the linear term 2 sum_i y_0 y_i d_i and by the constraint y_i = -y_{i+n}. When the pairs (i, i+n) are rounded together, the cross term involving A_{i,i+n} can become a negative quadratic term, so the coordinate-wise rounding lemma from [GMM25] does not automatically apply. Since inequality f(y_hat) <= f(y) is load-bearing for the entire chain of inequalities, the proof is incomplete as written.
minor comments (3)
  1. [Section 3.2, proof of Theorem 3.5] The proof says 'Let epsilon_0 < delta in the ETH' but the assumption being used is Gap-ETH; the reference to ETH appears to be a typo and should be corrected to Gap-ETH.
  2. [Definition 1.4 and Section 3.3] The label-advice probability is written as '1+epsilon/2' and '1-epsilon/2', which is ambiguous. It should be written as (1+epsilon)/2 and (1-epsilon)/2 to match the subsequent calculations.
  3. [Corollary 2.3 and Table 1] The symbol c_3 is used both for the unadvised PPSZ base constant and for the advised base constant in Corollary 2.3; using c'_3 for the advised constant, as in Theorem 2.2, would avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the PPSZ/PPZ advice exponents are derived from the standard R_k forcing recursion with epsilon as an input, and the cited lifting and rounding results are external prior work.

full rationale

The paper's central derivations are self-contained with respect to the advice parameter. Theorem 2.1 computes the PPZ forced-variable probability after conditioning on the subset S and obtains the improved exponent c'_k as an explicit function of epsilon and k; no quantity is fitted to the claimed running time. Theorem 2.2 reuses the standard PPSZ forcing function R_k(r), adds epsilon as a branch-cut probability, and derives the saving epsilon_k = epsilon - integral_0^epsilon R_k(r) dr from the expectation calculation in Equation (2); epsilon_k is the output of the analysis, not a parameter chosen to match the conclusion. The lifting from Unique-k-SAT to general k-SAT is imported as an external black box from Hertli and from Scheder-Steinberger, not from the present authors' prior work. Even if that lifting fails to preserve the advice-specific saving in general formulas, that would be a correctness or assumption gap, not a definitional circularity, because the paper does not use its own conclusion as a premise. The MAX-SAT improvement alpha + (1-alpha)epsilon follows by linearity of expectation from the independent revelation of literals, and the label-advice MAX-2-SAT result is an adaptation of the external GMM25 analysis. There are no fitted inputs, no self-citation chain is load-bearing, and no advice-dependent parameter is renamed as a prediction. No significant circularity is present.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

There are no data-fitted constants. The advice parameter epsilon is an input, and epsilon_k, R_k, and c'_k are derived analytically from PPSZ's known recursion. Axioms are standard conjectures and cited PPSZ/GMM25 lemmas.

assumptions (5)
  • domain assumption PPSZ analysis lemmas (PPSZ05 Lemmas 6-8) lower-bound the forced-variable probability by R_k(r).
    Theorem 2.2 imports this as a black box and modifies the recursion for the advice.
  • domain assumption Unique-k-SAT bounds lift to general k-SAT (Hertli 2014; Scheder-Steinberger 2017).
    The paper relies on this to extend its Unique-k-SAT analysis to all k-SAT without reproving it.
  • domain assumption ETH (Conjecture 2.4) holds.
    Used for Theorem 2.5 hardness; standard conjecture.
  • domain assumption Gap-ETH (Conjecture 3.4) holds.
    Used for Theorem 3.5 hardness.
  • domain assumption GMM25 rounding and concentration lemmas: existence of integer rounding with f(y_hat) <= f(y), and bound E||A(y* - y_tilde/epsilon)||_1 <= (2/epsilon) sqrt(mn).
    Theorem 3.6 and Lemma B.2 extend these; the paper does not prove the rounding step itself.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning-Augmented Algorithms for Boolean Satisfiability." pith.science (2026). https://pith.science/paper/DH64GLH7

@misc{pith2026250506146,
  author       = {Pith},
  title        = {Pith review of: Learning-Augmented Algorithms for Boolean Satisfiability},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DH64GLH7}},
  note         = {Machine review of arXiv:2505.06146}
}
abstract

Learning-augmented algorithms are a prominent recent development in beyond worst-case analysis. In this framework, a problem instance is provided with a prediction (``advice'') from a machine-learning oracle, which provides partial information about an optimal solution, and the goal is to design algorithms that leverage this advice to improve worst-case performance. We study the classic Boolean satisfiability (SAT) decision and optimization problems within this framework using two forms of advice. ``Subset advice" provides a random $\epsilon$ fraction of the variables from an optimal assignment, whereas ``label advice" provides noisy predictions for all variables in an optimal assignment. For the decision problem $k$-SAT, by using the subset advice we accelerate the exponential running time of the PPSZ family of algorithms due to Paturi, Pudlak, Saks and Zane, which currently represent the state of the art in the worst case. We accelerate the running time by a multiplicative factor of $2^{-c}$ in the base of the exponent, where $c$ is a function of $\epsilon$ and $k$. For the optimization problem, we show how to incorporate subset advice in a black-box fashion with any $\alpha$-approximation algorithm, improving the approximation ratio to $\alpha + (1 - \alpha)\epsilon$. Specifically, we achieve approximations of $0.94 + \Omega(\epsilon)$ for MAX-$2$-SAT, $7/8 + \Omega(\epsilon)$ for MAX-$3$-SAT, and $0.79 + \Omega(\epsilon)$ for MAX-SAT. Moreover, for label advice, we obtain near-optimal approximation for instances with large average degree, thereby generalizing recent results on MAX-CUT and MAX-$2$-LIN.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Better Analysis For PPSZ For 3-SAT

    cs.DS 2026-07 accept novelty 5.0 of 10

    Recombining Scheder's regular and irregular PPSZ estimates via an LP dual certificate improves the Unique-3-SAT base to 1.306969598^n and the general 3-SAT base to 1.307031578^n.

Reference graph

Works this paper leans on

63 extracted references · 49 canonical work pages · cited by 1 Pith paper

  1. [1]

    Paging with succinct predictions

    Antonios Antoniadis, Joan Boyar, Marek Eli \'a s, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S Larsen, Adam Polak, and Bertrand Simon. Paging with succinct predictions. In International Conference on Machine Learning , pages 952--968. PMLR, 2023

    work page 2023

  2. [2]

    Improved approximation algorithms for max nae-sat and max sat

    Adi Avidor, Ido Berkovitch, and Uri Zwick. Improved approximation algorithms for max nae-sat and max sat. In International Workshop on Approximation and Online Algorithms , pages 27--40. Springer, 2005

    work page 2005

  3. [3]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (JACM) , 45(3):501--555, 1998

    1998

  4. [4]

    https://algorithms-with-predictions.github.io/, 2023

    Online index for algorithms with predictions. https://algorithms-with-predictions.github.io/, 2023

    work page 2023

  5. [5]

    Probabilistic checking of proofs: A new characterization of np

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of np. Journal of the ACM (JACM) , 45(1):70--122, 1998

    1998

  6. [6]

    Balanced max 2-sat might not be the hardest

    Per Austrin. Balanced max 2-sat might not be the hardest. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 189--197, 2007

    work page 2007

  7. [7]

    Learning-augmented maximum independent set

    Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning-augmented maximum independent set. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) , pages 24--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2024

    work page 2024

  8. [8]

    Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems

    Evripidis Bampis, Bruno Escoffier, Dimitris Fotakis, Panagiotis Patsilinakos, and Michalis Xefteris. Polynomial time learning-augmented algorithms for np-hard permutation problems. arXiv preprint arXiv:2502.00841 , 2025

    work page Pith review arXiv 2025

Show all 63 references
  1. [9]

    Parsimonious learning-augmented approximations for dense instances of np-hard problems

    Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Parsimonious learning-augmented approximations for dense instances of np-hard problems. In International Conference on Machine Learning , pages 2700--2714. PMLR, 2024

    2024

  2. [10]

    Tight approximability of max 2-sat and relatives, under ugc

    Joshua Brakensiek, Neng Huang, and Uri Zwick. Tight approximability of max 2-sat and relatives, under ugc. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1328--1344. SIAM, 2024

    2024

  3. [11]

    Improving a probabilistic 3-sat algorithm by dynamic search and independent clause pairs

    Sven Baumer and Rainer Schuler. Improving a probabilistic 3-sat algorithm by dynamic search and independent clause pairs. In International Conference on Theory and Applications of Satisfiability Testing , pages 150--161. Springer, 2003

    2003

  4. [12]

    Learning-augmented approximation algorithms for maximum cut and related problems

    Vincent Cohen-Addad, Tommaso d’Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. Learning-augmented approximation algorithms for maximum cut and related problems. Advances in Neural Information Processing Systems , 37:25961--25980, 2024

    2024

  5. [13]

    The complexity of satisfiability of small depth circuits

    Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In International Workshop on Parameterized and Exact Computation , pages 75--85. Springer, 2009

    2009

  6. [14]

    The complexity of theorem-proving procedures

    Stephen A Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing , pages 151--158, 1971

    1971

  7. [15]

    The adwords problem: online keyword matching with budgeted bidders under random permutations

    Nikhil R Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce , pages 71--78, 2009

    2009

  8. [16]

    Mildly exponential reduction from gap-3sat to polynomial-gap label-cover

    Irit Dinur. Mildly exponential reduction from gap-3sat to polynomial-gap label-cover. In Electronic colloquium on computational complexity ECCC; research reports, surveys and books in computational complexity , page 128, 2016

    2016

  9. [17]

    Learning-augmented streaming algorithms for approximating max-cut

    Yinhao Dong, Pan Peng, and Ali Vakilian. Learning-augmented streaming algorithms for approximating max-cut. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) , pages 44--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2025

    2025

  10. [18]

    Learning-augmented k -means clustering

    Jon C Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, and Samson Zhou. Learning-augmented k -means clustering. In International Conference on Learning Representations

  11. [19]

    Refuting smoothed 3cnf formulas

    Uriel Feige. Refuting smoothed 3cnf formulas. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) , pages 407--417. IEEE, 2007

    2007

  12. [20]

    Approximating the value of two power proof systems, with applications to max 2sat and max dicut

    Uriel Feige and Michel Goemans. Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In Proceedings third Israel symposium on the theory of computing and systems , pages 182--189. IEEE, 1995

    1995

  13. [21]

    Approximate cluster recovery from noisy labels

    Buddhima Gamlath, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. Approximate cluster recovery from noisy labels. In Conference on Learning Theory , pages 1463--1509. PMLR, 2022

    2022

  14. [22]

    Constraint satisfaction problems with advice

    Suprovat Ghoshal, Konstantin Markarychev, and Yury Markarychev. Constraint satisfaction problems with advice. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1202--1221. SIAM, 2025

    2025

  15. [23]

    878-approximation algorithms for max cut and max 2sat

    Michel X Goemans and David P Williamson. . 878-approximation algorithms for max cut and max 2sat. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing , pages 422--431, 1994

    1994

  16. [24]

    Some optimal inapproximability results

    Johan Hastad. Some optimal inapproximability results. Journal of the ACM (JACM) , 48(4):798--859, 2001

    2001

  17. [25]

    3-sat faster and simpler---unique-sat bounds for ppsz hold in general

    Timon Hertli. 3-sat faster and simpler---unique-sat bounds for ppsz hold in general. SIAM Journal on Computing , 43(2):718--729, 2014

    2014

  18. [26]

    Breaking the ppsz barrier for unique 3-sat

    Timon Hertli. Breaking the ppsz barrier for unique 3-sat. In International Colloquium on Automata, Languages, and Programming , pages 600--611. Springer, 2014

    2014

  19. [27]

    Faster k-sat algorithms using biased-ppsz

    Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, and Uri Zwick. Faster k-sat algorithms using biased-ppsz. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 578--589, 2019

    2019

  20. [28]

    A probabilistic 3—sat algorithm further improved

    Thomas Hofmeister, Uwe Sch \"o ning, Rainer Schuler, and Osamu Watanabe. A probabilistic 3—sat algorithm further improved. In STACS 2002: 19th Annual Symposium on Theoretical Aspects of Computer Science Antibes-Juan les Pins, France, March 14--16, 2002 Proceedings 19 , pages 1...

    2002

  21. [29]

    On the complexity of k-sat

    Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences , 62(2):367--375, 2001

    2001

  22. [30]

    Improved upper bounds for 3-sat

    Kazuo Iwama and Suguru Tamaki. Improved upper bounds for 3-sat. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages 328--328, 2004

    2004

  23. [31]

    Approximation algorithms for combinatorial problems

    David S Johnson. Approximation algorithms for combinatorial problems. In Proceedings of the fifth annual ACM symposium on Theory of computing , pages 38--49, 1973

    1973

  24. [32]

    Reducibility among combinatorial problemst

    Richard M Karp. Reducibility among combinatorial problemst. 1972

    1972

  25. [33]

    On coloring resilient graphs

    Jeremy Kun and Lev Reyzin. On coloring resilient graphs. In Erzs \' e bet Csuhaj - Varj \' u , Martin Dietzfelbinger, and Zolt \' a n \' E sik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29...

    2014

  26. [34]

    New methods for 3-sat decision and worst-case analysis

    Oliver Kullmann. New methods for 3-sat decision and worst-case analysis. Theoretical Computer Science , 223(1-2):1--72, 1999

    1999

  27. [35]

    A 7/8-approximation algorithm for max 3sat? In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 406--415

    Howard Karloff and Uri Zwick. A 7/8-approximation algorithm for max 3sat? In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 406--415. IEEE, 1997

    1997

  28. [36]

    Leonid A. Levin. Universal sequential search problems. Problems of Information Transmission , 9(3):265--266, 1973

    1973

  29. [37]

    Chain, generalization of covering code, and deterministic algorithm for k-sat

    Sixue Liu. Chain, generalization of covering code, and deterministic algorithm for k-sat. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) , pages 88--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2018

    2018

  30. [38]

    Online scheduling via learned weights

    Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1859--1877. SIAM, 2020

    2020

  31. [39]

    Improved rounding techniques for the max 2-sat and max di-cut problems

    Michael Lewin, Dror Livnat, and Uri Zwick. Improved rounding techniques for the max 2-sat and max di-cut problems. In International Conference on Integer Programming and Combinatorial Optimization , pages 67--82. Springer, 2002

    2002

  32. [40]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. Journal of the ACM (JACM) , 68(4):1--25, 2021

    2021

  33. [41]

    Scheduling with predictions and the price of misprediction

    Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , pages 14--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2020

    2020

  34. [42]

    0.935-approximation randomized algorithm for max 2sat and its derandomization

    Shiro Matuura and Tomomi Matsui. 0.935-approximation randomized algorithm for max 2sat and its derandomization

  35. [43]

    A birthday repetition theorem and complexity of approximating dense csps

    Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense csps. arXiv preprint arXiv:1607.02986 , 2016

    2016 arXiv

  36. [44]

    Solving satisfiability in less than 2n steps

    Burkhard Monien and Ewald Speckenmeyer. Solving satisfiability in less than 2n steps. Discrete Applied Mathematics , 10(3):287--295, 1985

    1985

  37. [45]

    A full derandomization of sch \"o ning's k-sat algorithm

    Robin A Moser and Dominik Scheder. A full derandomization of sch \"o ning's k-sat algorithm. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 245--252, 2011

    2011

  38. [46]

    Algorithms with predictions

    Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Communications of the ACM , 65(7):33--35, 2022

    2022

  39. [47]

    Improved learning-augmented algorithms for k-means and k-medians clustering

    Thy Nguyen, Anamay Chaturvedi, and Huy L Nguyen. Improved learning-augmented algorithms for k-means and k-medians clustering. In International Conference on Learning Representations . International Conference on Learning Representations, 2023

    2023

  40. [48]

    An improved exponential-time algorithm for k-sat

    Ramamohan Paturi, Pavel Pudl \'a k, Michael E Saks, and Francis Zane. An improved exponential-time algorithm for k-sat. Journal of the ACM (JACM) , 52(3):337--364, 2005

    2005

  41. [49]

    Satisfiability coding lemma

    Ramamohan Paturi, Pavel Pudl \'a k, and Francis Zane. Satisfiability coding lemma. In Proceedings 38th Annual Symposium on Foundations of Computer Science , pages 566--574. IEEE, 1997

    1997

  42. [50]

    Improving online algorithms via ml predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems , 31, 2018

    2018

  43. [51]

    An improvement of the algorithm of hertli for the unique 3sat problem

    Tong Qin and Osamu Watanabe. An improvement of the algorithm of hertli for the unique 3sat problem. Theoretical Computer Science , 806:70--80, 2020

    2020

  44. [52]

    A new approach on solving 3-satisfiability

    Robert Rodo s ek. A new approach on solving 3-satisfiability. In International Conference on Artificial Intelligence and Symbolic Mathematical Computing , pages 197--212. Springer, 1996

    1996

  45. [53]

    Near-optimal bounds for online caching with machine learned advice

    Dhruv Rohatgi. Near-optimal bounds for online caching with machine learned advice. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1834--1845. SIAM, 2020

    2020

  46. [54]

    Beyond the worst-case analysis of algorithms

    Tim Roughgarden. Beyond the worst-case analysis of algorithms . Cambridge University Press, 2021

    2021

  47. [55]

    Approximating csps with global cardinality constraints using sdp hierarchies

    Prasad Raghavendra and Ning Tan. Approximating csps with global cardinality constraints using sdp hierarchies. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms , pages 373--387. SIAM, 2012

    2012

  48. [56]

    Solving 3-satisfiability in less than 1, 579 n steps

    Ingo Schiermeyer. Solving 3-satisfiability in less than 1, 579 n steps. In Computer Science Logic: 6th Workshop, CSL'92 San Miniato, Italy, September 28--October 2, 1992 Selected Papers 6 , pages 379--394. Springer, 1993

    1992

  49. [57]

    A probabilistic algorithm for k-sat and constraint satisfaction problems

    T Schoning. A probabilistic algorithm for k-sat and constraint satisfaction problems. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) , pages 410--414. IEEE, 1999

    1999

  50. [58]

    Ppsz is better than you think

    Dominik Scheder. Ppsz is better than you think. TheoretiCS , 3, 2024

    2024

  51. [59]

    Generating hard satisfiability problems

    Bart Selman, David G Mitchell, and Hector J Levesque. Generating hard satisfiability problems. Artificial intelligence , 81(1-2):17--29, 1996

    1996

  52. [60]

    Ppsz for general k-sat-making hertli's analysis simpler and 3-sat faster

    Dominik Scheder and John P Steinberger. Ppsz for general k-sat-making hertli's analysis simpler and 3-sat faster. In 32nd Computational Complexity Conference (CCC 2017) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2017

    2017

  53. [61]

    Optimal online assignment with forecasts

    Erik Vee, Sergei Vassilvitskii, and Jayavel Shanmugasundaram. Optimal online assignment with forecasts. In Proceedings of the 11th ACM conference on Electronic commerce , pages 109--118, 2010

    2010

  54. [62]

    Optimal robustness-consistency trade-offs for learning-augmented online algorithms

    Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. Advances in Neural Information Processing Systems , 33:8042--8053, 2020

    2020

  55. [63]

    Analyzing the max 2-sat and max di-cut approximation algorithms of feige and goemans

    Uri Zwick. Analyzing the max 2-sat and max di-cut approximation algorithms of feige and goemans. 2000

    2000

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.