Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Attribute-efficient:
TR06-066 | 5th May 2006
Vitaly Feldman

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

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint