Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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).


Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: