MIT Theory of Computation COLLOQUIUM ARCHIVE 2013-2020
Fall 2020
- 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
Spring 2020
- 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 — (Video of talk)
- October 2, 2018: Suresh Venkatasubramanian: Towards a theory (or theories) of fairness in automated decision-making — (Video of talk)
- October 9, 2018: Columbus Day Holiday
- October 16, 2018: No Seminar
- October 23, 2018: Urmila Mahadev: Classical Verification of Quantam Computation — (Video of talk)
- October 30, 2018: No Seminar (STOC Deadline)
- November 6, 2018: Vijay Vazirani: Planar Graph Perfect Matching is in NC — (Video of talk)
- November 13, 2018: Aaron Sidford: Perron-Frobenius Theory in Nearly Linear Time
- November 20, 2018: Scott Aaronson: Gentle Measurement of Quantum States and Differential Privacy — (Video of talk)
- November 27, 2018: Avishay Tal: Oracle Seperation of BQP and the Polynomial Hierarchy — (Video of talk)
- December 4, 2018: Michael Saks: Approximating the edit distance to within a constant factor in truly subquadratic time — (Video of talk)
- December 11, 2018: Dean Doron: Probabilistic logspace algorithms for Laplacian solvers — (Video of talk, begins at 37:16)
Spring 2018
- 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:
- March 20, 2018: Ohad Shamir (Weizmann and Microsoft Research) PLEASE NOTE LOCATION CHANGE TO 32-155: Is Depth Needed for Deep Learning? Circuit Complexity in Neural Networks
- 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:
Fall 2017
- 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
Spring 2017
- 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 7, 2017: Nikhil Bansal: A fast polynomial space algorithm for Subset Sum
- March 14, 2017: Irit Dinur: Grassmann agreement testing and the 2:1 conjecture
- March 21, 2017: Moni Naor: White-box vs Black-box Search Problems: A Cryptographic Perspective
- March 28, 2017: MIT Spring Break
- April 11, 2017: Virginia Vassilevska Williams: Fast distance product of bounded difference matrices with applications to Language Edit Distance and RNA-Folding
- 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 2, 2017: Yuval Peres: Trace reconstruction for the deletion channel
- May 16, 2017: Ilias Diakonikolas: TBD
Fall 2016
- September 13, 2016: Boaz Barak: Computational Bayesianism, Sums of Squares, and Unicorns — (Video)
- September 19, 2016: (Special Day - Monday) Alina Ene: From Minimum Cut to Submodular minimization: Leveraging the Decomposable Structure
- 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 — (Video)
- 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
- December 6, 2016: Gil Cohen: Recent Advances in Randomness Extractors and Their Applications
- December 13, 2016: Ola Svensson: Small Extended Formulations via Monotone Circuits of Small Depth
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
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 (Fall 2013 and earlier)
- 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
- Archive 2000-2013