Theory of Computation Seminar

General Information

for Fall Semester, 2021:

  • Location (Hybrid): 
    • In-Person: Science and Engineering Complex (SEC) 2.118, 150 Western Avenue, Allston, MA 02134
    • Zoom: Please see Theory Seminar Google Calendar for Zoom links/ Zoom information
  • Time: Wednesdays, roughly biweekly, 3:45-5:00pm ET
  • Mailing List: Subscribe to receive information about future talks via email.
If you are interested in giving a talk, please contact Sumegha Garg at

Past TOC Seminars


May 6, 2019
Ran Raz - 

April 22, 2019
Santosh Vempala - 

April 8, 2019
Sam Hopkins - 

March 25, 2019
Yury Makarychev - 

March 11, 2019
Jiapeng Zhang- 

March 4, 2019
Ketan Mulmuley - 

February 25, 2019
Rasmus Kyng - A numerical analysis approach to convex optimization

February 11, 2019
Sanjeev Khanna - Sublinear Algorithms for (Delta +1)-Coloring

January 28, 2019
Christos Tzamos - Learning Geometric Concepts from Positive Examples


December 10, 2018
Eric Price - The Sketching Complexity of Graph and Hypergraph Counting
November 26, 2018
Ilias Diakonikolas - Algorithmic Questions in High-Dimensional Robust Statistics
November 12, 2018
Natesh Pillai - Mixing times of Kac’s random walk and other related Markov chains
November 5, 2018
Aaron Roth - How to Use Heuristics for Differential Privacy
October 15, 2018
Nutan Limaye - A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
October 1, 2018
Alexander Golovnev - Linear Data Structures and Rigidity
September 24, 2018
Nima Anari - Log-Concave Polynomials: Combinatorics, Counting, and Optimization
September 10, 2018
Ilya Razenshteyn - Holder Homeomorphisms and Approximate Nearest Neighbors
May 14, 2018
May 7, 2018
April 16, 2018
April 2, 2018
March 26, 2018
February 26, 2018
February 12, 2018
January 29, 2018


November 27, 2017
November 20, 2017
November 6, 2017
October 23, 2017
September 25, 2017
September 11, 2017
Noah Stephens-Davidowitz - On the Quantitative Hardness of CVP
May 8, 2017
May 1, 2017
April 17, 2017
April 10, 2017
Ben Rossman - University of Toronto
March 20, 2017
February 27, 2017
February 13, 2017
January 30, 2017
Virginia Vassilevska-Williams. Fixed-parameter dynamic algorithms



December 7, 2015
Yin-Tat Lee. Cutting Plane Method: A Faster Algorithm for Many (Combinatorial) Optimization Problems

November 30, 2015
David Shmoys. Smarter Tools for (Citi)bike-Sharing

November 23, 2015
Boaz Barak. Sum of Squares Lower Bounds for Planted Clique

November 9, 2015
Sasha Razborov. On the $AC^0$ Complexity of Subgraph Isomorphism

October 26, 2015
Elad Hazan. Is Optimization Computationally Equivalent to Online Learning?

October 5, 2015
Philip Klein. Approximation Schemes for Planar Graphs: A How-To Guide

September 21, 2015
Ryan O'Donnell. How to Refute a Random CSP

August 31, 2015
Madhu Sudan. Communication Amid Uncertainty

May 11, 2015
Anupam Gupta. The Independent Set problem on Degree-d Graphs

May 4, 2015
Shay Solomon. Dynamic Maximum Matching and Related Problems

April 27, 2015
Hammurabi Mendes. Multidimensional $\epsilon$-Approximate Agreement and Computability in Byzantine Systems 

April 13, 2015
Chandra Chekhuri. Recent progress in structure of large treewidth graphs and some applications

March 30, 2015
Bobby Kleinberg. Secretary Problems with Non-Uniform Arrival Order

March 9, 2015
Marco Gaboardi. Relational verification of Differential Privacy and Mechanism Design...for a theory audience

March 2, 2015
Tsvi Kopelowitz. Higher lower bounds from the 3SUM conjecture

February 2, 2015
CS Colloquium: Omer Reingold. Randomness vs. Memory: A Treasure(s) Hunt

January 26, 2015
Yi Li. For-all Sparse Recovery in Near-Optimal Time

January 21, 2015
CS Colloquium: Cynthia Dwork. Privacy in the Land of Plenty


December 15, 2014
Zeev Dvir. Private Information Retrieval with 2-Servers and sub-polynomial communication

December 8, 2014
Omri Weinstein. Approximating the Best Nash Equilibrium in n^{o(log n)}-Time Breaks ETH.

December 1, 2014
CS Colloquium: Boaz Barak. Proofs for Algorithms, Algorithms from Proofs.

December 1, 2014
Seth Pettie. Randomized Symmetry Breaking and the Constructive Lovász Local Lemma

November 24, 2014
Jan Vondrak. Fast algorithms for optimization of submodular functions

November 20, 2014
CS Colloquium: Christopher Moore. Physics-inspired Algorithms and Phase Transitions in Community Detection.

November 17, 2014
CS Colloquium: Yael Tauman Kalai. Delegating Computation.

November 17, 2014
Gillat Kol. Exponential Separation of Information and Communication.

November 17, 2014
CRCS Lunch Seminar: Babis Tsourakakis. Algorithm Design for Large-Scale Datasets.

November 14, 2014
Avi Wigderson. Points, Lines and Ranks of design matrices

November 13-14, 2014
Ahlfors Lectures: Avi Wigderson. Randomness/Permanent and Determinant: Non-Identical Twins

November 10, 2014
CS Colloquium: Madhu Sudan. Communication Amid Uncertainty.

November 10, 2014
Chris Musco. Graph Sparsification in the Streaming Model.

November 6, 2014
CS Colloquium: Michael Kearns. Games, Networks, and People.

November 3, 2014
Pranjal Awasthi. Learning Halfspaces with Noise.

October 30, 2014
CS Colloquium: Richard Baraniuk. Learning Near-Isometric Linear Embeddings.

October 27, 2014
Sofya Raskhodnikova. Constant-Time Testing and Learning Algorithms for Image Properties.

October 24, 2014
EconCS Seminar: Rafael Frongillo. Risk Dynamics in Trade Networks.

October 16, 2014
CS Colloquium: Ankur Moitra. New Algorithms for Nonnegative Matrix Factorization and Beyond.

October 9, 2014
CS Colloquium: Ron Fagin. Applying Theory to Practice (and Practice to Theory).

October 8, 2014
CMSA Colloquium: Salil Vadhan. The Computational Complexity of Data Privacy.

October 6, 2014
Aaron Sidford. Path-Finding Methods for Linear Programming.

September 29, 2014
Applied Math Colloquium: Rachel Ward. Linear Dimensionality Reduction via Random Projections.

September 29, 2014
Eli Gafni. The Coordinated-Attack Problem Revisited.

September 29, 2014
CRCS Lunch Seminar: Or Sheffet. Utilitarian Models of Privacy Loss and Social Choice.

September 22, 2014
Emanuele Viola. Local Reductions.

September 15, 2014
CRCS Lunch Seminar: Itai Ishlagi. Unbalanced Matching Markets.

September 12, 2014
EconCS Seminar: Moshe Babaioff. Bertrand Networks.

May 16, 2014
Sjoerd Dirksen. A Unified Approach to Dimensionality Reduction with Subgaussian Matrices. 

Tuesday, May 6, 2014
Venkat Guruswami. Polar codes: Reliable communication with complexity scaling polynomially in the gap to Shannon capacity. 

Tuesday, April 22, 2014
Or Sheffet. The Entropy Soon-To-Be-Method. 

April 8, 2014
Raef Bassily. Causal Erasure Channels. 

April 3, 2014
CS Colloquium: David Soloveichik. Engineering Intelligent Molecular Systems.

March 25, 2014
Aleksandar Nikolov. Approximating Hereditary Discrepancy via Small Width Ellipsoids.

March 24, 2014
CRCS Lunch Seminar: David Xiao. Understanding Incentives for Privacy-Aware Individuals.

March 11, 2014
Michael Forbes. Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order.

February 27, 2014
CS Colloquium: Raluca Ada Popa. Building Systems that Compute on Encrypted Data.

February 25, 2014
Mark Zhandry. Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation.

February 14, 2014
EconCS Seminar: Pavel Hubacek. Single Round Delegation with Sublinear Verification.

February 11, 2014
Justin Thaler. On Interactivity in Arthur-Merlin Communication and Stream Computation.

January 29, 2014
CRCS Lunch Seminar: Jon Ullman. Privacy and the Complexity of Simple Queries.

January 28, 2014
Vladimir Braverman. Approximating Large Frequency Moments with O(n^{1-2/k}) Bits.


December 3, 2013
Aravindan Vijayaraghavan. Smoothed analysis and uniqueness of tensor decompositions.

November 21, 2013
CS Colloquium: Tim Roughgarden. Beyond the worst case in auctions, graph partitioning, and social networks.

November 20, 2013
CRCS Lunch Seminar: Scott Kominers. Theory, practice, and engineering in (generalized) matching market design.

November 19, 2013
Ying Xiao. Fourier Principal Component Analysis.

November 12, 2013
Grigory Yaroslavtsev. Testing properties under Lp distances.

November 5, 2013
Adam Smith. Privacy, stability and high-dimensional sparse regression.

October 31, 2013
CS Colloquium: Aleksander Madry. (Electrical) Flows and graph algorithms.

October 15, 2013
Yaron Singer. Adaptive seeding in social networks.

October 10, 2013
CS Colloquium: Christos Papadimitriou. Computational insights and the theory of evolution.

October 7, 2013
Huy Nguyen. Approximate near neighbor search: Beyond locality sensitive hashing.

October 3, 2013
CS Colloquium: Garud Iyengar. First-order algorithms for convex optimization.

October 1, 2013
Siu-On Chan. Approximate constraint satisfaction requires large LP relaxations.

September 26, 2013
CS Colloquium: Craig Gentry. A cryptographic approach to software obfuscation.

September 17, 2013
Jelani Nelson. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings.

May 17, 2013
Daniel Reichman. Contagious Sets in Expanders. 

May 10, 2013
Udi Wieder. How to approximate a set without knowing its size in advance.

April 26, 2013
Lorenzo Orecchia. From Online Learning to Optimization and Back: the Power of Regularization.

April 12, 2013
Colin Jia Zheng. A Uniform Min-Max Theorem with Applications in Cryptography.

March 29, 2013
Eric Blais. Approximating boolean functions with depth-2 circuits.

March 15, 2013
David Xiao. Some optimal lower bounds for privacy in communication games.

March 1, 2013
Thomas Steinke. Unconditional Pseudorandom Generators for Small-Space Computation

February 15, 2013
Justin Thaler. Practical Verified Computation with Streaming Interactive Proofs

February 1, 2013
Brendan Juba. Efficient Reasoning in PAC Semantics



November 10, 2011
Vitaly Feldman. Bounds on complexity of SQ learning and 

October 7, 2011
Varun Kanade. Evolution with Recombination

September 14, 2011
Shachar Lovett. Existence of small families of t-wise independent permutations and t-designs via local limit theorems

May 13, 2011
Dana Moshkovitz. Hardness of Approximately Solving Linear Equations over Reals

May 5, 2011
Virginia Vassilevska Williams. Path, Matrix, and Triangle Problems: Algorithms and Equivalences

April 29, 2011
Graham Cormode. Distributed Summaries

April 22, 2011
Kai-Min Chung. Memory Delegation

April 11, 2011
Mayank Varia. Studies in Program Obfuscation

March 11, 2011
Yevgeniy Dodis. Leftover Hash Lemma, Revisited

February 25, 2011
Seth Pettie. Everything you always wanted to know about Davenport-Schinzel sequences, but were afraid to ask

February 17, 2011
David Steurer. On the Complexity of Graph Expansion and the Unique Games Conjecture

February 14, 2011
Ryan Williams. Algorithms, Obstructions, and Beating Exhaustive Search

February 10, 2011
Shubhangi Saraf. High-rate Codes with Sublinear-time Decoding

February 3, 2011
Jelani Nelson. Sketching and Streaming Algorithms

January 31, 2011
Mark Braverman Information and interactive communication

January 28, 2011
Martin Suchara. BGP Safety with Spurious Updates - The Conditions of BGP Convergence



November 18, 2009
Sergei Vassilvitskii. A Model of Computation for MapReduce

November 4, 2009
Niv Buchbinder. The Randomized k-Server Conjecture (Online Algorithms meet Linear Programming)

October 21, 2009
Varun Kanade. Potential-based agnostic boosting

October 9, 2009
Harvey M. Friedman. Decision Procedures for Verification

September 23, 2009
Justin Thaler. Graph Covers and Quadratic Minimization

April 30, 2009
Jennifer Chayes. IIC/CS colloquium

April 29, 2009.
Guy Rothblum. On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results (CRCS Privacy and Security Lunch Seminar)

April 20, 2009
Alex Samorodnitsky. Counting Magic Squares

April 15, 2009
Katrina Ligett. Differentially private approximation algorithms

April 6, 2009
Alex Slivkins. Multi-Armed Bandits in Metric Space

March 30, 2009
David Choi. Sample Complexity Bounds for Link Prediction

March 11, 2009
Ketan Mulmuley. On P vs NP, Geometric Complexity, and the Riemann Hypothesis

February 26, 2009
Muthu Muthukrishnan. See the departmental colloquium series

February 23, 2009
Zhenming Liu. Designing Floating Codes for Expected Performance

February 20, 2009
David Xiao. On the Black-box Complexity of PAC Learning