We go all the way back to January for the paper of the year, Mark Braverman's Poly-logarithmic independence fools AC0 circuits
. Runners up include the Moser-Tardos Constructive Proof of the Lovász Local Lemma
(mostly for Robin Moser's great STOC talk
) and Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous for QIP=PSPACE
. Yet another great year for complexity.
US Science funding in general and CS funding at the NSF in particular got a strong boost from the stimulus package and continues to be well funded in the new budget. Microsoft Research New England gobbles up Madhu Sudan and Boaz Barak. A new innovations conference
starts next week and we explored barriers
in August. Lots of postdoc jobs out there for theorists. If you are looking for a faculty job, well you might want to consider another postdoc.
This year we started vidcasts
with special guests Molly Fortnow, Meena Mahajan, John Rogers, Rahul Santhanam, Chris Umans and Ryan Williams.
Thanks to our guest posters and contributors: Michele Budinich, Hans Courant, Dave Doty, Sorelle Friedler, Samir Khuller, Clyde Kruskal, Joe Kruskal, Bill Kahn, Michael Lucas, Lucy Moser, Ryan O'Donnell, Tal Rabin, Rahul Santhanam, Aaron Sterling and Vijay Vazirani.
Have a great New Years. Bill will be back next week and I'll be posting regularly again in March starting in Columbus
Posted By Lance to Computational Complexity
at 12/28/2009 06:15:00 AM