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, 2019 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, 2019 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, 2019 at 12:17

0

Reset to default

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.