Theory of Computation Colloquium Series
Seminar series coordinated by Kuikui Liu and Sam Hopkins.
If you would like to be on the mailing list for this seminar series, please contact Olivia Cheo at: olivia (at) csail.mit.edu
Unless noted otherwise, the talks take place on Tuesdays, 4:15–5:15 pm, in 32-G449 (Kiva/Patil); refreshments served at 4:00 PM.
Our Zoom policy can be found here.
Fall 2026
September 15, 2026: Or Zamir (Tel Aviv University), "k-Coloring is Faster than Computing the Chromatic Number"
September 29, 2026: Frederic Koehler (UChicago), "Anticoncentration of Gaussian permanents"
October 06, 2026: Larry Guth (Mathematics), "Hard pure math problems and hard algorithmic problems" in 32-141
Spring 2026
Friday, March 06, 2026: Piotr Indyk (MIT), "Graph-Based Algorithms for Similarity Search: Challenges and Opportunities" at 11:00 AM in E18-304; part of IDSS' Statistics and Data Science Seminar Series
Thursday, March 12, 2026: Jim Orlin (MIT), "Interdiction problems and 2-person sequential games: beyond NP-completeness" in E51-145; co-hosted by MIT's Operations Research Center
March 17, 2026: Shachar Lovett (UCSD), "Corners and Communication Complexity"
March 24, 2026: Spring Break, no seminar
April 07, 2026: Kuikui Liu (MIT), "On zeros and algorithms for disordered systems"
April 14, 2026: Nir Shavit (MIT), "Toy Models of Combinatorial Interpretability"
April 21, 2026: Jerry Li (University of Washington), "Lower bounds for Learning Hamiltonians from Time Evolution"
April 28, 2026: Xi Chen (Columbia), "Adaptivity Does Not Help: Nearly Tight Lower Bounds for Boolean Monotonicity Testing" in 32-124
May 05, 2026: Aaron Roth (UPenn), "Calibration in the Age of AI: From Prediction to Decision Making to AI Assisted Research"
May 12, 2026: Madhur Tulsiani (TTIC), "List Decoding Expander-Based Codes (up to capacity, in near-linear time)"
September 09, 2025: Adam Klivans (UT Austin), "A New Paradigm for Learning with Distribution Shift"
September 16, 2025: Standa Zivny (Oxford), "Sparsification of 1-in-3-SAT"
September 23, 2025: Rachel Zhang (MIT), "Explicit Lossless Vertex Expanders"
October 07, 2025: Nikhil Bansal (University of Michigan), "On Beck-Fiala and Komlós Conjectures"
October 14, 2025: Vincent Cohen-Addad (Google Research), "Introducing Algorithmic Thinking Theory for Foundation Models"
October 28, 2025: Venkat Guruswami (Berkeley), "Redundancy is all you need (for CSP sparsification)"
November 11, 2025: MIT closed for Veterans Day
December 09, 2025: Ronitt Rubinfeld (MIT), "Can we speed safely?"
February 11, 2025: Irit Dinur, "'Local-to-Global' Theorems on High Dimensional Expanders"
February 18, 2025: Micah Adler, "On the Complexity of Neural Computation in Superposition"
February 25, 2025: Alex Lubotzky, "Good Locally Testable Codes"
March 04, 2025: Elette Boyle, "Pseudorandom Correlation Generators"
March 11, 2025: Andrea Montanari, "Overparametrized systems: from Smale's 17th problem to two-layer neural networks"
March 18, 2025: Zongchen Chen, "Rapid Mixing at the Uniqueness Threshold"
March 25, 2025: Spring Break, no seminar
April 08, 2025: Ryan Williams, "Simulating Time With Square-Root Space"
April 15, 2025: Ilias Diakonikolas, "Learning Multi-Index Models"
April 22, 2025: Adi Shamir, "How to Securely Implement Cryptography in Deep Neural Networks"
May 06, 2025: Sam Hopkins, "Deciding high-dimensional sub-Gaussian-ness in polynomial time" in ✮ 32-D463 Star ✮
Fall 2024
September 17, 2024: Chara Podimata, "Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry"
September 24, 2024: Kai Zhe Zheng, "Near Optimal Alphabet-Soundness Tradeoff PCPs"
October 08, 2024: Thodoris Lykouris, "Learning to Defer in Content Moderation: The Human-AI Interplay"
October 15, 2024: Student Holiday: no seminar
November 19, 2024: Soheil Behnezhad, "Vizing’s Theorem in Near-Linear Time"
November 26, 2024: Monika Henzinger, "Recent Advances in Differential Privacy under Continual Observation"
December 03, 2024: Ramon van Handel, "A New Approach to Optimal Spectral Gaps" in 32-124
December 10, 2024: Ryan O'Donnell, "Coboundary Expansion Inside Chevalley Coset Complex HDXs"
September 6, 2023: Nika Haghtalab
September 19, 2023: Adam Kalai
October 3, 2023: Rahul Santhanam
October 17, 2023: Xin Li
October 24, 2023: Eva Tardos
November 14, 2023: Yuval Ishai
November 21, 2023: Fermi Ma
December 5, 2023: Kasper Green Larsen: Bagging is an Optimal PAC Learner
Fall 2022
October 25, 2022: David Zuckerman, Almost Chor-Goldreich Sources and Adversarial Random Walks
November 1, 2022: No seminar (FOCS '22)
November 8, 2022: Cancelled (due to the speaker's health problems)
November 15, 2022: Alexandr Andoni, Estimating the Longest Increasing and Longest Common Subsequences
November 22, 2022: Seth Pettie, Algorithms Should Have
November 29, 2022: Yang P. Liu, Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
December 6, 2022: Shuichi Hirahara, NP-Hardness of Learning Programs and Partial MCSP
December 13, 2022: Daniel Wichs, Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation
Spring 2022
March 8, 2022: Yael Lalai: Efficient Verification of Computation on Untrusted Platforms
March 15, 2022: Manuel Blum: The Conscious Turing Machine (CTM): A Theoretical CS Approach to the Hard Problem
March 22, 2022: No seminar (Spring Break)
March 29, 2022: Anurag Anshu: Complexity of Local Hamiltonians via Polynomial Approximations to AND Function
April 5, 2022: No seminar
April 12, 2022: Roei Tell: New Directions in Derandomization: Non-Black-Box Techniques, Superfast Algorithms
April 19, 2022: Tselil Schramm: Testing Thresholds for High-Dimensional Random Geometric Graphs
April 26, 2022: Pravesh Kothari: Refuting Smoothed k-SAT Formulas and a Proof of Feige's Conjecture
May 3, 2022: Anand Natarajan:
May 10, 2022: Jerry Li: Clustering Mixtures with Almost Optimal Separation in Polynomial Time
Fall 2021
September 28, 2021: Kuikui Liu: Markov Chain Analysis via Spectral Independence
October 5, 2021: Swastik Kopparty: Fast algorithms for polynomials over all finite fields via the Elliptic Curve Fast Fourier Transform (ECFFT)
October 12, 2021: Nutan Limaye: Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
October 19, 2021: Li-Yang Tan: Properly Learning Decision Trees In Almost Polynomial Time
October 26, 2021: Greg Valiant: Sequential Prediction: Calibration and Selective Prediction
November 2, 2021: No Seminar, ToC Deadline
November 9, 2021: Shachar Lovett: The log-rank conjecture - where do we stand?
November 16, 2021: Noga Alon: PAC Learnability of partial concept classes
November 23, 2021: Sanjoy Dasgupta: Some excursions into interpretable machine learning
November 30, 2021: Subhash Khot: On Approximability of CSPs on Satisfiable Instances
December 7, 2021: (STAR) Merav Parter: New Diameter Reducing Shortcuts: Breaking the $O(\sqrt{n})$ Barrier
Spring 2021
February 23, 2021:
March 2, 2021:
March 9, 2021:
March 16, 2021:
March 23, 2021:No Seminar "Spring Break"
March 30, 2021:
April 6, 2021:
April 13, 2021:
April 20, 2021: No Seminar "Student Holiday"
April 27, 2021:
May 4, 2021:
May 11, 2021:
May 18, 2021:
Archive 2013-2020
Archive 2000-2013