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

## Friday, January 23, 2009

Subscribe to:
Post Comments (Atom)

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

ReplyDeletehttp://lucatrevisan.wordpress.com/2009/01/23/bounded-independence-ac0-and-random-3sat/

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