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. :)
Subscribe to:
Post Comments (Atom)
Posts
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.