Algorithms and Complexity Seminar 2023


Jason Li, UC Berkeley
Minimum Isolating Cuts: A new tool for solving minimum cut problems
Speaker(s): Jason Li
Date: Wednesday, February 15, 2023
Time: 4:00 PM to 5:00 PM
Location:
Contact: Noah Golowich, nzg@csail.mit.edu

Rajesh Jayaram, Google NYC
Streaming Euclidean MST to a Constant Factor
Speaker(s): Rajesh Jayaram
Date: Thursday, February 16, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Roie Levin, Tel Aviv University
Online Covering: Secretaries, Prophets and Universal Maps
Speaker(s): Roie Levin
Date: Wednesday, February 22, 2023
Time: 4:15 PM to 5:15 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Huy Lê Nguyễn, Northeastern University
Efficient locally private algorithms for estimation problems
Speaker(s): Huy Lê Nguyễn
Date: Wednesday, March 01, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Misha Khodak, CMU
New Directions in Algorithms with Predictions: Learning and Privacy
Speaker(s): Misha Khodak
Date: Wednesday, March 08, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Ludwig Schmidt, University of Washington
A data-centric view on reliable generalization: From ImageNet to LAION-5B
Speaker(s): Ludwig Schmidt
Date: Thursday, March 09, 2023
Time: 3:00 PM to 4:00 PM
Location: 32-G449
Contact: Noah Golowich, nzg@csail.mit.edu

Khashayar Gatmiry, MIT
Sampling with Barriers: Faster Mixing via Lewis Weights
Speaker(s): Khashayar Gatmiry
Date: Wednesday, March 15, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Lydia Zakynthinou, Northeastern University
From Robustness to Privacy and Back
Speaker(s): Lydia Zakynthinou
Date: Thursday, March 23, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu

Chin Ho Lee, Harvard University
Bounded independence plus noise and derandomization
Speaker(s): Chin Ho Lee
Date: Wednesday, April 12, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Matheus Venturyne Xavier Ferreira, Harvard
Credible Decentralized Exchange Design via Verifiable Sequencing Rules
Speaker(s): Matheus Venturyne Xavier Ferreira
Date: Wednesday, April 19, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Maryam Aliakbarpour,
Statistical inference with computational constraints
Speaker(s): Maryam Aliakbarpour
Date: Wednesday, April 26, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Ewin Tang, University of Washington
Query-optimal estimation of unitary channels in diamond distance
Speaker(s): Ewin Tang
Date: Thursday, April 27, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G449
Contact: Noah Golowich, nzg@csail.mit.edu

Or Zamir, IAS & Princeton
Algorithmic Applications of Hypergraph and Partition Containers
Speaker(s): Or Zamir
Date: Tuesday, May 30, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Nika Haghtalab, UC Berkeley
A unified framework for robustness, fairness, and collaboration in machine learning
Speaker(s): Nika Haghtalab
Date: Wednesday, September 06, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Pasin Manurangsi, Google Research
User-Level Differential Privacy With Few Examples Per User
Speaker(s): Pasin Manurangsi
Date: Monday, September 25, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G449
Contact: Noah Golowich, nzg@csail.mit.edu

Shivam Gupta, UT Austin
Finite-Sample Symmetric Mean Estimation with Fisher Information Rate
Speaker(s): Shivam Gupta
Date: Wednesday, October 04, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu

Sidhanth Mohanty, MIT
High-dimensional expansion in random geometric graphs
Speaker(s): Sidhanth Mohanty
Date: Wednesday, October 11, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Nikhil Vyas, Harvard University
On Provable Copyright Protection for Generative Models
Speaker(s): Nikhil Vyas
Date: Wednesday, October 18, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Binghui Peng, Columbia Uniersity
Fast (distributional) swap regret and applications to approximate correlated equilibria
Speaker(s): Binghui Peng
Date: Wednesday, October 25, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rahul Ilango, rilango@mit.edu

Chris Harshaw, MIT
Clip-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments
Speaker(s): Chris Harshaw
Date: Wednesday, November 01, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Mitali Bafna, MIT
Direct Product Testing on High Dimensional Expanders
Speaker(s): Mitali Bafna
Date: Wednesday, November 15, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Yeshwanth Cherapanamjeri, MIT
Optimal PAC Bounds without Uniform Convergence
Speaker(s): Yeshwanth Cherapanamjeri
Date: Monday, November 27, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu

Ali Vakilian, TTIC
Algorithms for Generalized Clustering: Min-Max Objective to Cascaded Norms
Speaker(s): Ali Vakilian
Date: Wednesday, December 06, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu

Lijie Chen, UC Berkeley
New Circuit Lower Bounds via Solving Range Avoidance
Speaker(s): Lijie Chen
Date: Thursday, December 07, 2023
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu