Friday, January 23, 2009

Polylog-wise independence fools constant-depth circuits

Well, the big buzz around the blogosphere, occasioned by an anonymous comment on Luca's blog Wednesday night is a new preprint by the mighty Mark Braverman, currently a postdoc at Microsoft Research, soon a faculty member at the University of Toronto.

Mark paper proves a conjecture of Linial and Nisan from 1990; namely, that no $n$-input circuit with constant depth and polynomial size can distinguish truly random inputs from inputs that are $k$-wise independent for $k = polylog(n)$.

The preprint is discussed in some detail on Scott's blog and also on Lance/Bill's blog.

There is a good chance we'll have the tools to cover this paper toward the end of the course. :)

1 comment:

  1. Update: Luca also discusses the result on his blog here,

    and makes some interesting connections to refuting random 3Sat and 3Xor formulas.


Note: Only a member of this blog may post a comment.