Yao's test
Introduction In cryptography and the theory of computation, '''Yao's test''' is a test defined by Andrew Chi-Chih Yao in 1982, against pseudo-random sequences. A sequence of words passes Yao's test if an attacker with reasonable computational power cannot distinguish it from a sequence generated uniformly at random.
Formal statement === Boolean circuits ===Let  be a polynomial, and  be a collection of sets  of -bit long sequences, and for each , let  be a probability distribution on , and  be a polynomial. A predicting collection  is a collection of boolean circuits of size less than . Let  be the probability that on input , a string randomly selected in  with probability , , i.e.Moreover, let  be the probability that  on input  a -bit long sequence selected uniformly at random in . We say that  passes Yao's test if for all predicting collection , for all but finitely many , for all polynomial  :=== Probabilistic formulation ===As in the case of the next-bit test, the predicting collection used in the above definition can be replaced by a probabilistic Turing machine, working in polynomial time. This also yields a strictly stronger definition of Yao's test (see Adleman's theorem). Indeed, One could decide undecidable properties of the pseudo-random sequence with the non-uniform circuits described above, whereas BPP machines can always be simulated by exponential-time deterministic Turing machines.
References