Theory of Computation (TOC) Seminar Series 2015


Robert Kleinberg, Associate Professor, Cornell University, Dept. of Computer Science
Robert Kleinberg: Secretary Problems with Non-Uniform Arrival Order
Speaker(s): Robert Kleinberg
Date: Tuesday, February 17, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Vinod Vaikuntanathan,
Vinod Vaikuntanathan: Program Obfuscation from Functional Encryption
Speaker(s): Vinod Vaikuntanathan
Date: Tuesday, February 24, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Shayan Gharan, Dept. CS & Engineering, University of Washington
Shayan Gharan: Effective-Resistance-Reducing Flows, Spectrally Thin Trees and Asymmetric TSP
Speaker(s): Shayan Gharan
Date: Tuesday, March 03, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Moses Chharikar, Prof., Dept. of CS, Princeton University
Moses Charikar: The Hidden Objective of Spectral Clustering?
Speaker(s): Moses Chharikar
Date: Tuesday, March 10, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Mikkel Thorup,
Mikkel Thorup: Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
Speaker(s): Mikkel Thorup
Date: Tuesday, March 17, 2015
Time: 4:15 PM to 5:15 PM
Location: D463 Star
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Antoine Joux,
Antoine Joux: A Simplified Setting for Discrete Logarithms in Small Characteristics Finite Fields
Speaker(s): Antoine Joux
Date: Tuesday, April 07, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Nir Bitanksy,
Nir Bitansky: On the Cryptographic Hardness of Finding a Nash Equilibrium
Speaker(s): Nir Bitanksy
Date: Tuesday, April 14, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Oded Regev, Courant Institute of Mathematical Sciences,
Oded Regev: Faster Algorithms for the Shortest Vector Problem
Speaker(s): Oded Regev, Courant Institute of Mathematical Sciences
Date: Thursday, April 23, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Constantinos Daskalakis,
Constantinos Daskalakis: Mechanism Design via Optimal Transport
Speaker(s): Constantinos Daskalakis
Date: Tuesday, April 28, 2015
Time: 4:15 PM to 5:15 PM
Location: G575
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Elad Hazan,
Elad Hazan: Is Optimization Computationally Equivalent to Online Learning?
Speaker(s): Elad Hazan
Date: Tuesday, May 12, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 (Patil/Kiva)
Contact: Deborah Lehto, dlehto@csail.mit.edu

Shaddin Dughmi,
Shaddin Dughmi: Algorithmic Bayesian Persuasion
Speaker(s): Shaddin Dughmi
Date: Wednesday, May 13, 2015
Time: 4:00 PM to 5:00 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

David Steurer, Assistant Professor, Computer Science Department, Cornell University
David Steurer: Lower bounds on the size of semidefinite programming relaxations
Speaker(s): David Steurer
Date: Tuesday, May 19, 2015
Time: 4:15 PM to 5:15 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Ravi Kannan, Microsoft Research India
Ravi Kannan: Topic Modeling and NMF using Soft Clustering
Speaker(s): Ravi Kannan
Date: Tuesday, September 22, 2015
Time: 4:15 PM to 5:15 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Dana Moshkovitz,
Dana Moshkovitz: Amplification and Derandomization Without Slowdown
Speaker(s): Dana Moshkovitz
Date: Tuesday, September 29, 2015
Time: 4:15 PM to 5:15 PM
Location: Patil Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Mika Göös, Department of Computer Science of the University of Toronto
Mika Göös: Communication Complexity vs. Partition Numbers
Speaker(s): Mika Göös
Date: Tuesday, October 06, 2015
Time: 4:15 PM to 5:15 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Benjamin Rossman,
Benjamin Rossman: The Average Sensitivity Bounded-Depth Formulas
Speaker(s): Benjamin Rossman
Date: Tuesday, October 13, 2015
Time: 4:15 PM to 5:15 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Noga Ron-Zewi,
Noga Ron-Zewi: High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity
Speaker(s): Noga Ron-Zewi
Date: Tuesday, October 27, 2015
Time: 4:00 PM to 5:00 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Elchanan Mossel, Professor, Statistics & CS, UC Berkeley,
Elchanan Mossel: Corruption Detection and Shotgun Assembly of Networks
Speaker(s): Elchanan Mossel, Professor, Statistics & CS, UC Berkeley
Date: Tuesday, November 03, 2015
Time: 4:00 PM to 5:00 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Mortiz Hardt,
Mortiz Hardt: Reliable Machine Learning Through Algorithmic Stability
Speaker(s): Mortiz Hardt
Date: Thursday, November 19, 2015
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Nati Linial, Hebrew University
Nati Linial: High-Dimensional Permutations
Speaker(s): Nati Linial
Date: Tuesday, November 24, 2015
Time: 4:00 PM to 5:00 PM
Location: G449 Patil/Kiva
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Julian Shun,
Julian Shun: Shared-Memory Parallelism Can Be Simple, Fast, and Scalable
Speaker(s): Julian Shun
Date: Monday, November 30, 2015
Time: 4:00 PM to 5:00 PM
Location: D-463 Star
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Nike Sun, MIT
Nike Sun: The Exact k-SAT Threshold for Large k
Speaker(s): Nike Sun
Date: Tuesday, December 01, 2015
Time: 4:15 PM to 5:15 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Mary Wootters, Carnegie Mellon University (CMU)
Repairing Reed-Solomon Codes
Speaker(s): Mary Wootters
Date: Monday, December 07, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Li-Yang Tan,
Li-Yang Tan: Unconditional Lower Bounds in Complexity Theory
Speaker(s): Li-Yang Tan
Date: Tuesday, December 08, 2015
Time: 4:00 PM to 5:00 PM
Location: Patil/Kiva G449
Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu