Carnegie Mellon University, School of Computer Science

Theory Lunch

Theory Lunch is an informal seminar run by Algorithms and Complexity Theory Group on Wednesdays, noon till 1pm, in NSH 1507 (unless otherwise specified). It is open to faculty, graduate and undergraduate students interested in theoretical aspects of Computer Science.

The meetings have various forms: talks on recently completed results, joint reading of an interesting paper, presentations of current work in progress and exciting open problems, etc.

Spring 2008 Schedule

(Wednesdays noon-1:00pm, NSH 1507)

January 23, Wednesday Nina Balcan A Theory of Similarity Functions for Learning and Clustering  
January 30, Wednesday Shuheng Zhou High Dimensional Sparse Regression and Clustering  
February 6, Wednesday Mohit Singh Iterative Methods in Combinatorial Optimization  
February 13, Wednesday Katrina Ligett A Learning Theory Approach to Non-Interactive Database Privacy  
February 20, Wednesday Yi Wu An Optimal SDP Approximation Algorithm for Max-Cut  
February 27, Wednesday Daniel Golovin Uniquely Represented Data Structures with Applications to Privacy  
March 5, Wednesday Deeparnab Chakrabarty Steiner Trees - Geometry, Linear Programs and Algorithms  
March 12, Wednesday Spring Break! No Theory Lunch!  
March 19, Wednesday Abe Othman Beyond the Revelation Principle: Manipulation-Optimal Mechanisms  
March 26, Wednesday Aaron Roth The Price of Malice in Linear Congestion Games  
April 2, Wednesday Christian Klein Unbiased Controlled Rounding  
April 9, Wednesday Eric Blais Testing Juntas  
April 16, Wednesday Mike Dinitz The Discounted Secretary Problem  
April 23, Wednesday Elaine Shi How to build private Google Docs  
April 30, Wednesday Varun Gupta Optimal size-based scheduling with selfish users  
May 7, Wednesday Karl Wimmer Polynomial regression under arbitrary product spaces  
May 14, Wednesday Yiannis Koutis Faster algebraic algorithms for path and packing problems  

Previous Seminar Series

maintained by Aaron Roth (alroth@cs)