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.
$\begingroup$
$\endgroup$
7
-
2$\begingroup$ 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? $\endgroup$– Robin KothariCommented May 20, 2013 at 17:16
-
2$\begingroup$ 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. $\endgroup$– Mahdi CheraghchiCommented May 20, 2013 at 17:58
-
2$\begingroup$ @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. $\endgroup$– Lev Reyzin ♦Commented May 20, 2013 at 19:40
-
$\begingroup$ @RobinKothari, that's exactly right. $\endgroup$– Keki BurjorjeeCommented May 20, 2013 at 20:39
-
$\begingroup$ 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. $\endgroup$– Mahdi CheraghchiCommented May 20, 2013 at 21:41
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
0
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).
