0
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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, 2014 at 23:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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