Algorithms and Complexity Series Fall 2014 / Spring 2015
All seminars at 4pm in G575 unless otherwise noted
Richard Peng, MIT
Richard Peng: Solving SDD Linear Systems in Nearly mlog1/2n Time
Speaker(s): Richard Peng
Date: Friday, September 12, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Hammurabi Mendes, Brown
Hammurabi Mendes, Multidimensional ?- Approximate Agreement and Computability in Byzantine Systems
Speaker(s): Hammurabi Mendes
Date: Wednesday, September 24, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Avishay Tal, Weizmann Institute
Avishay Tal: Shrinkage of De Morgan Formulae by Spectral Techniques
Speaker(s): Avishay Tal
Date: Thursday, October 23, 2014
Time: 2:30 PM to 3:30 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
John Wright, Carnegie Mellon University (CMU)
Quantum Spectrum Testing
Speaker(s): John Wright
Date: Thursday, November 13, 2014
Time: 2:00 PM to 3:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Cameron Musco, MIT
Cameron Musco: Uniform Sampling for Matrix Approximation
Speaker(s): Cameron Musco
Date: Thursday, November 20, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Aviad Rubinstein, UC Berkeley
Inapproximability of Nash Equilibrium
Speaker(s): Aviad Rubinstein
Date: Tuesday, November 25, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu
Sepideh Mahabadi, MIT
Approximate Nearest Line Search in High Dimensions
Speaker(s): Sepideh Mahabadi
Date: Thursday, December 11, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Bernhard Haeupler, Carnegie Mellon University (CMU)
TALK: CODING FOR INTERACTIVE COMMUNICATION MADE EFFICIENT AND EASY (OR "HOW TO MAKE CONVERSATIONS ROBUST TO NOISE.")
Speaker(s): Bernhard Haeupler
Date: Tuesday, December 23, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Eric Price, UT Austin
Tight bounds for learning a mixture of two Gaussians
Speaker(s): Eric Price
Date: Wednesday, January 14, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Richard Peng,
Richard Peng: Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification
Speaker(s): Richard Peng
Date: Wednesday, February 25, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Henry Yuen
Michael Cohen, MIT
Michael Cohen: l_p Row Sampling by Lewis Weights
Speaker(s): Michael Cohen
Date: Wednesday, March 04, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Jelani Nelson, Harvard
The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
Speaker(s): Jelani Nelson
Date: Wednesday, March 11, 2015
Time: 2:30 PM to 3:30 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Peter van Emde Boas, University of Amsterdam
Peter van Emde Boas: History of the van Emde Boas Trees
Speaker(s): Peter van Emde Boas
Date: Wednesday, March 18, 2015
Time: 3:30 PM to 4:30 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Cameron Musco,
Cameron Musco: Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Speaker(s): Cameron Musco
Date: Wednesday, April 01, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Grigory Yaroslavtsev, UPenn
Grigory Yaroslavtsev:Near Optimal LP Rounding for Correlation Clustering on Complete Graphs
Speaker(s): Grigory Yaroslavtsev
Date: Thursday, April 09, 2015
Time: 3:15 PM to 4:15 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Henry Yuen, MIT
Henry Yuen: Parallel repetition for entangled games via fast quantum search
Speaker(s): Henry Yuen
Date: Wednesday, April 15, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
This event has been cancelled.
Henry Yuen: Parallel repetition for entangled games via fast quantum search
Speaker(s):
Date: Wednesday, April 15, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Sergey Gorbunov,
Sergey Gorbunov: Leveled Fully Homomorphic Signatures from Standard Lattices
Speaker(s): Sergey Gorbunov
Date: Wednesday, April 22, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
JM Landsberg, Texas A&M
Geometry and the Complexity of Matrix Multiplication
Speaker(s): JM Landsberg
Date: Wednesday, April 29, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Siu On Chan,
Siu On Chan: Sum of Squares Lower Bounds from Pairwise Independence
Speaker(s): Siu On Chan
Date: Wednesday, May 06, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Shay Solomon, The Weizmann Institute of Science
Shay Solomon: Dynamic Maximum Matching and Related Problems
Speaker(s): Shay Solomon
Date: Thursday, May 07, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Rati Gelashvili, MIT
Rati Gelashvili: Polylogarithmic-Time Leader Election in Population Protocols Using Polylogarithmic States
Speaker(s): Rati Gelashvili
Date: Wednesday, May 20, 2015
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu