# 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? – Robin Kothari May 20 '13 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. – Mahdi Cheraghchi May 20 '13 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. – Lev Reyzin May 20 '13 at 19:40
• @RobinKothari, that's exactly right. – Keki Burjorjee May 20 '13 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. – Mahdi Cheraghchi May 20 '13 at 21:41