2
$\begingroup$

In the query complexity model, we define $R(f)$ as the bounded-error query complexity of $f$. It is said that

Claim. we can find two hard distributions over the 0- and 1-inputs of $f$ respectively, such that distinguishing between them with bounded error takes at least $\Omega(R(f))$ time for any randomized algorithm.

I have tried to use Yao's minimax lemma to show this but I failed. More concretely, the obstacle I met is that an algorithm that distinguishes distributions as described need NOT to be a bounded error algorithm for $f$.

Question. How to prove this claim?

Improve this question
$\endgroup$
3
  • $\begingroup$ What does "distinguishing between them with bounded error" mean? $\endgroup$ – Yuval Filmus Apr 11 '19 at 11:28
  • $\begingroup$ @YuvalFilmus That is, we (or, the algorithm) are guaranteed that the input is sampled from a distribution $\mathcal{D}$. We require that the distinguishing algorithm returns the correct answer $f(x)$ with probability larger than, say, $2/3$. Note that since $x$ is sampled from a distribution, it is possible that there exists a $x_0$ on which the algorithm always fails. $\endgroup$ – Lwins Apr 11 '19 at 12:16
  • $\begingroup$ Can you write a formal definition of when an algorithm can distinguish between two hard distributions? $\endgroup$ – Yuval Filmus Apr 11 '19 at 12:17

Your Answer

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

Browse other questions tagged or ask your own question.