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)

TIME SPEAKER TITLE SLIDES

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)

TIME	SPEAKER	TITLE	SLIDES
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