Algorithms and Complexity Seminar Series 2016/2017


Jonathan Mosheiff , Hebrew University
On the Rigidity of Sparse Random Graphs
Speaker(s): Jonathan Mosheiff
Date: Tuesday, August 23, 2016
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Ofer Grossman, MIT
Bipartite Perfect matching in Pseudo-deterministic NC
Speaker(s): Ofer Grossman
Date: Wednesday, September 21, 2016
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Rasmus Kyng, Yale
Approximate Gaussian Elimination for Laplacians
Speaker(s): Rasmus Kyng
Date: Wednesday, September 28, 2016
Time: 3:00 PM to 4:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Ilias Diakonikolas, University of Southern California
A New Approach for Distribution Testing
Speaker(s): Ilias Diakonikolas
Date: Wednesday, October 12, 2016
Time: 4:00 PM to 5:00 PM
Location: Conference Room G575
Contact: Akshay Dhananjai Degwekar, akshayd@csail.mit.edu

Alex Wein, MIT
Optimality and sub-optimality of PCA for spiked random matrix models
Speaker(s): Alex Wein
Date: Wednesday, October 19, 2016
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Rati Gelashvili,
Time-Space Trade-Offs in Molecular Computation
Speaker(s): Rati Gelashvili
Date: Wednesday, October 26, 2016
Time: 4:00 PM to 5:00 PM
Location: 32)g575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Huy L. Nguyen, Northeastern U.
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
Speaker(s): Huy L. Nguyen
Date: Wednesday, November 09, 2016
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Tengyu Ma, Princeton
Analyzing non-convex optimization: matrix completion and linear residual networks
Speaker(s): Tengyu Ma
Date: Wednesday, November 30, 2016
Time: 4:00 PM to 5:00 PM
Location: G575
Contact: Aleksander Madry, madry@csail.mit.edu

Dhiraj Holden, MIT CSAIL
Solving Problems in P given Correlated Instances
Speaker(s): Dhiraj Holden
Date: Wednesday, December 07, 2016
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Morteza Monemizadeh, Rutgers University
Testable Bounded Degree Graph Properties Are Random Order Streamable
Speaker(s): Morteza Monemizadeh
Date: Thursday, December 08, 2016
Time: 4:00 PM to 5:00 PM
Location: 32-G882
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Nika Haghtalab, Carnegie Mellon University (CMU)
Opting Into Optimal Matchings
Speaker(s): Nika Haghtalab
Date: Wednesday, March 01, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Yuval Filmus, Technion, Israel
Twenty (simple) questions
Speaker(s): Yuval Filmus
Date: Thursday, March 02, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Dean Doron, Tel-Aviv University
Explicit two-source extractors for near-logarithmic min-entropy
Speaker(s): Dean Doron
Date: Wednesday, March 15, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Ben Rossman, U. Toronto
Ben Rossman:New Separations of Formula vs. Circuit Size
Speaker(s): Ben Rossman
Date: Thursday, March 30, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Clement Canonne, Columbia University
Fifty Shades of Adaptivity (in Property Testing)
Speaker(s): Clement Canonne
Date: Wednesday, April 05, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Richard Baraniuk, Rice University
A Probabilistic Theory of Deep Learning
Speaker(s): Richard Baraniuk
Date: Thursday, April 06, 2017
Time: 3:00 PM to 4:00 PM
Location: 32-D463 (Star)
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Ben Rossman, U. Toronto
New separations of formula vs. circuit size
Speaker(s): Ben Rossman
Date: Wednesday, April 12, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

This event has been cancelled. Inbal Talgam-Cohen, Hebrew University
Approximate Modularity Revisited
Speaker(s): Inbal Talgam-Cohen
Date: Tuesday, April 18, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G449 (Kiva)
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Inbal Talgam-Cohen, Hebrew University
Approximate Modularity Revisited
Speaker(s): Inbal Talgam-Cohen
Date: Thursday, April 20, 2017
Time: 4:00 PM to 5:00 PM
Location: Conference Room G575
Contact: Akshay Dhananjai Degwekar, akshayd@csail.mit.edu

Govind Ramnarayan, CSAIL MIT
Relaxed Locally Correctable Codes
Speaker(s): Govind Ramnarayan
Date: Wednesday, May 10, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-D463
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Arnab Bhattacharyya , IISc
Arnab Bhattacharyya: Hardness of Learning Noisy Halfspaces Using Polynomial Thresholds
Speaker(s): Arnab Bhattacharyya
Date: Thursday, May 11, 2017
Time: 2:00 PM to 3:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Josh Alman, CSAIL MIT
Talk: Cell-Probe Lower Bounds from Online Communication Complexity
Speaker(s): Josh Alman
Date: Wednesday, May 24, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Andrea Lincoln, CSAIL MIT
Talk: Andrea Lincoln:Conditional Hardness for Sensitivity Problems
Speaker(s): Andrea Lincoln
Date: Wednesday, May 31, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Harry Lang, Johns Hopkins University
Harry Lang: Coresets for k-Means-Type Problems on Streams
Speaker(s): Harry Lang
Date: Wednesday, July 05, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu