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 :