Theory
Discussion Group
Spring 2010
*All meetings are held in 5126 Upson Hall from 1:15-2:30 on Tuesdays unless otherwise noted *
Funding for the TDG is generously provided by Eva Tardos
|
Date &
Time
|
Speaker
|
Title
|
|
2/16/2010 |
Gabriel Bender
|
On the Shannon capacity of a graph
L Lovasz IEEE Transactions on Information Theory, 1979 |
|
2/23/2010 |
Hu Fu
|
Regularity Lemmas and Combinatorial Algorithms
Nikhil Bansal and Ryan Williams FOCS 2009 |
|
3/2/2010 |
Alexander Fix
|
A Quantum Lovasz Local Lemma Andris Ambainis, Julia Kempe, Or Sattath STOC 2010 |
|
3/9/2010 |
Stanley Shen
|
The (1 + β)-Choice Process and Weighted Balls-into-Bins
Yuval Peres, Kunal Talwar, and Udi Wieder SODA 2010 |
|
3/16/2010 |
Vasilis Syrgkanis
|
A New Approximation Technique for Resource-Allocation Problems
Barna Saha and Aravind Srinivasan Innovations in Computer Science, 2010 |
|
3/23/2010 |
**NO TDG**
SPRING BREAK |
**NO TDG** SPRING BREAK |
|
3/30/2010 |
Katherine Lai
|
Connections Between Unique Games and Multicut
David Steurer and Nisheeth K. Vishnoi ECCC 2009 |
|
4/6/2010 |
Evan Danaher
|
A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model
Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani SODA 2010 |
|
4/13/2010 |
Anna Blasiak
|
Highway Dimension, Shortest Paths, and Provably Efficient Algorithms
Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck SODA 2010 |
|
4/20/2010 |
Hongyu Liang
|
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
Venkatesan Guruswami and Rishi Saket ICALP 2010 |
|
4/27/2010 |
TBD
|
TBD |
|
5/4/2010 |
TBD
|
TBD |
To receive email announcements about the Theory Discussion Group, subscribe to our mail list at
https://lists.cs.cornell.edu/mailman/listinfo/tdg-l