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?
At the end of Section 2 of the lecture notes that you cite, it explicitly states &quot;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.&quot;