-DNF Formulas (Extended Abstract).

Nader H. Bshouty Zhixiang Chen Scott E. Decatur Steven Homer

Published in: COLT (1995)

Keyphrases

extended abstract
dnf formulas
membership queries
upper and lower bounds
uniform distribution
monotone dnf
boolean functions
concept class
monotone dnf formulas
conjunctive queries
randomly chosen
truth table
np hard
theoretical analysis
concept classes