Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR95-060 | 21st November 1995 00:00

#### A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

TR95-060
Publication: 4th December 1995 23:16
Keywords:

Abstract:

We present a $2^{\tilde O(\sqrt{n})}$ time exact learning
algorithm for polynomial size
DNF using equivalence queries only. In particular, DNF
is PAC-learnable in subexponential time under any distribution.
This is the first subexponential time
PAC-learning algorithm for DNF under any distribution.

ISSN 1433-8092 | Imprint