Speaker: Lisa Hellerstein
Polytechnic Institute of NYU
Title: DNF Formulas: Certificates and Learning
We present new results on two related types of problems involving DNF formulas: certificates and learning.
Certificate problems for DNF formulas concern the number of points of a Boolean function needed to certify that the function requires a ``large'' DNF. DNF-learning problems concern the problem of learning the function computed by an unknown DNF formula, given ways of gathering information about that formula.
This talk covers joint work with Devorah Kletenik, Linda Sellie, and Rocco Servedio.