Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

Description

We prove a new structural lemma for partial Boolean functions f, which we call the seed lemma for DNF. Using the lemma, we give the first subexponential algorithm for proper learning of poly(n)-term DNF in Angluin's Equivalence Query (EQ) model. The algorithm has time and query complexity 2(?n), which is optimal. We also give a new result on certificates for DNF-size, a simple algorithm for properly PAC-learning DNF, and new results on EQ-learning log n-term DNF and decision trees.

Questions and Answers

You need to be logged in to be able to post here.