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

List-decoding and list recovery ask how much corruption or uncertainty a code can tolerate while still keeping the number of plausible codewords small. For large alphabet codes, the ultimate benchmark for list-decoding is the ($\epsilon$-relaxed) generalized Singleton bound, which targets list-of-$L$ decoding radius with rate $R$ up to radius $\frac{L}{L+1}(1-R-\epsilon)$. ... more >>>