Theory Lunch is an informal seminar run by the Algorithms and Complexity Theory Group. The seminar meets on Wednesdays, noon till 1pm, in GHC 8102 (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, exciting open problems, etc.

Spring 2012 Schedule
Jan 18, 2012
The Entropy Soon-to-be-Method
Or Sheffet
Jan 25, 2012
Green Computing Algorithmics: Managing Power Heterogeneity
Kirk Pruhs
Feb 1, 2012
Testing Low Complexity Affine-Invariant Properties
Arnab Bhattacharyya
Feb 8, 2012
Differential Privacy in a Space of Functions
Rob Hall
Feb 15, 2012
Greedy Sequential Maximal Independent Set and Matching are Parallel on Average
Julian Shun
Feb 22, 2012
The Snowball Effect of Uncertainty
Steven Ehrlich
Feb 29, 2012
A General Framework for Graph Sparsification
Debmalya Panigrahi
Mar 7, 2012
CSD Open House
Mar 14, 2012
Spring Break
Mar 21, 2012
Usable and Secure Password Management
Jeremiah Blocki
Mar 28, 2012
The World is Flat: Algorithms for Classical Optimization Problems Restricted to Planar Graphs
Philip Klein
Apr 4, 2012
Randomized Algorithms in Linear Algebra and the Column Subset Selection Problem
Petros Drineas
Apr 11, 2012
Learnability of DNF with Representation-Specific Queries
Liu Yang
Apr 18, 2012
Faster Flow Algorithms using Variations of Electrical Flows
Richard Peng
Apr 25, 2012
Online Algorithms and the K-server Conjecture
Aleksander Mądry
May 2, 2012
A new point of NP-hardness for Unique Games
John Wright
May 9, 2012
Min-Max Graph Partitioning
Viswanath Nagarajan
Previous Seminar Series
Maintained by Richard Peng and John Wright.