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,1n. 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. This is the first evidence that attribute-efficient learning of a natural PAC learnable concept class can be computationally hard.
Cite
Text
Feldman. "Attribute-Efficient and Non-Adaptive Learning of Parities and DNF Expressions." Journal of Machine Learning Research, 2007.Markdown
[Feldman. "Attribute-Efficient and Non-Adaptive Learning of Parities and DNF Expressions." Journal of Machine Learning Research, 2007.](https://mlanthology.org/jmlr/2007/feldman2007jmlr-attributeefficient/)BibTeX
@article{feldman2007jmlr-attributeefficient,
title = {{Attribute-Efficient and Non-Adaptive Learning of Parities and DNF Expressions}},
author = {Feldman, Vitaly},
journal = {Journal of Machine Learning Research},
year = {2007},
pages = {1431-1460},
volume = {8},
url = {https://mlanthology.org/jmlr/2007/feldman2007jmlr-attributeefficient/}
}