Theory of Computation (TOC) Seminar Series 2016


Laszllo Babai, Dept. of Computer Science and Mathematics, University of Chicago
Laszlo Babai: Graph Isomorphism in Quasipolynomial Time
Speaker(s): Laszllo Babai
Date: Tuesday, February 02, 2016
Time: 4:00 PM to 5:00 PM
Location: Stata Center, 32-141 - Refreshments in Stata Center, Gates Tower, 5th floor lounge
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Avi Wigderson, IAS,
Avi Wigderson: Elementary Mathematical Problems Disguising Computational Hardness
Speaker(s): Avi Wigderson, IAS
Date: Thursday, February 11, 2016
Time: 4:00 PM to 5:00 PM
Location: D463, Star Conf. Room
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Sasha Rakhlin, University of Pennsylvania
Sasha Rahklin:How to Predict When Estimation is Hard: Algorithms for Learning on Graphs
Speaker(s): Sasha Rakhlin
Date: Tuesday, February 16, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva Gates Bldg. G449 Refreshments in the Gates Bldg. 5th floor lounge
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Greg Valiant,
Greg Valiant: When your big data seems too small: accurate inferences beyond the empirical distribution
Speaker(s): Greg Valiant
Date: Tuesday, February 23, 2016
Time: 4:00 PM to 5:00 PM
Location: 32 - 155 Stata Bldg.
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Raghu Meka, UCLA,
Raghu Meka: Pseudorandomness- old problems, new methods, and current challanges
Speaker(s): Raghu Meka, UCLA
Date: Thursday, March 03, 2016
Time: 2:45 PM to 3:45 PM
Location: D-463 (Star)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Omer Reingold, Principal Research Engineer, Samsung Research America,
Omer Reingold: Constant-round Interactive-proofs for Delegating Computation
Speaker(s): Omer Reingold, Principal Research Engineer, Samsung Research America
Date: Tuesday, March 08, 2016
Time: 4:00 PM to 5:00 PM
Location: G449, Pail/Kiva, Gates Bldg.
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Ran Raz, Professor, Mathematics and Computer Science, Weizmann Institute,
Ran Raz: Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning
Speaker(s): Ran Raz, Professor, Mathematics and Computer Science, Weizmann Institute
Date: Tuesday, March 15, 2016
Time: 4:00 PM to 5:00 PM
Location: G449, Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Dimitris Achlioptas, Univ. of California, Santa Cruz
Dimitris Achlioptas: Random Walks that Find Perfect Objects and the Lovasz Local Lemma
Speaker(s): Dimitris Achlioptas
Date: Tuesday, March 29, 2016
Time: 4:00 PM to 5:00 PM
Location: Stata Bldg 32 - 155 Cookies at 3:45 G(Gates)5 Lounge
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

David Zuckerman, Comp. Science Dept., Univ. of Texas at Austin,
David Zuckerman: Explicit Two-Source Extractors and Resilient Functions
Speaker(s): David Zuckerman, Comp. Science Dept., Univ. of Texas at Austin
Date: Tuesday, April 12, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Rocco Servedio, Columbia University
Rocco Servedio: Two Circuit Lower Bounds
Speaker(s): Rocco Servedio
Date: Tuesday, April 26, 2016
Time: 4:00 PM to 5:00 PM
Location: G449 - Patil
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Ken Clarkson, IBM Research, Almaden,
Ken Clarkson: More Near-Linear Linear Algebra, via Sketching
Speaker(s): Ken Clarkson, IBM Research, Almaden
Date: Tuesday, May 03, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Madhu Sudan, Harvard University,
Madhu Sudan: Communication Amid Uncertainty
Speaker(s): Madhu Sudan, Harvard University
Date: Tuesday, May 10, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 6, dlehto@csail.mit.edu

Boaz Barak, Harvard Paulson School,
Boaz Barak: Computational Bayesianism, Sums of Squares, and Unicorns
Speaker(s): Boaz Barak, Harvard Paulson School
Date: Tuesday, September 13, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Alina Ene, Boston University,
Alina Ene: From Minimum Cut to Submodular Minimization: Leveraging the Decomposable Structure
Speaker(s): Alina Ene, Boston University
Date: Monday, September 19, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva, Gates Tower - G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Mohsen Ghaffari, MIT,
Mohsen Ghaffari: Improved Local Distributed Graph Algorithms
Speaker(s): Mohsen Ghaffari, MIT
Date: Tuesday, September 27, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Alexandr Andoni, Columbia University,
Alexandr Andoni: Optimal Hashing for High-Dimensional Spaces
Speaker(s): Alexandr Andoni, Columbia University
Date: Monday, October 03, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449, Gates Tower
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Jonathan Ullman,
Jonathan Ullman: Algorithmic Stability for Adaptive Data Analysis
Speaker(s): Jonathan Ullman
Date: Tuesday, October 18, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Sebastien Bubeck,
Sebastien Bubeck: New Results at the Crossroads of Convexity, Learning and Information Theory
Speaker(s): Sebastien Bubeck
Date: Tuesday, October 25, 2016
Time: 4:00 PM to 5:00 PM
Location: G449 Patil/Kiva
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Ronitt Rubenfeld, MIT,
Ronitt Rubinfeld: Local Computation Algorithms
Speaker(s): Ronitt Rubenfeld, MIT
Date: Tuesday, November 01, 2016
Time: 4:00 PM to 5:00 PM
Location: G449 Patil/Kiva
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Yuval Ishai, Technion and UCL,
Yuval Ishai: Succinct Secure Computation from DDH
Speaker(s): Yuval Ishai, Technion and UCL
Date: Tuesday, November 08, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Jelani Nelson, Harvard,
Jelani Nelson: Heavy Hitters via Cluster-Preserving Clustering
Speaker(s): Jelani Nelson, Harvard
Date: Tuesday, November 15, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Nisheeth Vishnoi, EPFL
Slime Molds and Sparse Recovery
Speaker(s): Nisheeth Vishnoi
Date: Tuesday, November 22, 2016
Time: 4:00 PM to 5:00 PM
Location: G449
Contact: Aleksander Madry, madry@csail.mit.edu

Tim Roughgarden,
How Computer Science Informs Modern Auction Design
Speaker(s): Tim Roughgarden
Date: Tuesday, November 29, 2016
Time: 4:00 PM to 5:00 PM
Location: G449
Contact: Aleksander Madry, madry@csail.mit.edu

Tim Roughgarden, Stanford University,
Tim Roughgarden: How Computer Science Informs Modern Auction Design
Speaker(s): Tim Roughgarden, Stanford University
Date: Tuesday, November 29, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Tim Roughgarden, Stanford University,
Tim Roughgarden: How Computer Science Informs Modern Auction Design
Speaker(s): Tim Roughgarden, Stanford University
Date: Tuesday, November 29, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Gil Cohen,
Gil Cohen: Recent Advances in Randomness Extractors and Their Applications
Speaker(s): Gil Cohen
Date: Tuesday, December 06, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu

Ola Svensson, EPFL,
Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth
Speaker(s): Ola Svensson, EPFL
Date: Tuesday, December 13, 2016
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Goodwin, 617.324.7303, dlehto@csail.mit.edu