Organizer: Neil Immerman

The theory seminar is a weekly meeting in which topics of interest in the theory of computation -- broadly construed -- are presented. This is sometimes new research by visitors or by local people. It is sometimes work in progress, and it is sometimes recent or classic material of others that some of us present in order to learn and share.

This is a one-credit seminar which may be taken repeatedly for credit.

Schedule, Spring 2008:

Tues, Jan. 29	Brief Organizational Meeting
Tues, Feb. 5	Norman Danner, Wesleyan University: Two Algorithms in Search of a Type System
Tues, Feb. 19, dept seminar	Susan Dumais: "Information Retrieval in Context", 4:00 Room 151
Thurs, Feb. 21, dept seminar	Jan Vondrak, Princeton University, "Approximation Algorithms for Combinatorial Allocation Problems", 4:00 Room 151
Tues, Feb. 26	Elisha Rosensweig: Arora's PTAS for TSP
Thurs, Feb. 28, dept seminar	Nina Balcan, CMU, A Theory of Similarity Functions for Learning and Clustering, 4:00 Room 151
Mon, March 3, dept seminar	Daniel Golovin, CMU, Uniquely Represented Data Structures with Applications to Privacy, 4:00 Room 151
Tues, March 11, dept seminar	Andrew McGregor, UCSD, Computing on Streams: New Results and Directions 4:00 Room 151
Tues, April 1, dept. seminar	Mohit Singh, CMU, Iterative Methods in Combinatorial Optimization 4:00 Room 151
Mon, April 7, dept. seminar	Vahab Mirrokni: Online Advertisement and Submodular Maximization, 4:00 Room 151
Tues, April 8	Naomi Fox: Bar-and-Joint Rigidity of Proteins
Thurs, April 24	Michael Sindelar: Two Techniques for Linear Programming Relaxations of Some Combinatorial Optimization Problems; note due to a conflict this talk will be on Thursday, 4:00, usual room: Computer Science 140.
Tues, April 29	Philipp Weis: Finite-Variable Logics
Tues, May 6	Brandon McPhail: Stochastic Scheduling Problems and the Benefit of Adaptivity