Algorithms and Complexity Seminar: Fall 2008
Organizer: Aleksander Mądry (madry (at) mit.edu)
The Algorithms and Complexity seminar for Fall 2008 will
meet either Mondays, Wednesdays or Thursdays 4pm--5:15pm in
32-G575 (Theory Lab at 5th floor of Stata Center).
The style and format of these meetings are quite variable. Please feel free to
contact the host to find out more details. There is a mailing list where the announcements of upcoming talks are being sent. To subscribe to this list send an empty email to: compalgsem-subscribe **at** lists.csail.mit.edu
(Partial) Schedule:
-
Wednesday, September 10, 2008:
Speaker:
Ola Svensson
(IDSIA).
Topic:
(Acyclic) Job Shops are Hard to Approximate
.
Host: Andreas S. Schulz
-
Monday, September 15, 2008:
Speaker:
Ankur Moitra
(MIT).
Topic:
A Solution to the Papadimitriou-Ratajczak conjecture
.
Host: Tom F. Leighton
-
Thursday, September 18, 2008:
Speaker:
Swastik Kopparty
(MIT).
Topic:
The homomorphism domination exponent.
Host: Madhu Sudan
-
Wednesday, September 24, 2008:
Speaker:
Krzysztof Onak
(MIT).
Topic:
Constant-Time Approximation Algorithms via Local Improvements.
Host: Ronitt Rubinfeld
-
Monday, September 29, 2008:
Speaker:
Jelani Nelson
(MIT).
Topic:
Sketching and Streaming Entropy via Approximation Theory.
Host: Erik Demaine
-
Monday, October 6, 2008:
No A&C seminar - Shachar Lovett's talk at MSR
-
Wednesday, October 8, 2008:
Speaker:
Yuzhen Xie
(Waterloo University).
Topic: On the Parallelization of Polynomial System Solvers.
Host: Charles E. Leiserson
-
Thursday, October 9, 2008:
Speaker:
Swastik Kopparty
(MIT).
Topic:
Random Graphs and First-order Logic with Parity Quantifiers.
-
Monday, October 13, 2008:
No A&C seminar - Columbus Day
-
Wednesday, October 15, 2008:
Speaker:
Elliot Anshelevich
(RPI).
Topic:
Terminal Backup, 3D Matching and Covering Cubic Graphs
.
Host: Evdokia Nikolova
-
Thursday, October 16, 2008:
No A&C seminar - Dertouzos Lecture of Cynthia Dwork
-
Monday, October 20, 2008:
No A&C seminar - Vijay Vazirani's talk at MSR
-
Wednesday, October 22, 2008:
Speaker:
Asaf Nussbaum
(Weizmann Institute).
Topic:
Pseudorandom and k-wise independent random graphs
-
Thursday, October 23, 2008:
No A&C seminar - Alexander Shvartsman's talk at CSAIL Colloquium
-
Monday, October 27, 2008:
No A&C seminar - FOCS
-
Thursday, October 30, 2008:
Speaker:
Jakob Nordström
(KTH, MIT).
Topic:
Understanding space in resolution: optimal lower bounds and exponential trade-offs
.
Host: Madhu Sudan
-
Monday, November 10, 2008:
No A&C seminar - Veteran's Day
-
Monday, November 17, 2008:
No A&C seminar - STOC deadline
-
Wednesday, November 19, 2008:
Speaker:
Avinatan Hassidim
(Hebrew University, MIT).
Topic:
Quantum Multi Proof System with Communicating Provers.
-
Monday, December 1, 2008:
Speaker:
Vineet Goyal
(CMU, MIT).
Topic:
Approximation Algorithms for Demand-Robust Covering Problems
.
Host: Andreas S. Schulz
-
Monday, December 8, 2008:
Speaker:
Adi Akavia
(IAS).
Topic:
Finding Significant Fourier Transform Coefficients Deterministically and Locally
.
Host: Piotr Indyk
-
Wednesday, December 10, 2008:
Speaker:
Avinatan Hassidim
(Hebrew University, MIT).
Topic: Derandomizing Algorithms on Product Distributions
-
Friday, December 12, 2008:
Speaker:
Victor Chen
(MIT).
Topic:
The role of pseudorandomness in the testing of boolean functions
-
Thursday, January 8, 2009:
Speaker:
Łukasz Jeż
(University of Wrocław).
Topic:
Collecting Weighted Items from a Dynamic Queue
-
Thursday, January 22, 2009:
Speaker:
Mahdi Cheraghchi
(EPFL).
Topic:
Noise-Resilient Group Testing: Limitations and Constructions. Host: Madhu Sudan
Archives from previous semesters:
People who attended talks like these also attended: