Shrinkage of Decision Lists and DNF Formulas.

Benjamin Rossman

Published in: CoRR (2020)

Keyphrases

dnf formulas
decision lists
term dnf
concept class
concept classes
pac model
membership queries
upper and lower bounds

learning theory
pac learning
sample complexity
decision trees
uniform distribution
upper bound
vc dimension
efficient learning

conjunctive queries
statistical queries
agnostic learning
target function
target concept
learning models
boolean functions
computational learning theory

rule sets
lower bound
concept learning
noise tolerant
equivalence queries
mistake bound
exact learning
query answering