Algorithms and Complexity Seminar 2022
Sepehr Assadi, Rutgers University
Deterministic Graph Coloring in the Streaming Model
Speaker(s): Sepehr Assadi
Date: Wednesday, March 02, 2022
Time: 4:00 PM to 5:00 PM
Location: https://mit.zoom.us/j/94625002202?pwd=bkROYjdBZStKeUIzVlNNTU11MVp6dz09
Contact: Noah Golowich, nzg@csail.mit.edu
Ewin Tang, University of Washington
Optimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States
Speaker(s): Ewin Tang
Date: Wednesday, March 30, 2022
Time: 4:00 PM to 5:00 PM
Location:
Contact: Rahul Ilango, rilango@mit.edu
Clayton Sanford,
A&C Seminar: Clayton Sanford "On the Approximation Power of Two-Layer Networks of Random ReLUs"
Speaker(s): Clayton Sanford
Date: Friday, April 08, 2022
Time: 4:00 PM to 5:00 PM
Location: Seminar Room G575
Contact: Rahul Ilango, rilango@csail.mit.edu
Rahul Santhanam, Oxford University
A&C Seminar: Rahul Santhanam "Errorless vs Error-Prone Average-Case Hardness"
Speaker(s): Rahul Santhanam
Date: Wednesday, April 13, 2022
Time: 2:00 PM to 3:00 PM
Location:
Contact: Rahul Ilango, rilango@csail.mit.edu
Roei Tell, IAS
A&C Seminar: Roei Tell on "Hardness vs randomness without PRGs, and derandomizing interactive protocols without paying for it"
Speaker(s): Roei Tell
Date: Thursday, April 14, 2022
Time: 4:00 PM to 5:00 PM
Location: Conference Room D451
Contact: Rahul Ilango, rilango@csail.mit.edu
Igor Oliveira, University of Warwick, UK
A&C Seminar: Igor Oliveira "Extracting computational hardness from classical and quantum learning algorithms"
Speaker(s): Igor Oliveira
Date: Wednesday, April 20, 2022
Time: 4:00 PM to 5:00 PM
Location:
Contact: Rahul Ilango, rilango@csail.mit.edu
Max Hopkins, UC San Diego
A&C Seminar: Max Hopkins "Hypercontractivity and Small-Set Expansion on High Dimensional Expanders"
Speaker(s): Max Hopkins
Date: Thursday, April 21, 2022
Time: 4:00 PM to 5:00 PM
Location: Seminar Room G575
Contact: Rahul Ilango, rilango@csail.mit.edu
Ruta Mehta, University of Illinois at Urbana-Champaign
Allocating Goods, Bads, and Mixed: Fairness and Efficiency through Competitiveness
Speaker(s): Ruta Mehta
Date: Wednesday, April 27, 2022
Time: 4:00 PM to 5:00 PM
Location:
Contact: Noah Golowich, nzg@csail.mit.edu
Jakub Tětek, University of Copenhagen
A&C Seminar: Jakub Tětek on "Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs"
Speaker(s): Jakub Tětek
Date: Wednesday, May 04, 2022
Time: 4:00 PM to 5:00 PM
Location: Seminar Room D463 (Star)
Contact: Rahul Ilango, rilango@csail.mit.edu
Isaac Grosof, Carnegie Mellon University
Optimal Scheduling in the Multiserver-job Model
Speaker(s): Isaac Grosof
Date: Thursday, September 08, 2022
Time: 4:00 PM to 5:00 PM
Location:
Contact: Noah Golowich, nzg@csail.mit.edu
Harsha Vardhan Simhadri, Microsoft Research India
Approximate Nearest Neighbor Search algorithms for web-scale search and recommendation
Speaker(s): Harsha Vardhan Simhadri
Date: Wednesday, September 14, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu
Nicole Wein, DIMACS/Rutgers
A&C Seminar: Nicole Wein on "Closing the Gap Between Directed Hopsets and Shortcut Sets"
Speaker(s): Nicole Wein
Date: Wednesday, September 28, 2022
Time: 4:00 PM to 5:00 PM
Location:
Contact: Rahul Ilango, rilango@csail.mit.edu
William Kuszmaul, MIT
William Kuszmaul on Online List Labeling: Breaking the log^2 n Barrier
Speaker(s): William Kuszmaul
Date: Wednesday, October 05, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu
Ainesh Bakshi, MIT
Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products
Speaker(s): Ainesh Bakshi
Date: Wednesday, October 12, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu
Jessica Shi, MIT
Theoretically and Practically Efficient Parallel Nucleus Decomposition
Speaker(s): Jessica Shi
Date: Wednesday, October 26, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu
Jad Silbak, Tel Aviv University
Jad Silbak: On the Complexity of Two-Party Differential Privacy
Speaker(s): Jad Silbak
Date: Tuesday, November 08, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-D507
Contact: Noah Golowich, nzg@csail.mit.edu
Mikhail Makarov, École Polytechnique Fédérale de Lausanne (EPFL)
Mikhail Makarov: Motif Cut Sparsification
Speaker(s): Mikhail Makarov
Date: Wednesday, November 09, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu
Haotian Jiang, University of Washington
Haotian Jiang: Classical and New Tools for Discrepancy Theory, and What They Say About the Matrix Spencer Conjecture
Speaker(s): Haotian Jiang
Date: Monday, November 14, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Noah Golowich, nzg@csail.mit.edu
Lijie Chen, Computer Science at UC Berkeley
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Speaker(s): Lijie Chen
Date: Tuesday, November 29, 2022
Time: 12:00 PM to 1:00 PM
Location: 32-G575
Contact: Rahul Ilango, rilango@csail.mit.edu
Aparna Gupte, MIT
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
Speaker(s): Aparna Gupte
Date: Wednesday, November 30, 2022
Time: 4:00 PM to 5:00 PM
Location: 32-G575
Contact: Rahul Ilango, rilango@csail.mit.edu
Ronitt Rubinfeld, MIT
A&C Seminar: Ronitt Rubinfeld on "A Comedy of Errors" then "Ask Me Anything"
Speaker(s): Ronitt Rubinfeld
Date: Wednesday, December 07, 2022
Time: 1:00 PM to 2:00 PM
Location: G882
Contact: Rahul Ilango, rilango@csail.mit.edu