As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution.

Suppose we have a boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ and we are given a distribution over the inputs. I would like to ask whether I can apply Yao's principle when there is already some distribution given over inputs? If yes, then how?

I was reading the paper by Scott Aaronson and could not understand why he simply stated that by Yao's principle we can assume that algorithm is deterministic while there was already a distribution given over the inputs.

  • 6
    $\begingroup$ If a randomized algorithm succeeds on a fixed input distribution with probability $p$, then there exists a deterministic algorithm that succeeds with probability $p$ as well. This is a trivial fact that is nothing more than averaging and I would not call it Yao's principle. $\endgroup$ – Sasho Nikolov Dec 10 '14 at 23:33

As you said, it is enough to point out a distribution (this could be any distribution) on which every deterministic algorithm fails. Now, if there is already a distribution given, and you can show that any deterministic algorithm fails on this one, then this provides also a lower bound for randomized algorithms. You can use any distribution in order to apply Yao's principle.

| cite | improve this answer | |

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.