Algorithms and Complexity Seminar:
Spring 2006
Organizers:
Ronitt Rubinfeld and Madhu Sudan.
The Algorithms and Complexity seminar
will
meet Thursdays 4pm-5:15pm in G575
(Theory Lab). The style and format of
these meetings
are quite variable. Please feel free to contact the host to find out
more details.
- February 16,
2006: Speaker: Amir Shpilka
(Technion). Topic: New Constructions of epsilon-biased
generators. Host: Madhu Sudan
- February 23, 2006:
Speaker: Nick Harvey (MIT).
Topic: Randomized
Algebraic Algorithms for Matroid and Matching Problems.
Host: Madhu Sudan
- March 2, 2006: Open
- March 9, 2006: Special Applied
Math Seminar in 2-146 Speaker: Thomas
Hayes (Berkeley). The Adaptive k-armed Bandit.
(Note unusual location!)
- March 16, 2006: Speaker: Sofya Raskhodnikova
(Weizmann Institute). Topic: Sublinear Algorithms for String
Compressibility and the
Distribution Support Size. Host: Ronitt
Rubinfeld.
- April 6, 2006 at 5:15pm: (Time changed due to Dertouzos Lecture)
Speaker: Nicole Immorlica
(Microsoft
Research). Topic: Monopoly Pricing, Profit Extraction, and
Popping Balloons. Host: Piotr Indyk.
- April 13, 2006:
Speaker: Seth Pettie (MPI).
Topic: Low Distortion Graph Spanners.
Host: Mihai Patrascu.
- April 20, 2006: Speaker: Mihai Patrascu (MIT). Topic: Data
Structures and Cell-Probe Complexity. Host: Madhu Sudan.
- April 27, 2006: No talk due to Dertouzos Lecture
- May 4, 2006: Speaker: Jonathan Kelner (MIT). Topic: A
Randomized Polynomial Time Simplex Algorithm for Linear Programming.
Host: Madhu Sudan.
- May 11, 2006: Speaker: Dieter van Melkebeek (U. Wisconsin).
Topic: Time Hierarchies for Semantic Models of
Computation. Host: Madhu Sudan.
- May 18, 2006: Speaker: Milena Mihail (G. Tech.). Topic: Algorithmic
performance in Complex Networks.
Host: Madhu Sudan.