Algorithms and Complexity Seminar 2024


D Ellis Hershkowitz, Brown University
Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies
Speaker(s): D Ellis Hershkowitz
Date: Wednesday, February 28, 2024
Time: 4:00 PM to 5:00 PM
Location: G575
Contact: Rahul Ilango, rilango@csail.mit.edu

Brian Zhang, Carnegie Mellon University
Efficient Φ-Regret Minimization with Linear and Low-Degree Swap Deviations in Extensive-Form Games
Speaker(s): Brian Zhang
Date: Wednesday, March 06, 2024
Time: 4:00 PM to 5:00 PM
Location: G575
Contact: Rahul Ilango, rilango@csail.mit.edu

Ilya Volkovich, Boston College
Synergy between Circuit Obfuscation and Circuit Minimization
Speaker(s): Ilya Volkovich
Date: Wednesday, March 13, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Kai Zheng, MIT
Near Optimal Alphabet-Soundness Tradeoff PCPs
Speaker(s): Kai Zheng
Date: Wednesday, March 20, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Vahab Mirrokni, Google Research
ML Efficiency for Large Models: Faster Transformers, Sparsity, and beyond
Speaker(s): Vahab Mirrokni
Date: Thursday, April 11, 2024
Time: 2:00 PM to 3:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu

Peter Manohar, CMU
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes
Speaker(s): Peter Manohar
Date: Wednesday, April 17, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Dmitrii Avdiukhin, Northwestern Uniersity
Optimal Sample Complexity of Contrastive Learning
Speaker(s): Dmitrii Avdiukhin
Date: Thursday, April 18, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu

Felix Zhou, Yale University
Lipschitz Continuous Graph Algorithms via Proximal Gradient Analysis
Speaker(s): Felix Zhou
Date: Wednesday, April 24, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Alex Psomas, Purdue University
Theory and Practice of Fair Food Allocation
Speaker(s): Alex Psomas
Date: Thursday, April 25, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu

Ce Jin & Yinzhan Xu, MIT
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Speaker(s): Ce Jin & Yinzhan Xu
Date: Wednesday, May 01, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Meghal Gupta, UC Berkeley
Optimal Quantile Estimation: Beyond the Comparison Model
Speaker(s): Meghal Gupta
Date: Monday, May 06, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu

Andrea Lincoln, Boston University
A Biased Introduction to Average-Case Fine Grained Complexity
Speaker(s): Andrea Lincoln
Date: Wednesday, May 08, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Gavin Brown, Boston University
Stable Estimators for Fast Private Statistics
Speaker(s): Gavin Brown
Date: Wednesday, May 15, 2024
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu