4
$\begingroup$

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.

$\endgroup$
  • 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 Kothari May 20 '13 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$ – MCH May 20 '13 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 May 20 '13 at 19:40
  • $\begingroup$ @RobinKothari, that's exactly right. $\endgroup$ – Keki Burjorjee May 20 '13 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$ – MCH May 20 '13 at 21:41
7
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.