On learning k-parities with and without noise

Arnab Bhattacharyya, Ameet Gadekar, Ninad Rajgopal

We first consider the problem of learning $k$-parities in the on-line mistake-bound model: given a hidden vector $x\in \{0,1{\}}^n$ with $|x|=k$ and a sequence of "questions" $a_1,…