-term DNF formulas from satisfying assignments.
Maciej LiskiewiczMatthias LutterRüdiger ReischukPublished in: J. Comput. Syst. Sci. (2019)
Keyphrases
- monotone dnf formulas
- dnf formulas
- monotone dnf
- membership queries
- upper and lower bounds
- uniform distribution
- boolean functions
- polynomial size
- conjunctive queries
- randomly chosen
- term dnf
- concept classes
- truth table
- statistical queries
- data model
- concept class
- database
- query processing
- database systems
- learning algorithm