**Theory of Computation Colloquium Series**

Seminar series coordinated by Kuikui Liu and Sam Hopkins.

If you would would like to be on the mailing list for this seminar series, please contact

Nathan Higgins at: nhiggins (at) mit.edu

Unless noted otherwise, the talks take place on Tuesdays, from 4:15 pm to 5:15 pm, in 32-G449 (Patil/Kiva). Refreshments will be served 4:00--4:15 pm.

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:

October 13, 2020: (RW) Alexandr Andoni: Approximating Edit Distance in Near-Linear Time

October 20, 2020: (NL) James Aspnes: Population Protocols

October 27, 2020: (MG) Nathan Klein: A (Slightly) Improved Approximation Algorithm for Metric TSP

November 3, 2020: Election Day (Remember to Vote)

November 10, 2020: (DK) Ashish Goel: Beyond Voting: Mechanisms and Platforms for Societal Decision Making

November 17, 2020: (YK) Huijia (Rachel) Lin: Indistinguishability Obfuscation from Well-Founded Assumptions

November 24, 2020: Thanksgiving Week

December 1, 2020: (MK) Toniann Pitassi: Lifting with Sunflowers

December 8, 2020: (RR) Nike Sun: Phase transitions in random constraint satisfaction problems

December 15, 2020: (AM) Surbhi Goel: Computational Complexity of Learning Neural Networks over Gaussian Marginals

February 4, 2020:

February 11,2020:

February 18, 2020: Adi Shamir, Weizmann Institute of Tech: A Simple Explanation for the Mysterious Existence of Adversarial Examples with Small Hamming Distance

February 25, 2020:

March 3, 2020:

March 10, 2020:

March 17, 2020:

March 24, 2020:

March 31, 2020:

April 7, 2020:

April 14, 2020:

April 21, 2020:

April 28, 2020:

May 5, 2020:

May 12, 2020:

__Fall 2019__

September 24, 2019: László Végh: A Strongly Polynomial Algorithm for Linear Exchange Markets

October 8, 2019: Ryan O'Donnell: Explicit near-Ramanujan graphs of every degree

October 15, 2019: Columbus Day Vacation

October 22, 2019: Rediet Abebe: Subsidy Allocations in the Presence of Income Shocks

October 29, 2019:

November 5, 2019: Anindya De: Junta correlation is testable.

November 12, 2019:

November 19, 2019:

November 26, 2019:

December 3, 2019:

December 10, 2019:

__Spring 2019__

May 16, 2019: Greg Valiant: New Problems and Perspectives on Learning, Testing, and Sampling in the Small Data Regime

February 5, 2019:

February 12. 2019:

February 26, 2019:

March 5, 2019:

March 12, 2019: Arkadev Chattopadhyay: The Log-Approximate-Rank Conjecture is False

March 19, 2019:

March 26, 2019: Spring Vacation

April 2, 2019: (Star)

April 9, 2019: Sam Hopkins: How to Estimate the Mean of a Heavy-Tailed Random Vector in Polynomial Time

April 16, 2019: Patriots' Day Holiday

April 23, 2019: (Joint with Lids) Yoram Singer: Memory-Efficient Adaptive Optimization for Humungous-Scale Learning

April 30, 2019:

May 7, 2019:

May 14, 2019:

May 21, 2019: Sepehr Assadi:

May 28, 2019: (Star)

__Fall 2018__

September 18, 2018: Costis Daskalakis: Improving Generative Adversarial Networks using Game Theory and Statistics

September, 25, 2018: Alexander Razborov: Grand Challanges in Complexity Theory through the Lens of Proof Theory

October 2, 2018: Suresh Venkatasubramanian: Towards a theory (or theories) of fairness in automated decision-making

October 9, 2018: Columbus Day Holiday

October 16, 2018: No Seminar

October 23, 2018: Urmila Mahadev: Classical Verification of Quantam Computation

October 30, 2018: No Seminar (STOC Deadline)

November 6, 2018: Vijay Vazirani: Planar Graph Perfect Matching is in NC

November 13, 2018: Aaron Sidford: Perron-Frobenius Theory in Nearly Linear Time

November 27, 2018: Avishay Tal: Oracle Seperation of BQP and the Polynomial Hierarchy

December 4, 2018: Michael Saks: Approximating the edit distance to within a constant factor in truly subquadratic time

December 11, 2018: Dean Doron: Probabilistic logspace algorithms for Laplacian solvers

February 6, 2018: Asaf Shapira (Tel Aviv University): Efficient graph property testing

February 13, 2018: Amnon Ta-Shma (Tel Aviv University): Parity samplers and explicit, epsilon-Balanced codes close to the __GV __Bound

February 20, 2018: No Seminar

February 27, 2018:

March 6, 2018:

March 13, 2018:

April 3, 2018:

April 10, 2018: Benny Applebaum (Tel Aviv University): Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

April 11, 2018: (SPECIAL DATE): Dor Minzer: 2-to-2 Games is NP-hard

April 17, 2018: Patriots' Day, No Colloquium.

April 24, 2018:

May 1, 2018:

May 8, 2018:

May 15, 2018:

September 12, 2017: Russell Impagliazzo (UCSD): Learning Modesl: Connections Between Boosting, Hard-Core Distributions, Dense Models, Gan, and Regularity

September 19, 2017: Sanjam Garg (Berkeley): Identity-Based Encryption from the Diffie-Hellman Assumption

September 26, 2017: Adam Klivans (UT Austin): Learning discrete Markov random fields with nearly optimal runtime and sample complexity

October 10, 2017: Columbus Day -- Holiday.

October 17, 2017: FOCS

October 24, 2017: David Woodruff (Carnegie Mellon University): Relative Error Tensor Low Rank Approximation

October 31, 2017: Joint with LIDS: Noga Alon (Tel-Aviv University): Structure, randomness and universality

November 7, 2017: Omer Paneth (MIT): On the Round Complexity of Zero-Knowledge Protocols and Compressing Collisions

November 14, 2017: Venkat Guruswami (CMU): Promise Constraint Satisfaction

November 28, 2017: Kasper Green Larsen (Aarhus University): Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

December 5, 2017: Pravesh Kothari: Outlier-Robust Moment Estimation via Sum-of-Squares

December 12, 2017: Barna Saha (UMass Amherst): Space & Time Efficient Algorithms for "Bounded Difference" Problems

February 7, 2017: Silvio Micali: ALGORAND: The True Public Ledger

February 14, 2017: Vitaly Feldman: Lower bounds against convex relaxations via the statistical query complexity

February 22, 2017** (Please note this seminar is on Wednesday)**: Aaron Roth: Quantifying Tradeoffs Between Fairness and Accuracy in Online Learning

February 28, 2017: Vasilis Syrgkanis: Oracle efficient Learning and Auction Design

March 14, 2017: Irit Dinur: Grassmann agreement testing and the 2:1 conjecture

March 28, 2017: MIT Spring Break

April 11, 2017: Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit

April 19, 2017: (Please note this seminar is on Wednesday): Andrea Montanari: The landscape of some statistical problems

April 25, 2017: Cynthia Dwork: What's Fair?

May 16, 2017: Ilias Diakonikolas: TBD

September 13, 2016: Boaz Barak: Computational Bayesianism, Sums of Squares, and Unicorns

September 19, 2016: (Special Day - Monday) Alina Ene: From Minimum Cut to Submodular minimization: Leveraging the Decomposable

September 27, 2016: Mohsen Ghaffari: Improved Local Distributed Graph Algorithms

October 3, 2016: (Special Day - Monday) Alexandr Andoni: Optimal Hashing for High-Dimensional Spaces

October 11, 2016: MIT Holiday - Columbus Vacation

October 18, 2016: Jonathan Ullman: Algorithmic Stability for Adaptive Data Analysis

October 25, 2016: Sebastien Bubeck: New Results at the Crosstroads of Convexity, Learning and Information Theory

November 1, 2016: Ronitt Rubinfeld: Local Computation Algorithms

November 8, 2016: Yuval Ishai: Succinct Secure Computation from DDH

November 15, 2016: Jelani Nelson: Heavy Hitters via Cluster-Preserving Clustering

November 22, 2016: Nisheeth Vishnoi:

November 29, 2016: Tim Roughgarden: How Computer Science Informs Modern Auction Design

__Spring 2016__

February 2, 2016: Laszlo Babai

February 11, 2016: (Special Date) Avi Wigderson

February 16, 2016: Joint with LIDS, Sasha Rakhlin (cookies and milk, 3:45pm in G5 lounge)

February 23, 2016: Joint with LIDS, Greg Valiant (cookies and milk, 3:45pm in G5 lounge)

March 3, 2016: (Special Date and Time) Raghu Meka

March 8, 2016: Omer Reingold

March 15, 2016: Ran Raz

March 22, 2016: Spring Break

March 29, 2016: Joint with LIDS, Dimitris Achlioptas (cookies and milk, 3:45pm in G5 lounge)

April 12, 2016: David Zuckerman

April 19, 2016: Patriot's Day, MIT Holiday

April 26, 2016: Rocco Servedio

May 3, 2016: Ken Clarkson

May 10, 2016: Madhu Sudan

**Fall 2015**

September 15, 2015: Sanjeev Arora

September 22, 2015: Ravi Kannan

September 29, 2015: Dana Moshkovitz

October 6, 2015: Mika Göös: Video of Previous Seminar

October 13, 2015: Benjamin Rossman

October 20, 2015: (Joint with LIDS) Rudi Urbanke Special Time - Starting at 4pm in 32 - 141

October 27, 2015: Noga Ron-Zewi

November 3, 2015: Elchanan Mossel

November 10, 2015: Virginia Vassilevska Williams

November 16, 2015: Omri Weinstein

November 17, 2015: Robin Kothari

November 19, 2015: Moritz Hardt

November 24, 2015: Nati Linial

November 30, 2015: (Joint Theory Systems Seminar) Julian Shun

December 1, 2015: (Starting 4:15) Nike Sun

December 3, 2015: Gillat Kol

December 7, 2015: Mary Wooters

December 8, 2015: Li-Yang Tan

December 10, 2015: Amir Abboud

**Spring 2015**

February 3, 2015: Cancelled

February 10, 2015: Constantinos **Daskalakis** - Cancelled, MIT closed due to weather

February 17, 2015: Robert Kleinberg

February 24, 2015: Vinod Vaikuntanathan

March 3, 2015: Shayan Gharan

March 10, 2015: Moses Charikar

March 17, 2015: Mikkel Thorup

March 24, 2015: Spring Vacation

April 7, 2015: Antoine Joux

April 14, 2015: Nir Bitansky

April 21, 2015: Patriot's Day Vacation

April 23, 2015 * (special date)*: Oded Regev

April 28, 2015: Constantinos Daskalakis

May 12, 2015: Elad Hazan

May 13, 2015: Shaddin Dughmi

May 19, 2015: David Steurer

**Fall 2014**

September 2, 2014: Registration Day, No Seminar

September 9, 2014: Shubhangi Saraf

September 16, 2014: Shachar Lovett

September 23, 2014: Ronald Fagin

September 30, 2014: (in joint with LIDS) Eli Gafni

October 7, 2014: (room G882) Zeev Dvir

October 14, 2014: Alexandr Andoni

October 21, 2014: FOCS, No Seminar

October 28, 2014: Paul Beame

November 4, 2014: Seth Pettie

November 11, 2014: Holiday

November 18, 2014: Nicole Immorlica

**November 21, 2014 Cancelled (special date and time, Joint with CIS Seminar)**: Antoine Joux

December 2, 2014: Ran Raz

December 9, 2014: Madhu Sudan

**Theory of Computation Colloquium Series**

**Spring 2014**

February 11, 2014: Adam Smith

February 18, 2014: Venkatesan Guruswami

February 25, 2014: Jelani Nelson

March 4, 2014: Cynthia Rudin

March 11, 2014: Laszlo Babai

March 14, 2014: Nikhil Devanur Special date and time!

March 18, 2014: Rafael Pass

March 25, 2014: Spring Break! No seminar

April 1, 2014: No seminar

April 8, 2014: Maria Florina Balcan

April 15, 2014: Anup Rao

April 22, 2014: Patriot's Day, no seminar

April 29, 2014: Benjamin Recht

May 6, 2014: David Zuckerman

May 12, 2014: Special day and time! Toni Pitassi

May 13, 2014: Dana Moshkovitz

May 14, 2014: Special Day and time! Umesh Vazirani

__Recent__

December 10, 2013: Andrew Drucker

December 3, 2013: Mahdi Cheraghchi

November 26, 2013: Mark Braverman

November 19, 2013: Yaron Singer

November 12, 2013: Paul Valiant

November 5, 2013: Gillat Kol

November 4, 2013: Amos Korman

November 1, 2013: Aleksandr Madry

October 22, 2013: Yael Kalai

October 8, 2013: Phil Klein

October 1, 2013: Jonathan Kelner

September 24, 2013: Richard Peng

September 17, 2013: Sofya Raskhodnikova

September 10, 2013: Ankur Moitra