A r-independent distribution over binary strings of length n means that for every set of r bits are uniformly distributed over the 2r possible values for those bits. We can create r-independent distributions using O(r log n) truly random bits.
Braverman shows that no depth-d size-m circuit of AND, OR and NOT gates can distinguish between a truly uniform distribution and any r-independent distribution with r = (log m)O(d2).
In a celebrated 2007 FOCS paper, Bazzi proved the result for the special case for DNF formulas (depth-2 circuits). Razborov recently had a simpler proof of Bazzi's theorem.
Nisan already created specific pseudorandom generators for constant-depth circuits but Braverman's result allows us to use any poly-logarithmically independent set including some that come out of coding theory. While the result doesn't have immediately obvious applications, I expect this result to be a fundamental tool for complexity for years to come.
Scott has a longer take and somehow manages to connect it with quantum computing.
Actually the result requires r = (log m) to the O(d^2) independence for depth d.
ReplyDeleteThanks. Fixed.
ReplyDeleteShould this result now be known as "Braverman's Theorem"?
ReplyDeleteDear Lance, here is a problem (perhaps silly) that comes to mind: Is the conclusion of the Linial-Nisan conjecture (=Braverman’s result) holds for monotone threshold circuits, namely for bounded depth circuits with (monotone) threshold gates?
ReplyDeleteWhat are consequences and applications of this result?
ReplyDelete