Algorithms and Complexity Seminar Series 2017/2018


Dor Minzer, Tel-Aviv University
An approach for 2-to-1 Games Conjecture via expansion on the Grassmann Graph
Speaker(s): Dor Minzer
Date: Wednesday, September 06, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Paul Hand, Rice University
Paul Hand: Deep Compressed Sensing
Speaker(s): Paul Hand
Date: Wednesday, September 27, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-D463 (Star)
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Yuval Dagan, Technion
Trading Information Complexity for Error
Speaker(s): Yuval Dagan
Date: Thursday, September 28, 2017
Time: 3:00 PM to 4:00 PM
Location: Conference Room G575
Contact: Akshay Dhananjai Degwekar, akshayd@csail.mit.edu

Lijie Chen, MIT
On The Power of Statistical Zero Knowledge
Speaker(s): Lijie Chen
Date: Wednesday, October 11, 2017
Time: 4:00 PM to 5:00 PM
Location: Conference Room G575
Contact: Akshay Dhananjai Degwekar, akshayd@csail.mit.edu

Pritish Kamath, MIT
Non-Interactive Agreement & Dimension Reduction for Polynomials
Speaker(s): Pritish Kamath
Date: Wednesday, October 25, 2017
Time: 4:30 PM to 5:30 PM
Location: Conference Room G575
Contact: Pritish Kamath, pritish@csail.mit.edu

Andrej Risteski, MIT
Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
Speaker(s): Andrej Risteski
Date: Wednesday, November 01, 2017
Time: 4:00 PM to 5:00 PM
Location: Conference Room G575
Contact: Akshay Degwekar, akshayd@csail.mit.edu

Li-Yang Tan, TTI Chicago
Fooling intersections of low-weight halfspaces
Speaker(s): Li-Yang Tan
Date: Thursday, November 02, 2017
Time: 4:00 PM to 5:00 PM
Location: Seminar Room G882 (Hewlett Room)
Contact: Akshay Degwekar, akshayd@csail.mit.edu

Jiantao Jiao, Stanford
Jiantao Jiao: Instance-optimal learning of the total variation distance
Speaker(s): Jiantao Jiao
Date: Thursday, November 16, 2017
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Pritish Kamath, pritish@csail.mit.edu

Slobodan Mitrovic, EPFL
Matchings in MPC frameworks
Speaker(s): Slobodan Mitrovic
Date: Wednesday, November 29, 2017
Time: 4:00 PM to 5:00 PM
Location: Conference Room G575
Contact: Pritish Kamath, pritish@csail.mit.edu

Jerry Li, MIT
Mixture Models, Robustness, and Sum of Squares Proofs
Speaker(s): Jerry Li
Date: Thursday, November 30, 2017
Time: 4:00 PM to 5:00 PM
Location: Seminar Room G449 (Patil/Kiva)
Contact: Pritish Kamath, pritish@csail.mit.edu

Keerti Choudhary, Weizmann Institute
Fault Tolerant Data Structures
Speaker(s): Keerti Choudhary
Date: Wednesday, January 17, 2018
Time: 4:00 PM to 5:00 PM
Location: Conference Room G575
Contact: Pritish Kamath, pritish@csail.mit.edu

Amnon Ta-Shma, Tel-Aviv University
Parity samplers and explicit, epsilon-balanced codes close to the GV Bound
Speaker(s): Amnon Ta-Shma
Date: Thursday, February 15, 2018
Time: 10:00 AM to 11:30 AM
Location: 32-D463 STAR
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Yuval Dagan , Technion
Detecting Correlations with Little Memory and Communication
Speaker(s): Yuval Dagan
Date: Wednesday, March 21, 2018
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Manuel Sabin , UC Berkeley
Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity
Speaker(s): Manuel Sabin
Date: Wednesday, April 25, 2018
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Sitan Chen, MIT
Learning Mixtures of Product Distributions via Higher Multilinear Moments
Speaker(s): Sitan Chen
Date: Wednesday, May 09, 2018
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Lisa Yang,
Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy
Speaker(s): Lisa Yang
Date: Wednesday, May 16, 2018
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Venkat Guruswami , Carnegie Mellon University (CMU)
Improved Bounds for Perfect Hashing
Speaker(s): Venkat Guruswami
Date: Thursday, May 17, 2018
Time: 4:30 PM to 5:30 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Lijie Chen,
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
Speaker(s): Lijie Chen
Date: Thursday, May 24, 2018
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Arnab Bhattacharyya, Indian Institute of Science
Parameterized Intractability of Even Set
Speaker(s): Arnab Bhattacharyya
Date: Thursday, June 07, 2018
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu

Brendan Juba,
New Algorithms for Conditional Linear Regression
Speaker(s): Brendan Juba
Date: Monday, July 30, 2018
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu