Fitting and Learning Basis-Restricted Propositional Formulas
cs.LO · cs.LG
Quick verdict
Classifies fitting, ERM, PAC and SQ learning for every Boolean basis via Post's lattice; partly a synthesis, but the new ERM trichotomy is sound.
Summary
The paper classifies the complexity of fitting and learning problems for propositional formula classes PL_O defined by a finite basis O of Boolean connectives, sweeping all of Post's lattice. (1) Fitting — deciding whether a labeled sample is realizable and constructing a fitting formula — is polynomial-time for every fixed basis, via a divide-and-conquer refinement of the Baker–Pixley theorem (Proposition 3.1) yielding polynomial-size, logarithmic-depth terms. (2) Empirical risk minimization receives a new trichotomy (Theorem 1.3): for the conjunction, disjunction and parity intervals, no weak approximator exists unless P=NP (via Håstad's Max-E3Lin and Feldman et al.'s monomial hardness); for the degree-k separating clones and the majority clone, ERM is NP-hard but admits a k-approximation, optimal under the Unique Games Conjecture, via LP rounding and an objective-preserving vertex-cover reduction; all remaining bases are polynomial-time solvable by min-cut and forcing arguments. (3)-(4) The Occam and PAC/statistical-query classifications are largely reorganizations of Dalmau's and Kearns's results; the genuine fill is showing that Dalmau's PAC-learnability dichotomy, previously proved only for circuits, extends to formulas by balancing source formulas before gadget substitution. Limitations: negative results are conditional (P≠NP, UGC, cryptographic assumptions); attribute-efficiency for affine bases and learning parities with noise remain open; the constraint-language extension in Section 9 gives worked examples rather than a classification.
Review complete
Assessment at a glance
2
risk flags identified
● high 0
● medium 0
● low 2
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
- Fitting is decidable, and a polynomial-size fitting formula constructible, in polynomial time for every fixed finite basis (Theorem 1.1), via a divide-and-conquer refinement of the Baker–Pixley theorem giving logarithmic-depth terms (Proposition 3.1).
- ERM over Post's lattice obeys a trichotomy (Theorem 1.3): no weak approximator unless P=NP for the conjunction/disjunction/parity intervals; NP-hard with a UGC-optimal k-approximation for the degree-k separating clones and the majority clone D2; polynomial-time for every other basis.
- Dalmau's PAC-learnability dichotomy, previously proved only for circuits, holds also for formulas; the gap is closed by balancing source formulas before gadget substitution and carrying truth constants in auxiliary variables (Theorem 1.5, Lemmas 6.5–6.7).
- Occam algorithms exist for the conjunctive, disjunctive and unary bases (attribute-efficiently) and for the affine interval (non-attribute-efficiently, status open), and nowhere else under cryptographic assumptions (Theorem 1.2); SQ-learnability holds iff the basis is conjunctive, disjunctive or essentially unary (Theorem 1.6).
Strengths
Complete uniform map over Post's lattice
For every finite basis O (Table 1 enumerates all clones with bases), the paper determines the status of five tasks simultaneously (fitting, ERM, VC dimension, PAC, Occam, SQ), summarized per region in Figure 1 — a genuinely useful reference artifact for cs.LO/cs.LG.
Efficient Baker–Pixley interpolation is a real technical contribution
Proposition 3.1 strengthens the classic theorem with a divide-and-conquer construction (block partitioning, |S\Bi| < (1−1/2d)^s analysis) giving fitting terms of O(log m) depth and polynomial size; this refines the subpower-membership machinery of [40, 14] and is reusable beyond learning.
ERM trichotomy is assembled cleanly with correct attribution
Honest provenance and open-problem discipline
The circuit-to-formulas gap fill is correct and fully written out
Weaknesses
Novelty is narrower than the framing suggests
All negative results are conditional, and the abstract does not say so
Section 9 is a survey of examples, not a classification
Constant-basis restriction is nowhere discussed as a limitation
LLM assistance in obtaining technical results
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper asks how the complexity of core learning-theoretic tasks depends on which Boolean connectives are available. For every finite basis O (equivalently, every clone of Post's lattice, all listed with bases in Table 1), it determines the status of: fitting (realizability plus construction), Occam compression, empirical risk minimization (ERM), PAC learning/prediction, and statistical-query learning — uniformly for formulas PL_O (trees) and circuits CIR_O. The author is explicit in §1 that contributions are 'partly organizational': Theorems 1.2, 1.5 and 1.6 trace to Dalmau [16] and Kearns/Blum et al. [28, 9]. The novel results are the efficient Baker–Pixley fitting algorithm (Proposition 3.1), the ERM trichotomy (Theorem 1.3), and the extension of Dalmau's PAC dichotomy from circuits to formulas. Claims are stated precisely, with conditionality (P≠NP, UGC, cryptographic assumptions of §6) flagged in the figure caption and body text.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 2 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 the main result of this paper?
It gives a complete complexity map, over all possible finite sets of Boolean connectives (equivalently, all clones of Post's lattice), of five learning-theoretic tasks for propositional formulas and circuits: fitting (always polynomial-time, with a new divide-and-conquer construction), empirical risk minimization (a new trichotomy: inapproximable / k-approximable optimally under UGC / easy), plus Occam compression, PAC learning and statistical-query learning (tractable exactly for conjunction-like, disjunction-like and, for PAC, parity-like connective sets, under standard hardness assumptions for the negative parts).
Does the paper solve the learning parities with noise (LPN) problem?
No. For parity/affine connective bases, PAC learning under random classification noise is exactly LPN and remains open; the paper resolves only the statistical-query variant negatively for affine bases (unconditionally, via pairwise-uncorrelated parities under the uniform distribution).
Are the hardness results in the paper unconditional?
No. The ERM lower bounds hold unless P=NP, the approximation-factor optimality in the threshold regime holds under the Unique Games Conjecture, and the PAC/Occam/SQ negative results rely on standard cryptographic assumptions (hardness of quadratic residuosity, RSA inversion, and factoring Blum integers). All conditional entries are marked in the paper's Figure 1.
Was AI used to write this paper?
Yes, and it is disclosed in the acknowledgements: Claude was used editorially and as a tool in the creative process, and 'several of the technical results were obtained with its help'. The proofs themselves are written out in full in the paper, so they can be verified independently.
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.
- Figure 1's lattice diagram extracts as flattened clone-name text; the accompanying region/status table is fully legible in the extracted text, but the visual edge structure of Post's lattice could not be checked.
- Proofs were verified by close reading of the main novel lemmas (4.1, 4.5, 4.7, 4.9, 6.5–6.7, Proposition 3.1's recursion analysis), not line-by-line formal verification of every derived case.
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.