I'm reading the proof of Yao's theorem on Boaz Barak's lecture, the main part of the proof is the following claim:

enter image description here

My question is:

How can we say "without loss of generality" here? Since $H^i$ and $H^{i-1}$ are probability ensembles, hence for a fixed $D$, whether $\mathrm{Pr}[D(H^i_n)=1]\ge \mathrm{Pr}[D(H^{i-1}_n)=1]$ or not may not necessary the same for all $n$, where $H^i_n$ is the $n$th distribution in that ensemble. So, when one wants to design the algorithm $P$, one need to encode these relation information, how can we do this?


1 Answer 1


He's doing a pretty poor job of expressing a very simple idea here, which is that if there exists a distinguisher $D$ for which $Pr\lbrack D(H^{i-1})=1\rbrack$ > $Pr\lbrack D(H^{i})=1\rbrack$ (which means the advantage is negative before taking the absolute value), there also exists a distinguisher $\overline{D}$ for which $Pr\lbrack D(H^{i})=1\rbrack$ > $Pr\lbrack D(H^{i-1})=1\rbrack$ (i.e. the advantage is positive before taking the absolute value) by just defining $\overline{D}(H^*) = 1-D(H^*)$ for $H^* \in \{H^i,H^{i-1}\}$. Informally, this distinguisher runs $D$ on its input and just flips whatever $D$ outputs.

Thus, w.l.o.g. we can assume the distinguisher has a higher probability of outputting a 1 given a sample from $H^i$ than from $H^{i-1}$, which means we don't need the absolute value.

  • $\begingroup$ Hi pg, I can understand this part, but my question is: how do we know the relation $\mathrm{Pr}[D(H^i_n)=1]>\mathrm{Pr}[D(H^{i-1}_n)=1]$ is "uniform" for all $n$, since when we say $|\mathrm{Pr}[D(H^i)=1]-\mathrm{Pr}[D(H^{i-1})=1]|\ge \epsilon$ we mean $|\mathrm{Pr}[D(H^i_n)=1]-\mathrm{Pr}[D(H^{i-1}_n)=1]|\ge \epsilon(n)$ for all $n$. $\endgroup$
    – Paul
    Commented Mar 31, 2016 at 22:54
  • 1
    $\begingroup$ Why does it matter? We fix a specific $n$ in the problem statement, and it holds for all $n$, and in fact the distinguishers are usually considered to be non-uniform Turing machines anyway so we can change the description of the program to make absolute values unnecessary for any $n$. $\endgroup$
    – pg1989
    Commented Mar 31, 2016 at 23:00
  • $\begingroup$ Alright, it make sense to me now if we are considering non-uniform Turing machine. Thanks! $\endgroup$
    – Paul
    Commented Mar 31, 2016 at 23:08

Your Answer

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

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