Theory of Computation Colloquium
Theory of Computation Colloquium Series
Seminar series coordinated by Kuikui Liu and Sam Hopkins.
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 17, 2024: Chara Podimata, "Learning in Strategic Environments: from Calibrated Agents to General Information Asymmetry"
September 24, 2024: Kai Zhe Zheng
October 08, 2024: Thodoris Lykouris
November 19, 2024: Ronitt Rubinfeld
December 10, 2024: Ryan O'Donnell
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:
Fall 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
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