<p>The question is about recovering with membership queries for which it is well known that O( k log n) queries suffice (via BCH codes see Hoffmeister's paper or my COLT 2005 paper). In terms of lower bounds \Omega(k log n) trivially follows from counting the number of parities and using the fact that they are all completely uncorrelated (basic packing-based lower bound).</p>

CC BY-SA 3.0
2013-05-20T20:19:05.360Z
2013-05-20T20:19:05.360Z
Vitaly
<p>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.   </p>

CC BY-SA 3.0
2013-05-20T17:16:10.807Z
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
CC BY-SA 3.0
2013-05-20T17:58:20.717Z
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
CC BY-SA 3.0
2013-05-20T19:40:10.630Z
@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
CC BY-SA 3.0
2013-05-20T20:39:42.023Z
@RobinKothari, that's exactly right.
Keki Burjorjee
CC BY-SA 3.0
2013-05-20T21:41:37.457Z
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
CC BY-SA 3.0
2013-05-20T23:01:10.167Z
Thanks @MCH. I was wondering (and this gets to the real question I need an answer to) if there is a proof that one cannot do better. Specifically, I was wondering if for small values of $k$ (say $k=5$, or $k=4$, or, to push it to the extreme, $k=1$), whether it is provably the case that parities cannot be learned in $o(\log n)$ queries (that's little-oh). If yes, can you, or someone else provide a sketch, or reference?
Keki Burjorjee
CC BY-SA 3.0
2013-05-21T01:17:17.697Z
I think an easy counting argument should work. There are $n$ choose $k$ possible parities, and the query results (say total of $m$ bits, even counting adaptivity) should distinguish between all of them. So $2^m$ must be at least $n$ choose $k$, which means $m=\Omega(k \log(n/k))$.
Mahdi Cheraghchi
<lg.learning><boolean-functions>
Lower Bound for the Parity Learning Problem
Keki Burjorjee
# Lower Bound for the Parity Learning Problem

(Asked by: username_0 on 2013-05-20)

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.

**Tags:** lg.learning, boolean-functions

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  
> **username_3**: @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*.  
> **username_0**: @RobinKothari, that's exactly right.  
> **username_2**: 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.  
> **username_0**: Thanks @MCH. I was wondering (and this gets to the real question I need an answer to) if there is a proof that one cannot do better. Specifically, I was wondering if for small values of $k$ (say $k=5$, or $k=4$, or, to push it to the extreme, $k=1$), whether it is provably the case that parities cannot be learned in $o(\log n)$ queries (that's little-oh). If yes, can you, or someone else provide a sketch, or reference?  
> **username_2**: I think an easy counting argument should work. There are $n$ choose $k$ possible parities, and the query results (say total of $m$ bits, even counting adaptivity) should distinguish between all of them. So $2^m$ must be at least $n$ choose $k$, which means $m=\Omega(k \log(n/k))$.  

---

## 1 answers

### Answer by username_4 on 2013-05-20. Score: 7 | Accepted answer

The question is about recovering with membership queries for which it is well known that O( k log n) queries suffice (via BCH codes see Hoffmeister's paper or my COLT 2005 paper). In terms of lower bounds \Omega(k log n) trivially follows from counting the number of parities and using the fact that they are all completely uncorrelated (basic packing-based lower bound).


---

