Algorithms and Complexity Series Fall 2013 / Spring 2014

All seminars at 4pm in G575 unless otherwise noted

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


Grigory Yaroslavtsev, Brown University
Property Testing and Communication Complexity
Speaker(s): Grigory Yaroslavtsev
Date: Wednesday, September 11, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Joanne Talbot Hanley, 3-6054, joanne@csail.mit.edu

Ruta Mehta, Gerogia Tech
(Essentially) Resolving the Complexity of Constant Rank Bimatrix Games
Speaker(s): Ruta Mehta
Date: Wednesday, November 06, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Ludwig Schmidt, MIT
Ludwig Schmidt: Approximation-Tolerant Model-Based Compressive Sensing
Speaker(s): Ludwig Schmidt
Date: Wednesday, November 13, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Daniel Kane, Stanford University
Pseudorandom Generators for Polynomial Threshold Functions
Speaker(s): Daniel Kane
Date: Monday, November 18, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Ilya Razenshteyn, MIT/CSAIL
Beyond Locality-Sensitive Hashing
Speaker(s): Ilya Razenshteyn
Date: Wednesday, November 20, 2013
Time: 4:00 PM to 5:00 PM
Location: 32 G575
Contact: Nina L. Olff, 617-253-6025, olff@csail.mit.edu

Ankit Sharma, Carnegie Mellon University (CMU)
Ankit Sharma TALK
Speaker(s): Ankit Sharma
Date: Monday, November 25, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Nina L. Olff, 617-253-6025, olff@csail.mit.edu

Thomas Steinke, Harvard
Pseudorandomness for Regular Branching Programs via Fourier Analysis
Speaker(s): Thomas Steinke
Date: Wednesday, December 04, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Nina L. Olff, olff@csail.mit.edu

Mohammad Bavarian, MIT
Beyond XOR Games: Information causality, Szemer├ędi-Trotter and Algebraic Variants of CHSH
Speaker(s): Mohammad Bavarian
Date: Wednesday, December 11, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Arnab Bhattacharyya,
Algorithmic Regularity for Polynomials and Applications
Speaker(s): Arnab Bhattacharyya
Date: Friday, December 13, 2013
Time: 1:30 PM to 2:30 PM
Location: G882
Contact: Joanne Talbot Hanley, 3-6054, joanne@csail.mit.edu

Michael Kapralov, MIT
Approximating matching size from random streams
Speaker(s): Michael Kapralov
Date: Wednesday, December 18, 2013
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Joanne Talbot Hanley, 3-6054, joanne@csail.mit.edu

Matthew Coudron, MIT
Infinite Randomness Expansion with a Constant Number of Devices
Speaker(s): Matthew Coudron
Date: Thursday, January 23, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Ilya Razenshteyn, ilyaraz@csail.mit.edu

Grigory Yaroslavtsev, Brown
APPROXIMATING GRAPH PROBLEMS: THE OLD AND THE NEW
Speaker(s): Grigory Yaroslavtsev
Date: Wednesday, February 19, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Alexander Belov, MIT
Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound
Speaker(s): Alexander Belov
Date: Wednesday, March 12, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Patrice Macaluso, , macaluso@csail.mit.edu

Alexander Belov, MIT
Quantum Algorithms for Learning and Testing Juntas via the Adversary Bound
Speaker(s): Alexander Belov
Date: Wednesday, March 26, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Kyle Fox, ICERM
Optimal Cuts in Surface Imbedded Graphs
Speaker(s): Kyle Fox
Date: Wednesday, April 02, 2014
Time: 4:30 PM to 5:30 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Carol Wang, Carnegie Mellon University (CMU)
Explicit List-Decodable Subspace Codes with High Rate
Speaker(s): Carol Wang
Date: Wednesday, April 09, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, (617)253-6025, ryadegar@csail.mit.edu

Rati Gelashvili, MIT
Leader Election and Renaming with Optimal Message Complexity
Speaker(s): Rati Gelashvili
Date: Wednesday, April 23, 2014
Time: 5:00 PM to 6:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Venkatesan Guruswami, Carnegie Mellon University
Talk: Hardness of (2+eps)-SAT and Balanced Hypergraph Coloring
Speaker(s): Venkatesan Guruswami
Date: Wednesday, April 30, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Sepideh Mahabadi, MIT
Talk: Sepideh Mahabadi: Composable Core-sets for Diversity and Coverage Maximization, and Its Application in Diverse Near Neighbor Problem
Speaker(s): Sepideh Mahabadi
Date: Wednesday, May 07, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Michael Brautbar, MIT
The Power of Local Information in Network Algorithms
Speaker(s): Michael Brautbar
Date: Friday, May 09, 2014
Time: 1:00 PM to 5:00 PM
Location: 32-G882
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Ali Vakilian, MIT
Improved Approximation Algorithms for Degree-bounded Network Design Problems with Node Connectivity Requirements
Speaker(s): Ali Vakilian
Date: Thursday, May 29, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Michael Forbes,
Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order
Speaker(s): Michael Forbes
Date: Thursday, May 29, 2014
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Krzysztof Onak, IBM TJ Watson Research Center
A Near-Optimal Algorithm for Testing Isomorphism of Two Unknown Graphs
Speaker(s): Krzysztof Onak
Date: Wednesday, July 23, 2014
Time: 11:00 AM to 12:00 PM
Location: 32-D463
Contact: Ronitt Rubinfeld, ronitt@csail.mit.edu