Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm
Weiming Feng, Yixiao Yu, Yiyao Zhang
cs.LG · cs.DS
Quick verdict
Near-tight Õ(n^⌈t⌉/ε) sample bounds for Valiant's CNF learning in the local lemma regime; rigorous proofs; t>1 lower bound is algorithm-specific.
Summary
The paper re-analyzes Valiant's 1984 clause-elimination algorithm for learning k-CNF formulas with bounded variable degree d from i.i.d. uniform satisfying assignments. Theorem 4.1 shows that for constants k ≥ 100, d and fixed t ≥ 1, under the local lemma condition k ≥ (1+1/t)log d + 2log k + t − 3log t + 5, the algorithm achieves total variation error ε with Õ_{k,d,t}(n^⌈t⌉·ln(1/δ)/ε) samples. For every fixed t > 1, Theorem 5.1 constructs layered-gadget instances satisfying the same condition on which Valiant's algorithm needs Ω_{k,t}((n/log n)^⌈t⌉/ε0) samples, so the exponent of n is tight for this algorithm. At t = 1, a new information-theoretic lower bound Ω_k(n/(ε0·log n)) for (k,k)-CNFs (Theorem 6.2, Appendix B) improves Feng et al.'s (STOC'26) exponent from 1−2/k to 1 and widens the error range to (0,1/4), making the near-linear upper bound optimal up to logarithms. The upper-bound proof partitions rare candidate clauses by large overlaps with target clauses and recursively refines classes via maximal variable-disjoint subfamilies, with explicit constants. A bonus result (Theorem 6.3) learns all bounded-degree CNFs with Õ(n/ε) samples in exp(O(n log n)) time, without any local lemma condition. Limitations: enormous hidden constants, asymptotic guarantees requiring k ≥ 100, and a t > 1 lower bound that constrains only Valiant's algorithm, not all learners.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 1
● low 3
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Under k ≥ (1+1/t)log d + 2log k + t − 3log t + 5 with constants k ≥ 100 and d, Valiant's algorithm learns any (k,d)-CNF to total variation error ε with Õ_{k,d,t}(n^⌈t⌉·ln(1/δ)/ε) samples (Theorem 4.1).
- For every fixed t > 1 there are (k,d)-CNF instances satisfying the same local lemma condition on which Valiant's algorithm requires Ω_{k,t}((n/log n)^⌈t⌉/ε0) samples for error ε0 with probability 1/3 (Theorem 5.1).
- Any learning algorithm requires Ω_k(n/(ε0·log n)) i.i.d. samples for (k,k)-CNFs with error ε0 ∈ (0,1/4), improving the exponent 1−2/k of FYYZ26b to 1 (Theorem 6.2).
- Without any local lemma condition, Õ_{k,d}(n/ε) samples with exp(O_{k,d}(n log n)) time learn every satisfiable bounded-degree CNF, matching the t=1 information-theoretic bound up to log factors for d = k (Theorem 6.3).
- The sample-complexity exponent of n for Valiant's algorithm increases by one each time t crosses a positive integer, forming the staircase of Figure 1 that approaches the satisfiability line k ≳ log d.
Strengths
Near-tight two-sided characterization
Theorem 4.1 (upper bound Õ(n^⌈t⌉·ln(1/δ)/ε) under k ≥ (1+1/t)log d + 2log k + t − 3log t + 5) and Theorem 5.1 (lower bound Ω_{k,t}((n/log n)^⌈t⌉/ε0) on layered gadgets) match up to log factors for every fixed t > 1, yielding the staircase phase diagram of Figure 1 with the exponent of n stepping up at each integer t.
Genuinely stronger information-theoretic lower bound
Theorem 6.2 with Lemma B.2 improves FYYZ26b (Theorem 6.1) from exponent 1−2/k to 1 for (k,k)-CNFs and widens the error range from (0, 1/(400·2^k)) to (0,1/4), via a spectral estimate N_ℓ = Θ(λ_k^ℓ) with λ_k = 2^{k−1} − 1 + √(2^{k−1}(2^{k−1}−k)) for the 2×2 transition matrix of the reused gadgets.
Fully explicit constants and verifiable local-lemma bookkeeping
Honest scoping and failure-mode analysis
Transparent AI-assistance disclosure
Weaknesses
Polylogarithmic gap with k-dependent exponent
Restriction to k ≥ 100
t > 1 lower bound is algorithm-specific
Compressed proof steps
Confidence-parameter asymmetry
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper studies Problem 1.3: learning an unknown (k,d)-CNF formula (clause width k, variable degree at most d) from T i.i.d. uniform satisfying assignments, with error measured in total variation distance. The object of study is precisely Valiant's 1984 clause-elimination algorithm. Three claims anchor the contribution. (1) Theorem 4.1: for constants k ≥ 100, d and fixed t ≥ 1, under the quantitative local lemma condition k ≥ (1+1/t)log d + 2log k + t − 3log t + 5, the algorithm achieves error ε with N = O_{k,d,t}((n^⌈t⌉/ε)·(ln(n/ε))^{k+1}·ln(n/δ)) samples and O(n^k·N) time. (2) Theorem 5.1: for every fixed t > 1, instances satisfying the same condition exist (layered implication gadgets with degree d = 2^a + 2^{k−a} − 2, k = a⌈t⌉ + ρ) on which Valiant's algorithm needs Ω_{k,t}((n/log n)^⌈t⌉/ε0) samples for error ε0 with success probability 1/3. (3) Theorem 6.2 (Appendix B): an information-theoretic Ω_k(n/(ε0·log n)) lower bound for (k,k)-CNFs, strengthening FYYZ26b (Theorem 6.1) from exponent 1−2/k to 1 and from error range (0, 1/(400·2^k)) to (0,1/4). A bonus, Theorem 6.3: with no local lemma condition, exhaustive search learns every satisfiable (k,d)-CNF with O_{k,d}((n/ε)(log n + log(1/δ))) samples in exp(O_{k,d}(n log n)) time. Figure 1 summarizes this as a phase diagram: the exponent f(C) of n under k ≳ C log d is a staircase approaching the satisfiability line, and its t = 1 knee sits near the 2log d location of the counting transitions of HWY23 and LWY+26 (Section 1.2).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is Valiant's algorithm for learning CNF formulas?
It is the 1984 clause-elimination procedure: start from all width-k candidate clauses over the n variables and delete any clause violated by an observed sample; the surviving clauses form the hypothesis CNF. Valiant introduced it for PAC learning; this paper analyzes the same algorithm when samples are uniform random satisfying assignments of a bounded-degree CNF.
What does the local lemma regime mean in this paper?
It is the parameter range where the symmetric Lovász local lemma guarantees a k-CNF formula with variable degree d is satisfiable: under uniform random bits a clause is violated with probability 2^{−k} and depends on at most k(d−1) other clauses, so satisfiability holds once k ≳ log d. The paper works under the stronger condition k ≥ (1+1/t)log d plus lower-order terms.
How many samples are needed to learn a bounded-degree CNF formula?
By Theorem 4.1, Õ(n^⌈t⌉/ε) samples under k ≳ (1+1/t)log d for constants k ≥ 100; at t = 1 this is near-linear Õ(n/ε), matching an information-theoretic lower bound up to logarithmic factors. Without any local lemma condition, Õ(n/ε) samples still suffice but the algorithm needs exp(O(n log n)) time.
Is the lower bound in this paper information-theoretic or specific to one algorithm?
Both, in different regimes. For t > 1 the matching lower bound applies only to Valiant's algorithm, via explicitly constructed hard instances. For t = 1 the Ω(n/(ε log n)) bound is information-theoretic: no algorithm whatsoever can learn (k,k)-CNFs with fewer samples, up to the same log factors.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Displayed equations were mangled by text extraction (e.g., formal statements of Theorems 5.1 and 6.2); bounds were reconstructed from surrounding prose and the proof endgames, so notation-level details may differ.
- Figures 1-6 are available only as captions; the phase diagram and gadget illustrations could not be inspected.
- Line-by-line re-derivation of Section 4.3's two-case LLL analysis and Appendix B's spectral constants was not performed; steps marked direct computation remain unverified by this review.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.