Fitting and Learning Basis-Restricted Propositional Formulas
For a finite set $O$ of Boolean functions, we consider the class of propositional formulas built using the functions in $O$ as connectives. We determine, for each possible choice of $O$, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss
Lineage graph
Paper → model → repo connections mined from source citations (Tier-1 exact match).
Why these links exist
Every edge carries a method, confidence, and the source snippet that justified it — so bad links are debuggable.
- PossiblePossibly related (embedding) · 45%Algorithm optimizes machine learning techniques that use linear, tunable resistor networks - aip.org →
- PossiblePossibly related (embedding) · 45%Machine Learning Help at 10th Grade Level [D] →
- FuzzySimilar title/name (fuzzy) · 84%amitness/learning →
“Fuzzy title match (0.92): “Fitting and Learning Basis-Restricted Propositional Formulas” ≈ “amitness/learning””
- LinkedLinked via arxiv author · 85%Balder ten Cate →
“Fitting and Learning Basis-Restricted Propositional Formulas”