On Attribute Efficient and Non-Adaptive Learning of Parities and DNF Expressions

Abstract

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over 0,1^ n . We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem in coding theory. An algorithm is said to use membership queries (MQs) non-adaptively if the points at which the algorithm asks MQs do not depend on the target concept. We give a deterministic and a fast randomized attribute-efficient algorithms for learning parities by non-adaptive MQs. Using our non-adaptive parity learning algorithm and a modification of Levin’s algorithm for locating a weakly-correlated parity due to Bshouty et al., we give the first non-adaptive and attribute-efficient algorithm for learning DNF with respect to the uniform distribution. Our algorithm runs in time ${\tilde O}(ns^{4}/\epsilon)$ and uses ${\tilde O}(s^{4}/\epsilon)$ non-adaptive MQs where s is the number of terms in the shortest DNF representation of the target concept. The algorithm also improves on the best previous algorithm for learning DNF (of Bshouty et al. ).