{"id":"1cd39f92-1b6d-4555-8c4d-b2fa925607a1","arxiv_id":"2607.10697","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"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.","lead":"A refined recombination of Scheder's existing PPSZ estimates yields slightly better worst-case running-time bases for Unique-3-SAT and general 3-SAT. The improvement is tiny but certified by exact rational arithmetic and currently the best published randomized bound for general 3-SAT.","discovery_kind":"incremental","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The paper’s contribution is deliberately narrow: it leaves Scheder’s regular and irregular estimates untouched, rewrites them in common coordinates (i0,i1,τ), and replaces only the final max recombination by a feasible dual solution whose margins are machine-checked. All free parameters are fixed before certification; the dual certificate is tight for the three-variable relaxation and the lifting calculation is a direct numerical specialization of an existing theorem. Because the new arithmetic is fully reproducible and the imported black boxes are the same ones used by the previous state-of-the-art bound, there is no load-bearing gap that would reverse or condition the ACCEPT verdict. The reader’s identification of the imported estimates as the weakest assumption is accurate; that assumption is inherited, not created, and does not undermine the incremental claim.","tokens_in":11589,"tokens_out":485,"duration_ms":42410,"concrete_test":"Independently re-evaluate the dual objective λ(A-Preg)/(1+λ) and the three dual inequalities at the exact rationals of (20) using an independent interval library (e.g., mpmath or Arb) with working precision ≥100 bits; confirm that γ* exceeds 0.0000687793 and that both lifted η∞ brackets remain strictly above the theorem constants 0.000000364 and the published bases.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on recombining two imported Scheder estimates (regular §7.8 and irregular §8.4) via an explicit dual certificate at fixed admissible parameters ε_R≈0.10248, ε_I≈0.07307. Appendix A verifies the irregular parameter lies inside the source density-nonnegativity range ε_I≤1/5; the dual margins (b0-2b1>0, bT+λS>0) and the resulting γ* are certified by exact rational interval arithmetic shipped with the paper. The Scheder–Steinberger lift is applied without modification and its numerical instantiation is likewise interval-checked. No internal inconsistency, hidden assumption, or unverified numerical step appears in the new material. The only residual risk is the black-box status of the imported coefficient inequalities themselves, which is already the literature baseline and is not introduced by this work.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":11723,"tokens_out":689,"duration_ms":14876,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"The repository URL appears only in a footnote; placing it also in the main text or in a dedicated “Reproducibility” paragraph would improve discoverability.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a pure analysis improvement of a well-known algorithm; its novelty is modest but the execution is careful and the numerical claims are unusually well certified. It is a good fit for a theory journal that values incremental but rigorously verified progress on exponential-time algorithms. I see no citation or priority issues."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper does one clean thing: it rewrites Scheder's regular and irregular gain estimates in shared coordinates (i0, i1, τ) and recombines them with an explicit three-variable dual certificate instead of the old max-of-two simplification. Everything else—PPSZ itself, the structural inequalities, the change-of-measure, and the Scheder–Steinberger lift—is left untouched. The payoff is a strictly larger unique-case bonus (γ_new ≈ 6.88e-5 vs Scheder's 6.57e-5) and, after the same lift, a general 3-SAT base of 1.307031578^n, which is the best published randomized worst-case number right now.\n\nWhat they do well is the bookkeeping. Parameters are fixed first (ε_R ≈ 0.10248, ε_I ≈ 0.07307), dual margins are positive, and every numerical claim is certified by exact rational interval arithmetic that ships with the paper. The finite-strength quantifier order is handled carefully so no ε_w n term is swept into o(n). Appendix A checks that the irregular parameter stays inside Scheder's density-nonnegativity range. The dual argument itself (Prop. 3.1) is elementary and tight for the relaxation they solve.\n\nThe soft spot is exactly the one the reader flags: the two coefficient inequalities are imported black boxes. That is not a new risk; it is the literature baseline. The absolute improvement is on the order of 10^{-8} in the base, so this is pure specialized-constant chasing. No claim is made that the parameters are globally optimal once all structural constraints are restored.\n\nThis is for people who track the exact exponential bases for k-SAT. The math is solid, the code is there, and the citation pattern is honest. I would send it to referees without hesitation; it is a correct, reproducible, narrowly scoped update of the state-of-the-art constant.","headline":"Tiny but real, fully certified improvement of Scheder's PPSZ constants via dual recombination of his own estimates.","tokens_in":12379,"tokens_out":501,"would_cite":true,"duration_ms":7671,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","68R10"],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["PPSZ","3-SAT","Unique-3-SAT","running-time analysis","dual certificate","lifting theorem","exact interval arithmetic"],"falsifier":"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.","tokens_in":12436,"feed_emoji":"⏱️","tokens_out":651,"duration_ms":7586,"temperature":0.7,"pith_summary":"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.","feed_headline":"PPSZ analysis tightened to 1.307031578^n for 3-SAT","feed_subtitle":"Only the recombination of Scheder's estimates changes; the algorithm and lifting theorem stay the same.","key_machinery":"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 + λ).","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Dual LP recombination tightens PPSZ 3-SAT to 1.307031578^n","Scheder estimates via dual yield O*(1.307031578^n) for 3-SAT","Feasible dual on common coords improves PPSZ unique base to 1.306969598^n","Unchanged PPSZ analysis gives best known 1.307031578^n randomized bound","Exact dual certificate lifts Scheder PPSZ to O*(1.307031578^n)"],"cache_read_input_tokens":128,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Dual LP recombination tightens PPSZ 3-SAT to 1.307031578^n","Scheder estimates via dual yield O*(1.307031578^n) for 3-SAT","Feasible dual on common coords improves PPSZ unique base to 1.306969598^n","Unchanged PPSZ analysis gives best known 1.307031578^n randomized bound","Exact dual certificate lifts Scheder PPSZ to O*(1.307031578^n)"]},"model":"grok-4.5","effort":"low","cost_usd":0.006568,"raw_usage":{"total_tokens":1684,"prompt_tokens":788,"num_sources_used":0,"completion_tokens":108,"cost_in_usd_ticks":65680000,"prompt_tokens_details":{"text_tokens":788,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":788,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":788,"tokens_out":108,"duration_ms":6563,"temperature":1.0,"reasoning_tokens":788,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T09:55:15.649340+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}