# Lower Bound for the Parity Learning Problem

What are known lower bounds for the time and query complexity of the problem of learning parities with an adaptive membership query oracle? To be clear the concept space $C$ is $\{x\in \{0,1\}^n \, \, | \, \,\sum_{i=1}^n x_i = k \}$, and the hypothesis space $\mathcal H$ is $\{0,1\}^n$. Given a bitstring of length $n$ as input, the adaptive membership query oracle returns 1 if the parity of the $k$ effective bits is odd and 0 otherwise.

• I'm not sure I understand. The oracle knows a string $x$ of Hamming weight $k$, and when given as input another string $y$, it returns to the parity of $y$ restricted to the $k$ bits of $x$ that are 1? Or in other words, it returns the inner product of x and y mod 2? Commented May 20, 2013 at 17:16
• Even non-adaptively, if there are no errors you can learn parities exactly by querying the $n$ basis vectors, of even $O(n)$ random vectors. And that's the best you can do. Commented May 20, 2013 at 17:58
• @MCH that's not necessarily the case. The lower bound on the number of queries is $\Omega(k \log n)$, and it's not known if it can be achieved by an efficient algorithm. This is called attribute efficient learning. Commented May 20, 2013 at 19:40
• @RobinKothari, that's exactly right. Commented May 20, 2013 at 20:39
• Oh, in that case you can just multiply the unknown string with the parity check matrix of a binary code with minimum distance more than $k$, and that would achieve $O(k log n)$ non-adaptive queries. Such matrices can be constructed via BCH codes. Commented May 20, 2013 at 21:41