Hacker News Reader

Comment by layer8 | Hacker News Reader

I wonder what the “standard and widely believed computational assumptions” are. Presumably, probabilistic approximations to NP-complete problems are not polynomial-time? Or the derandomized versions would still be just approximations?

View on HN

They are generally esoteric conjectures similar in spirit to P != NP. For example, the third paper uses the assumption "E requires exponential circuits". Here E is the class of problems solvable in exponential time, or 2^O(n) time, on a Turing Machine. Another model of computation besides Turing Machines are Boolean circuits, i.e. AND, OR, and NOT gates. The conjecture is that not every problem in E can be solved by "small" (subexponential-sized) circuits.

The basic idea of the work is that if these problems are hard, then we can use them to build pseudorandom generators that are "just as good" as true random, which we can use to turn truly random algorithms into pseudorandom algorithms with the same performance.

I think his argument assumes the existence of pseudorandom generators which map a small amount of "true" random bits to a large amount of bits that look random to any polytime observer. The "derandomization" is that we just have to check all possible states of the seed bits which hopefully will be logarithmic in the size of the problem so you can do exhaustive checking.

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

Reply on news.ycombinator.com