# Yao's theorem for the uniform case

Yao's theorem says that for a distribution, next bit unpredictability is equivalent to pseudo-randomness. This link proves Yao's theorem, but the proof relies on non-uniform probabilistic polynomial time algorithms. Is there a proof of Yao's theorem that instead only uses uniform probabilistic polynomial time algorithms?

• – D.W. Jan 29 at 23:06

At the end of Section 2 of the lecture notes that you cite, it explicitly states "We note that an analogue of this result holds for uniform distinguishers and predictors, provided that we change the definition of next-bit predictor to involve a random choice of $$i \leftarrow R [n]$$ instead of a fixed value of $$i$$, and change the time bounds in the conclusions to be $$t − O(n)$$ rather than $$t − O(1)$$ and $$t$$ (we can’t do tricks like in the final paragraph of the proof). In contrast to the multiple-sample indistinguishability result from last time, this result does not need $$X$$ to be efficiently samplable for the uniform version."