Complexity Theoretic Limitations on Learning DNF's.

Amit Daniely Shai Shalev-Shwartz

Published in: COLT (2016)

Keyphrases

complexity theoretic
uniform distribution
consistent query answering
learning dnf
prime implicates
database
databases
pac learning
model checking
learning theory
dnf formulas