Theory of Computation Colloquium - 2013

For more information on this series, please see http://toc.csail.mit.edu/node/424.


Ankur Moitra, MIT
AN INFORMATION COMPLEXITY APPROACH TO EXTENDED FORMULATIONS*
Speaker(s): Ankur Moitra
Date: Tuesday, September 10, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G882 (Talk), RSA G5 Lounge (Refreshments)
Contact: Holly A Jones, hjones01@csail.mit.edu

SOFYA RASKHODNIKOVA ,
AUTOMATED PRIVATE QUERIES AND THE LIPSCHITZ PROPERTY OF FUNCTIONS*
Speaker(s): SOFYA RASKHODNIKOVA
Date: Tuesday, September 17, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Richard Peng, MIT
ITERATIVE ROW SAMPLING*
Speaker(s): Richard Peng
Date: Tuesday, September 24, 2013
Time: 4:15 PM to 5:15 PM
Location: G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Prof. Philip Klein, Brown University Department of Computer Science
The world is flat: algorithms for classical optimization problems restricted to planar graphs
Speaker(s): Prof. Philip Klein
Date: Tuesday, October 08, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Yael Tauman Kalai, Microsoft Research
1-ROUND DELEGATION FOR DETERMINISTIC COMPUTATIONS*
Speaker(s): Yael Tauman Kalai
Date: Tuesday, October 22, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Aleksander Madry, École Polytechnique Fédérale de Lausanne (EPFL)
NAVIGATING CENTRAL PATH WITH ELECTRICAL FLOWS: FROM FLOWS TO MATCHINGS, AND BACK
Speaker(s): Aleksander Madry
Date: Friday, November 01, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Gillat Kol ,
INTERACTIVE CHANNEL CAPACITY
Speaker(s): Gillat Kol
Date: Tuesday, November 05, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G882
Contact: Holly A Jones, hjones01@csail.mit.edu

Paul Valiant, Brown University
INSTANCE-BY-INSTANCE OPTIMAL IDENTITY TESTING
Speaker(s): Paul Valiant
Date: Tuesday, November 12, 2013
Time: 4:15 PM to 5:15 PM
Location: G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Yaron Singer, Harvard University
Methods for Adaptive Seeding and their Applications
Speaker(s): Yaron Singer
Date: Tuesday, November 19, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Mark Braverman, Princeton University
Information Complexity and Applications
Speaker(s): Mark Braverman
Date: Tuesday, November 26, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Mahdi Cheraghchi,
Capacity and Constructions of Non-Malleable Codes
Speaker(s): Mahdi Cheraghchi
Date: Tuesday, December 03, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Andrew Drucker, Institute for Advanced Study
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers
Speaker(s): Andrew Drucker
Date: Tuesday, December 10, 2013
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Adam Smith, Penn State
PRIVACY, STABILITY AND LEARNING
Speaker(s): Adam Smith
Date: Tuesday, February 11, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Venkatesan Guruswami, Carnegie Mellon University
Polar codes: Reliable communication with complexity scaling polynomially in the gap to Shannon capacity
Speaker(s): Venkatesan Guruswami
Date: Tuesday, February 18, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Jelani Nelson, Harvard University
Sparse dimensionality reduction: beyond worst-case analysis
Speaker(s): Jelani Nelson
Date: Tuesday, February 25, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu

Cynthia Rudin, MIT
INTERPLAY BETWEEN STATISTICAL LEARNING AND DECISION MAKING
Speaker(s): Cynthia Rudin
Date: Tuesday, March 04, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G882
Contact: Holly A Jones, hjones01@csail.mit.edu

Laszlo Babai, University of Chicago
GRAPH ISOMORPHISM
Speaker(s): Laszlo Babai
Date: Tuesday, March 11, 2014
Time: 4:15 PM to 5:15 PM
Location: 32-G449
Contact: Holly A Jones, hjones01@csail.mit.edu