Computational Complexity

Wednesday, August 27, 2008

 
While I Was Gone

Posted by Lance

Just got back from vacation. Unlike Bill, I didn't see other math people and trade problems with them. Then again it wouldn't have been a vacation if I did.

As reported on a few other theory blogs, computational complexity hit a home run in NSF's new Expeditions Program. A dozen researchers in the New Jersey/New York area won an award for Understanding, Coping with and Benefiting from Intractability. In fact all four of the Expeditions grants has at least some theory connections. I'm not a fan of these big NSF programs but it's good to see the money going to our community.

The September issue of Scientific American focuses on privacy and Anna Lysyanskaya wrote an article on theory-based cryptography. Further Reading points to an old post Zero-Knowledge Sudoku. Thanks for the plug.

Finally Peter Lee writes about the growing theory group at CMU.

9:44 AM # 2 comments

1.  Anonymous says:  
   
   The last paragraph of Peter Lee's blog post sounds especially promising for current PhD students: "Overall, it seems pretty clear that, over the next decade, the best CS departments will be required to have the best theory research. We’ll be working hard to recruit the people we need to do just that."
   

   1:16 PM, August 27, 2008

2.  Anonymous says:  
   
   Is Venkat Guruswami moving to CMU?
   

   3:03 PM, August 27, 2008

Comment Feeds: This Post All