Here is a problem with a similar flavor to learning juntas:

Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$.

Goal: Find a subcube $S$ of $\{0,1\}^n$ with volume $|S|=2^{n-k}$ such that $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.1$. We assume such a subcube exists.

It is easy to get an algorithm that runs in time $n^{O(k)}$ and returns a correct answer with probability $\ge 0.99$ by trying all $(2n)^k$ ways to choose a subcube and sampling the average in each one.

I'm interesting in finding an algorithm that runs in time $poly(n,2^k)$. Alternatively, a lower bound would be great. The problem has similar flavor to learning juntas, but I don't see an actual connection between their computational difficulty.

Update: @Thomas below proves that the sample complexity of this problem is $poly(2^k,\log n)$. The interesting issue is, still, the computational complexity of the problem.

Edit: you can assume for simplicity that there exists a subcube with $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.2$ (notice the gap: we're looking for a subcube with average $\ge 0.1$.) I'm pretty sure any solution to the problem with the gap will also solve the problem without the gap.


1 Answer 1


Here is a better bound on the sample complexity. (Although the computational complexity is still $n^k$.)

Theorem. Assume there exists a subcube $S$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$. With $O(2^k \cdot k \cdot \log n)$ samples we can, with high probability, identify a subcube $S'$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S'}[f(x)]| \geq 0.1$.

Note the small loss in parameters ($0.12$ is optimal versus guarantee of $0.1$).

Proof. Pick $m$ points $P \subset \{0,1\}^n$ uniformly at random and query $f$ at each $x \in P$.

Fix a subcube $S$ of size $2^{n-k}$. We have $\mathbb{E}[|S \cap P|]=m 2^{-k}$. By a Chernoff bound, $$\mathbb{P}[|S \cap P| < m 2^{-k-1}] \leq 2^{-\Omega(m 2^{-k})}.$$ Also $$\mathbb{P}[| \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | > \varepsilon] \leq 2^{-\Omega(|S \cap P| \varepsilon^2)}.$$

By a union bound over all ${n \choose k}2^k$ choices of $S$, we have $$\mathbb{P}[\forall S ~~ | \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | \leq \varepsilon] \geq 1 - {n \choose k} 2^k 2^{-\Omega(m 2^{-k} \varepsilon^2)}.$$ So by picking $m = O(2^k/\varepsilon^2 \cdot k \log n)$, we can ensure that, with probability at least $0.99$, we can estimate $\mathbb{E}_{x \in S}[f(x)]$ to within $\varepsilon$ for all subcubes $S$ of size $2^{n-k}$.

Setting $\varepsilon=0.01$, we prove the theorem: picking the subcube with the largest $| \mathbb{E}_{x \in S \cap P}[f(x)]|$ will, with high probability, satisfy the requirements. Q.E.D.

  • 1
    $\begingroup$ Oh, whow, how silly of me: yes, the basic idea is that if you sample $C \cdot 2^k$ points, then an expected $C$ of them will be in each subcube, so with a modest value of $C$ that gives a large enough sample size to solve the problem, even after union-bounding over all $n^k$ Chernoff bounds. Also, I'm pretty sure that any solution can be adapted to eliminate the gap between 0.1 and 0.12, so I'll just add this as a comment to the question. Thanks!! $\endgroup$
    – greg
    Apr 29, 2014 at 17:53
  • 3
    $\begingroup$ Another way of seeing this is that the range space you describe has bounded shatter dimension and therefore bounded VC dimension, and then you throw the eps-approximation theorem at it. $\endgroup$ Apr 29, 2014 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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