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?


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.

| improve this answer | |
  • $\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 Mar 31 '16 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 Mar 31 '16 at 23:00
  • $\begingroup$ Alright, it make sense to me now if we are considering non-uniform Turing machine. Thanks! $\endgroup$ – Paul Mar 31 '16 at 23:08

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.