Theory of Computation Colloquium

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
  Joanne Hanley at: joanne (at) csail.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.
 
 
Spring 2024
 
 
 
 
 
April 16, 2024: Anand Natarajan
 
April 23, 2024: Yang Liu
 
May 7, 2024: Mohsen Ghaffari, "Parallel Derandomization for Chernoff-like Concentrations"
 
May 14, 2024: Thatchaphol Saranurak
 
Fall 2023

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 Bullshit Detectors(or Polynomial Time Byzantine Agreement with Optimal Resilience)

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
 
 
 
 
November 3, 2020:  Election Day (Remember to Vote)
 
 
 
November 24, 2020:  Thanksgiving Week
 
 
 
 
 
Spring 2020
 
February 4, 2020:
 
February 11,2020:
 
 
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

 
 
                                  (Video of talk)
 
 
October 9, 2018:  Columbus Day Holiday
 
October 16, 2018: No Seminar
 
                            (Video of talk)
 
October 30, 2018: No Seminar (STOC Deadline)
 
                             (Video of talk)
 
 
                               (Video of talk)
 
                               (Video of talk)
 
                              (Video of talk)
 
                                (Video of talk, begins at 37:16)
 
 
Spring 2018
 
 
 
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: 
 
 
Fall 2017
 
 
 
 
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
 
 
 
 
 
 
Spring 2017
 
 
 
 
February 22, 2017 (Please note this seminar is on Wednesday): Aaron Roth: Quantifying Tradeoffs Between Fairness and Accuracy in Online Learning
 
 
 
 
 
March 28, 2017:  MIT Spring Break
 
 
April 19, 2017: (Please note this seminar is on Wednesday): Andrea Montanari:  The landscape of some statistical problems
 
 
 
May 16, 2017: Ilias Diakonikolas: TBD
 
 
Fall 2016
 
 
                                                     (to view this talk click here)
 
 
 
October 3, 2016: (Special Day - Monday)  Alexandr Andoni: Optimal Hashing for High-Dimensional Spaces
 
October 11, 2016:  MIT Holiday - Columbus Vacation
 
                                                       (to view this talk click here)
 
 
 
 
 
November 22, 2016:  Nisheeth Vishnoi:
 
 
 
 
 

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, 2015Shaddin 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, 2013Gillat 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