{"id":"a4524444-b35b-4646-bb2a-88f50ce7a9be","arxiv_id":"2505.06146","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Subset advice provably reduces the exponential base of PPSZ for k-SAT and lifts MAX-SAT approximation from alpha to alpha + (1-alpha)*epsilon, while noisy label advice gives near-optimal MAX-2-SAT on high-average-degree instances.","lead":"This paper shows that machine-learned advice, in the form of hints about an optimal assignment, can speed up exponential-time SAT solvers and improve MAX-SAT approximation guarantees. It is worth reading because it brings the learning-augmented framework to a central NP-hard problem and quantifies exactly how much advice is needed for the improvements.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"General-k-SAT PPSZ claim fails on disjoint-clauses formulas: advice-specific saving does not lift from Unique-SAT; E[G] is linear at epsilon=1/2.","rationale":"Good-faith reading: the paper's core theoretical novelty is the claim that a random epsilon-fraction of an optimal assignment multiplicatively improves the base of PPSZ's worst-case exponent for general k-SAT, including sub-exponential time at epsilon >= (k-2)/(k-1). I examined the proof of Theorem 2.2 closely. The algebra of the change of variable u = epsilon+(1-epsilon)r is correct, and for Unique-k-SAT the recursive critical-clause equation [epsilon+(1-epsilon)(r+(1-r)R)]^{k-1} = R is a reasonable extension of PPSZ. The problem is the step from Unique-k-SAT to general k-SAT. The cited lifting theorems (Hertli; Scheder-Steinberger) show that PPSZ's success probability for finding some satisfying assignment in a general satisfiable formula is at least its success probability in the unique case. They do not show that the probability of finding the particular assignment x* used to generate the advice is preserved. The advice-specific saving epsilon_k is exactly a statement about finding x*: it counts how many variables are forced along the path to x*. In a formula with multiple satisfying assignments, x* need not have a critical clause for every variable, so the analysis of the forcing probability collapses. The disjoint-clauses formula makes this concrete: with epsilon=1/2, only the roughly m/8 clauses with no advised variable are active; each such clause is satisfied with probability 7/8 by random guesses, giving success probability 2^{-Theta(n)} and hence 2^{Theta(n)} expected iterations. This directly contradicts Corollary 2.3's 2^{o(n)}. The same failure applies to the general k-SAT exponents: the improvement is real only in the Unique-k-SAT setting or for formulas where x* is critical in the required sense. The paper's other contributions - the black-box MAX-SAT with subset advice, the label-advice MAX-2-SAT algorithm (modulo the unproved rounding step), and the hardness reductions - are largely orthogonal and appear mostly sound, but the headline decision-problem result as stated for k-SAT is false. Hence the reader's CONDITIONAL verdict should move to REJECT unless the paper is revised to restrict the PPSZ claim to Unique-k-SAT and clearly state that the general-k-SAT version is an open problem.","tokens_in":18184,"tokens_out":31972,"duration_ms":311915,"concrete_test":"Run Algorithm 1 (with D=omega(1)) on F_m for n=3m up to a few hundred, epsilon=1/2, advice from x*=1^n; measure the fraction of iterations that find a satisfying assignment and the number of guessed variables. The data should show success probability approximately (63/64)^m and E[G] approximately 0.448n, contradicting the paper's o(n) guess bound. Analytically, compare E[G] from Equation (2) (which is o(n) at epsilon=1/2) with the exact value for F_m: E[G] = (7/8)(3/2)m + (1/8)(7/4)m = 1.34375m = 0.448n. The discrepancy settles the concern.","verdict_should_be":"REJECT","load_bearing_attack":"Section 2 proves the improved PPSZ bound under the Unique-k-SAT critical-clause analysis and then cites Hertli/Scheder-Steinberger to lift it to general k-SAT. The lifting is not valid for the advice-specific saving epsilon_k: Hertli's theorem guarantees that PPSZ finds some satisfying assignment with the unique-case probability, not that it finds the particular assignment x* that generated the advice. This is not just a missing proof; the claimed general-k-SAT statement is false. Take F_m = \\wedge_{j=1}^m (x_{3j-2} \\vee x_{3j-1} \\vee x_{3j}), x* = 1^n, epsilon = 1/2. After fixing the advice, a clause is already satisfied iff at least one of its 3 variables lies in S (probability 7/8, independent). If K ~ Binomial(m,1/8) clauses have no variable in S, PPSZ must satisfy those K active clauses by random guesses; each is satisfied with probability 7/8. Hence the per-iteration success probability is E[(7/8)^K] = (63/64)^m = 2^{-Theta(n)}, so the expected number of iterations is 2^{Theta(n)}, contradicting the claimed O*(2^{o(n)}). Equivalently, E[G] for this instance is Theta(n), not o(n) as Equation (2) predicts, because the variables in clauses already satisfied by the advice are not forced (no critical clause for x*). The per-variable forcing bound in Theorem 2.2 requires every variable of x* to lie in a critical clause, which fails when the reduced formula has many satisfying assignments.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18460,"tokens_out":19637,"duration_ms":186066,"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":[{"comment":"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.","section":"Section 2.2, Theorem 2.2 and Eq. (2)"},{"comment":"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.","section":"Section 2.1, Theorem 2.1"},{"comment":"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.","section":"Appendix B, Theorem 3.6 and Algorithm 2"}],"minor_comments":[{"comment":"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.","section":"Section 3.2, proof of Theorem 3.5"},{"comment":"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.","section":"Definition 1.4 and Section 3.3"},{"comment":"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.","section":"Corollary 2.3 and Table 1"}],"recommendation":"reject","confidential_remarks":"The headline PPSZ-with-subset-advice result for general k-SAT is false, as demonstrated by the disjoint-clauses counterexample. The MAX-SAT subset-advice black-box improvement is correct, and the label-advice MAX-2-SAT section is promising but needs a rigorous rounding argument. The authors should also revisit the PPZ theorem, which inherits the same critical-clause issue. Unless the decision-problem claims are withdrawn or restricted to Unique-k-SAT, the paper's main advertised contribution is invalid. I recommend rejection, though a future version that honestly states only the Unique-SAT result and supplies the missing rounding proof for Theorem 3.6 could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi [Colleague],\n\nThe headline: the PPSZ-with-advice theorem is a real idea, but the paper overclaims the lifting from Unique-k-SAT to general k-SAT. The stress-test's disjoint-clauses counterexample doesn't hold up—PPSZ actually satisfies each disjoint clause with probability one—but the concern it points at is valid.\n\nWhat's actually new: Section 2 derives the PPSZ forcing probability with subset advice. The change of variable u = ε+(1−ε)r is clean, and for the unique case the exponent ε_k = ε − ∫_0^ε R_k(r)dr is correct. The claim of sub-exponential time at ε = 1/2 in the unique case is plausible. The black-box subset advice for MAX-SAT (Theorem 3.1) is correct and simple: fixing ε-fraction of OPT and then running an α-approximation gives α+(1−α)ε. The MAX-2-SAT label advice algorithm extends GMM25 to a non-symmetric CSP, with the same high-degree condition.\n\nThe soft spots: (1) The general-k-SAT statement of Theorem 2.2 is not supported. The proof computes E[G] under the unique-SAT critical-clause assumption. Hertli's lifting guarantees that for any formula and a fixed satisfying assignment x*, PPSZ finds x* with probability at least the unique-case bound 2^{-(1-R_k)n}. But that bound scales with n' = (1−ε)n if you merely run PPSZ on the reduced formula; it does not give the improved exponent ε_k. To get the improved exponent, you need a lifting that preserves the advice-specific saving. The paper doesn't provide one. So the theorem should either be restricted to Unique-k-SAT or accompanied by an honest proof of the lifting. (2) The hardness proofs in Theorems 2.5 and 3.5 enumerate assignments to a fixed subset, but the advice model gives a random subset; the simulation should enumerate over all (S, assignment) pairs. This is fixable by choosing ε small so that the total enumeration is 2^{o(n)}. (3) Algorithm 2's rounding step is delegated to GMM25 without proof for the modified objective; that's a gap but probably minor.\n\nIf the authors fix or restrict (1), the paper is a solid contribution to learning-augmented algorithms for SAT. As is, the central claim is not established.\n\nWho for: researchers in algorithms with predictions and exact exponential algorithms. Worth a serious referee, but ask for revision. I'd cite the MAX-SAT black-box result.","headline":"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.","tokens_in":19090,"tokens_out":14290,"would_cite":true,"duration_ms":137981,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A random sample of an optimal assignment provably shrinks the worst-case exponent of k-SAT and MAX-SAT algorithms.","keywords":["learning-augmented algorithms","algorithms with predictions","Boolean satisfiability","k-SAT","PPSZ","MAX-SAT","subset advice","label advice"],"falsifier":"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.","tokens_in":17910,"feed_emoji":"⚡","tokens_out":11674,"duration_ms":116941,"temperature":0.7,"pith_summary":"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.","feed_headline":"Half of an optimal assignment puts 3-SAT in sub-exponential time","feed_subtitle":"Even a random epsilon-fraction of an optimal assignment shrinks PPSZ's exponent and lifts MAX-SAT approximation ratios.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the original PPSZ algorithm, its random-restriction analysis, and the fixed-point function $R_k$ used throughout.","marker":"[PPSZ05]"},{"why":"Supplies the black-box lifting that transfers Unique-$k$-SAT PPSZ bounds to general $k$-SAT, on which Theorem 2.2's general-$k$ claim rests.","marker":"[Her14a]"},{"why":"Simplifies and generalises the PPSZ analysis and provides the version of the lifting used for the general $k$-SAT results.","marker":"[SS17]"},{"why":"Gives the PPZ algorithm whose forced-variable probability Theorem 2.1 extends to subset advice.","marker":"[PPZ97]"},{"why":"Provides the quadratic-programming approach and lemmas that Algorithm 2 adapts for MAX-2-SAT with label advice.","marker":"[GMM25]"},{"why":"Supplies the $7/8$-approximation for MAX-3-SAT that Corollary 3.3 upgrades with subset advice.","marker":"[KZ97]"},{"why":"Supplies the $0.940$-approximation for MAX-2-SAT that Corollary 3.2 upgrades.","marker":"[LLZ02]"},{"why":"States the Exponential Time Hypothesis used for the hardness of 3-SAT with subset advice.","marker":"[IP01]"},{"why":"States the Gap-ETH assumption used for the hardness of MAX-3-SAT with subset advice.","marker":"[Din16]"},{"why":"Provides the Gap-ETH formulation used alongside Dinur's paper for the MAX-3-SAT hardness.","marker":"[MR16]"}],"fun_headline_variants":["Epsilon fraction of optimal assignment speeds up k-SAT","Half of the optimal set makes 3-SAT sub-exponential","PPSZ exponent shrinks with random subset advice","Black-box advice lifts any MAX-SAT approximation","Label advice nearly optimal MAX-SAT on high-degree instances"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Epsilon fraction of optimal assignment speeds up k-SAT","Half of the optimal set makes 3-SAT sub-exponential","PPSZ exponent shrinks with random subset advice","Black-box advice lifts any MAX-SAT approximation","Label advice nearly optimal MAX-SAT on high-degree instances"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000421,"raw_usage":{"total_tokens":2281,"prompt_tokens":1178,"completion_tokens":1103,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":794,"completion_tokens_details":{"reasoning_tokens":1023}},"tokens_in":794,"tokens_out":1103,"duration_ms":11784,"temperature":1.0,"reasoning_tokens":1023,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:49:28.476145+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}