# Yao's minimax lemma for Monte Carlo algorithms

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?

• What does "distinguishing between them with bounded error" mean? Apr 11, 2019 at 11:28
• @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. Apr 11, 2019 at 12:16
• Can you write a formal definition of when an algorithm can distinguish between two hard distributions? Apr 11, 2019 at 12:17