Hacker News Reader

Comment by hinkley | Hacker News Reader

> Computer scientists have discovered a remarkable connection between randomness and computational difficulty (i.e., identifying natural problems that have no efficient algorithms). Working with colleagues, Wigderson authored a highly influential series of works on trading hardness for randomness. They proved that, under standard and widely believed computational assumptions, every probabilistic polynomial time algorithm can be efficiently derandomized (namely, made fully deterministic). In other words, randomness is not necessary for efficient computation. This sequence of works revolutionized our understanding of the role of randomness in computation, and the way we think about randomness.

How would I go about catching up with this aspect of his research? It’s not often that I’ve never heard of a Turing winner, but this guy is completely off of my radar.

View on HN

You can try his book. https://www.math.ias.edu/avi/book

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?

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

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.

Reply on news.ycombinator.com