Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-060 | 21st November 1995 00:00

A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

RSS-Feed




TR95-060
Authors: Nader Bshouty
Publication: 4th December 1995 23:16
Downloads: 2055
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