Pith. sign in

REVIEW 4 minor 6 references

A Better Analysis For PPSZ For 3-SAT

T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read A dual-certificate recombination of Scheder's PPSZ estimates improves the Unique-3-SAT base to 1.306969598^n and the general 3-SAT base to 1.307031578^n.

desk verdict Tiny but real, fully certified improvement of Scheder's PPSZ constants via dual recombination of his own estimates. read the letter →

arxiv 2607.10697 v1 pith:GXN6PF4S submitted 2026-07-12 cs.DS

Tao Jiang , Shaowei Cai This is my paper · ORCID
classification cs.DS MSC 68Q2568W2068R10
keywords PPSZ3-SATUnique-3-SATrunning-timeanalysisdualcertificateliftingtheoremexactintervalarithmetic
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

The paper re-examines Scheder's analysis of the classical PPSZ algorithm for 3-SAT without changing the algorithm itself. It keeps Scheder's regular and irregular lower bounds on success probability intact, rewrites them in shared structural coordinates (normalized counts of indegree-0 and indegree-1 variables and of variables with multiple critical clauses), and replaces the final numerical simplification by an explicit dual certificate of a three-variable linear program. The resulting Unique-3-SAT exponent improves from Scheder's 1.306972377^n to 1.306969598^n. Feeding the new unique-case bonus into the existing Scheder–Steinberger lifting theorem then yields a general 3-SAT bound of 1.307031578^n, which the authors state is the best currently known randomized worst-case running-time base. All numerical claims are certified by exact rational interval arithmetic.

What carries the argument

The affine minimax dual certificate (Proposition 3.1): a non-negative weight λ = b1/A that makes every structural coefficient of the convex combination λ L_reg + L_irr non-negative, certifying that max{L_reg, L_irr} is at least λ(A − P_reg)/(1 + λ).

What would settle it

Re-evaluate Scheder's final regular and irregular coefficient expressions at the fixed rationals ε_R ≈ 0.1024756190168075228998451658 and ε_I ≈ 0.07307238160252154687451293138; if either expression fails to be non-negative for admissible densities, the dual margins and the claimed γ* collapse.

Watch

Extended reading notes

Core claim

By expressing Scheder's unchanged regular and irregular estimates in common coordinates i0, i1, τ and exhibiting a feasible dual solution of the associated three-variable LP, one obtains a strictly larger unique-case bonus γ_new = 0.0000687793. The same lifting theorem then produces a strictly smaller general 3-SAT base O^*(1.307031578^n), claimed to be the best known randomized bound.

Load-bearing premise

The two coefficient inequalities taken from Scheder's regular and irregular analyses remain valid at the slightly larger parameters chosen here; those inequalities are used as black boxes.

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

0 major / 4 minor

Summary. The paper revisits Scheder’s analysis of the original PPSZ algorithm for Unique-3-SAT. It retains the published regular and irregular lower bounds (Imported estimates 2.1–2.2), rewrites them in the common normalized coordinates (i0, i1, τ), and recombines them via an explicit dual feasible solution of a three-variable linear program (Proposition 3.1). With fixed admissible parameters ε_R and ε_I, the dual certificate yields a unique-case bonus γ_new = 0.0000687793, improving Scheder’s 1/15218 and giving the Unique-3-SAT base O^*(1.306969598^n). The same unmodified Scheder–Steinberger lifting theorem then produces the general 3-SAT bound O^*(1.307031578^n), claimed to be the best currently known randomized worst-case bound. All numerical inequalities are certified by exact rational interval arithmetic; neither the algorithm nor the lifting theorem is altered.

Significance. The improvement is numerically small yet strictly better than the previous state-of-the-art analysis of the same algorithm, and the resulting general-3-SAT base is the best published randomized bound. The technical contribution is cleanly isolated: only the final recombination step is new, and it is reduced to a transparent dual certificate whose margins are machine-checked. The shipped exact-interval certificate, fixed rational parameters, and reproducible verification scripts are genuine strengths that raise the standard of numerical rigor in this literature. The work is incremental but solid and immediately usable by anyone relying on Scheder’s PPSZ analysis.

minor comments (4)
  1. The abstract and introduction state the new bases to nine decimals while the body works with a slightly smaller safe γ_new; a single sentence clarifying that the theorem uses a deliberately conservative truncation would avoid any impression of rounding ambiguity.
  2. Section 3.3 notes that the dual-tight point (i0=τ=0, i1≈0.060) need not be realized by a formula. A brief remark that the structural inequalities (10)–(11) are already incorporated into L_reg would make the relaxation status clearer to readers who have not memorized Scheder’s graph lemmas.
  3. Appendix A’s admissibility check for ε_I is elementary and correct, yet the printed source decimals for the coefficient functions are interpreted with source-specified rounding directions. Explicitly listing those rounding conventions (or pointing to the JSON certificate) would make the black-box import fully self-contained.
  4. The repository URL appears only in a footnote; placing it also in the main text or in a dedicated “Reproducibility” paragraph would improve discoverability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: dual recombination of imported Scheder estimates is independent of the target gain.

full rationale

The paper's only new analytic step is the common-coordinate dual certificate (Proposition 3.1) that recombines two black-box lower bounds imported from Scheder (Imported estimates 2.1–2.2). The dual multipliers and the resulting γ* are computed from those fixed coefficients; they are not defined in terms of the claimed success probability, nor fitted to any data that already encodes the target base. The subsequent Scheder–Steinberger lift is an unmodified external theorem whose numerical instantiation is interval-checked. Heavy citation of Scheder is ordinary reuse of published estimates, not a self-citation chain that forces the result by construction. No self-definitional loop, fitted-input-as-prediction, or uniqueness-from-authors step appears. Score 0 is therefore the correct outcome.

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

Virtually all analytic content is imported from Scheder (regular/irregular estimates, sibling-graph inequalities, change-of-measure) and Scheder–Steinberger (lifting theorem). The paper's only original contribution is the dual recombination of those estimates under two free numerical parameters chosen by exploratory search. No new physical or combinatorial entities are postulated.

free parameters (2)
  • ε_R (regular density parameter) = 0.1024756190168075228998451658
    Fixed decimal 0.1024756190168075228998451658 obtained by exploratory numerical search; admissible range is [0,0.13]. The dual certificate and final γ* depend on this choice.
  • ε_I (irregular density parameter) = 0.07307238160252154687451293138
    Fixed decimal 0.07307238160252154687451293138 obtained by the same exploratory search; admissible range is [0,1/5]. Directly enters the irregular coefficients b0,b1,bT.
assumptions (5)
  • domain assumption Scheder's regular lower-bound coefficient inequality (full version §7.8) holds for every admissible finite strength w and every ε_R ≤ 0.13.
    Imported estimate 2.1; used verbatim as the starting point for L_reg.
  • domain assumption Scheder's irregular lower-bound coefficient inequality (full version §8.4) holds for every admissible finite strength w and every ε_I ≤ 1/5.
    Imported estimate 2.2; used verbatim as L_irr. Admissibility of the chosen ε_I is checked only by a short density non-negativity argument (Lemma A.1).
  • domain assumption Sibling-graph inequality 18/17 |H_low| + 2 |H_high| + 3 |TwoCC| ≥ |H| and the degree-two subgraph bound |H| ≥ n − |ID1| − 2|ID0| − 2|TwoCC|.
    Equations (10)–(11), taken from Scheder; convert the regular estimate into the three structural coordinates.
  • domain assumption Scheder–Steinberger unique-to-general lifting theorem (Main Theorem 1.17 / Lifting Theorem 1.18) applies unchanged to any unique-case bonus γ > 0.
    Imported theorem 4.1; the general-case claim is obtained solely by numerical instantiation of this theorem.
  • standard math Standard change-of-measure inequality relating uniform and auxiliary distributions on permutations (Scheder Eq. (2)/(3)).
    Equation (4); classical KL-divergence argument used by Scheder and retained here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Better Analysis For PPSZ For 3-SAT." pith.science (2026). https://pith.science/paper/GXN6PF4S

@misc{pith2026260710697,
  author       = {Pith},
  title        = {Pith review of: A Better Analysis For PPSZ For 3-SAT},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GXN6PF4S}},
  note         = {Machine review of arXiv:2607.10697}
}
abstract

We revisit Scheder's analysis of the original PPSZ algorithm. Keeping his regular and irregular estimates unchanged, we express them in common structural coordinates and replace only their final recombination by an explicit linear-programming dual certificate. The old and new running-time bounds are \[ \begin{array}{c|cc} & \text{Unique-$3$-SAT} & \text{general $3$-SAT} \\ \hline \text{Scheder's analysis} & O^*(1.306972377^n) & O^*(1.307031594^n) \\ \text{this work} & O^*(1.306969598^n) & O^*(1.307031578^n). \end{array} \] In both rows, the general-case bound is obtained by applying the same existing Scheder--Steinberger unique-to-general lifting theorem to the corresponding Unique-$3$-SAT analysis. To the best of our knowledge, $O^*(1.307031578^n)$ is the best currently known worst-case randomized running-time bound for general $3$-SAT. Neither PPSZ nor the lifting theorem is modified. The numerical inequalities are certified by exact rational interval computation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 2 canonical work pages

  1. [1]

    Attias, X

    I. Attias, X. Gao, and L. Reyzin. Learning-augmented algorithms for Boolean satisfiability.CoRR, abs/2505.06146, 2025. arXiv:2505.06146

    arXiv 2025

  2. [2]

    Paturi, P

    R. Paturi, P. Pudl´ ak, M. E. Saks, and F. Zane. An improved exponential-time algorithm for k-SAT. Journal of the ACM, 52(3):337–364, 2005

    2005

  3. [3]

    D. Scheder. PPSZ is better than you think. In62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 205–216, 2021. doi:10.1109/FOCS52979.2021.00028

    doi:10.1109/focs52979.2021.00028 2021

  4. [4]

    D. Scheder. PPSZ is better than you think.Electronic Colloquium on Computational Complexity, Report TR21-069, Revision 1, 2021. stable Revision 1 PDF

    2021

  5. [5]

    D. Scheder. PPSZ is better than you think.TheoretiCS, Volume 3, Article 5, pages 1–37, 2024. doi:10.46298/theoretics.24.5

    work page doi:10.46298/theoretics.24.5 2024

  6. [6]

    Scheder and J

    D. Scheder and J. P. Steinberger. PPSZ for general k-SAT and CSP—making Hertli’s analysis simpler and 3-SAT faster.Computational Complexity, 33, Article 13, pages 1–48, 2024. doi:10.1007/s00037-024- 00259-y. 15

    work page doi:10.1007/s00037-024- 2024

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.