2 ms·
Nisan and Wigderson prove many different corollaries of their construction in their seminal 'Hardness vs Randomness' paper but their requirement for general der
by polymipisexp 2y ago
Nisan and Wigderson prove many different corollaries of their construction in their seminal 'Hardness vs Randomness' paper but their requirement for general derandomization (P = BPP) is that there's some function f computable in time 2^O(n)
such that for some e > 0 for all circuits of size 2^en the correlation between f and the output of the circuit is sufficiently low (if I understand correctly).