Theory of Computation Seminar
General Information
for Fall Semester, 2021:

Location (Hybrid):

InPerson: 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:455:00pm ET
 Mailing List: Subscribe to receive information about future talks via email.
Past TOC Seminars
2019
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
2018
Eric Price  The Sketching Complexity of Graph and Hypergraph Counting
2017
Virginia VassilevskaWilliams. Fixedparameter dynamic algorithms
2016
May 9, 2016
Heng Guo. Random Cluster Dynamics at q = 2 is Rapidly Mixing
April 25, 2016
LiYang Tan. An AverageCase Depth Hierarchy Theorem for Boolean Circuits
April 11, 2016
David Zuckerman. Explicit TwoSource Extractors and Resilient Functions
March 28, 2016
Ryan Williams. SuperLinear Gate and SuperQuadratic Wire Lower Bounds for DepthTwo and DepthThree Threshold Circuits
March 21, 2016
Mikkel Thorup. The Power of Tabulation Hashing
March 7, 2016
Dana Moshkovitz. Amplification and Derandomization Without Slowdown
February 22, 2016
Sitan Chen. Basis Collapse in Holographic Algorithms Over All Domain Sizes
February 8, 2016
Harry Lang. kMedian Clustering on Data Streams
2015
December 7, 2015
YinTat Lee. Cutting Plane Method: A Faster Algorithm for Many (Combinatorial) Optimization Problems
November 30, 2015
David Shmoys. Smarter Tools for (Citi)bikeSharing
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 HowTo 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 Degreed 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 NonUniform 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. Forall Sparse Recovery in NearOptimal Time
January 21, 2015
CS Colloquium: Cynthia Dwork. Privacy in the Land of Plenty
2014
December 15, 2014
Zeev Dvir. Private Information Retrieval with 2Servers and subpolynomial 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. Physicsinspired 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 LargeScale Datasets.
November 14, 2014
Avi Wigderson. Points, Lines and Ranks of design matrices
November 1314, 2014
Ahlfors Lectures: Avi Wigderson. Randomness/Permanent and Determinant: NonIdentical 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 NearIsometric Linear Embeddings.
October 27, 2014
Sofya Raskhodnikova. ConstantTime 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. PathFinding Methods for Linear Programming.
September 29, 2014
Applied Math Colloquium: Rachel Ward. Linear Dimensionality Reduction via Random Projections.
September 29, 2014
Eli Gafni. The CoordinatedAttack 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 SoonToBeMethod.
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 PrivacyAware Individuals.
March 11, 2014
Michael Forbes. Hitting Sets for Multilinear ReadOnce 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 ArthurMerlin 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^{12/k}) Bits.
2013
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 highdimensional 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. Firstorder algorithms for convex optimization.
October 1, 2013
SiuOn 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 MinMax Theorem with Applications in Cryptography.
March 29, 2013
Eric Blais. Approximating boolean functions with depth2 circuits.
March 15, 2013
David Xiao. Some optimal lower bounds for privacy in communication games.
March 1, 2013
Thomas Steinke. Unconditional Pseudorandom Generators for SmallSpace Computation
February 15, 2013
Justin Thaler. Practical Verified Computation with Streaming Interactive Proofs
February 1, 2013
Brendan Juba. Efficient Reasoning in PAC Semantics
2012
December 10, 2012
Grigory Yaroslavtsev. Learning and Testing Submodular Functions
December 3, 2012
Madhav Jha. Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.
November 19, 2012
Eli BenSasson. A new family of locally correctable codes based on degreelifted algebraic geometry codes
November 5, 2012
Greg Valiant. Finding Correlations, Learning Juntas, and the Closest Pair Problem
October 18, 2012
Irit Dinur. Direct Products of Proofs and Gap Amplification
October 15, 2012
Jon Ullman. Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard
October 1, 2012
Karthekeyan Chandrasekaran. A PolynomialTime Cutting Plane Algorithm for Matching
September 17, 2012
Andrew Wan. Pseudorandomness for Linear Length Branching Programs and Stack Machines
2011
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 twise independent permutations and tdesigns 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
KaiMin 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 DavenportSchinzel 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. Highrate Codes with Sublineartime 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
2010
November 19, 2010
Adam Kalai. Dueling Algorithms
October 29, 2010
David Steurer. Subexponential Algorithms for Unique Games and Related Problem
October 15, 2010
Tal Moran. On Complete Primitives for Fairness
October 1, 2010
Brendan Juba. Universal Semantic Communication
September 13, 2010
Chen Avin. Random walks techniques for (wireless) networks
June 29, 2010
Manoj Prabhakaran. Cryptographic Complexity and Computational Intractability
May 17, 2010
Raghu Meka. Pseudorandom Generators for Polynomial Threshold Functions
April 26, 2010
Jonathan Ullman. PCPs and the Hardness of Generating Private Synthetic Data
April 12, 2010
Justin Thaler. Streaming Graph Computations with a Helpful Advisor
April 5, 2010
Shubhangi Saraf. Blackbox Polynomial Identity Testing for Depth 3 Circuits
March 29, 2010
Giorgos Zervas. Information Asymmetries in PayPerBid Auctions: How Swoopo Makes Bank
February 8, 2010
Steven (Shlomo) Gortler. Characterizing the Universal Rigidity of Generic Frameworks
February 1, 2010
KaiMin Chung. Security Amplification and Parallel Repetition Theorems
2009
November 18, 2009
Sergei Vassilvitskii. A Model of Computation for MapReduce
November 4, 2009
Niv Buchbinder. The Randomized kServer Conjecture (Online Algorithms meet Linear Programming)
October 21, 2009
Varun Kanade. Potentialbased 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. MultiArmed 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 Blackbox Complexity of PAC Learning
2008
December 8, 2008
Yuri Gurevich. Proof of Church’s Thesis
December 1, 2008
Luca Trevisan. Regularity, boosting, and efficiently simulating every high entropy distribution
November 10, 2008
KaiMin Chung. Tight Bounds for Hashing Block Sources
November 3, 2008
Ran Raz. Parallel Repetition of Two Prover Games: A Survey, Application, and a Counterexample to Strong Parallel Repetition.
October 20, 2008
Tal Moran. An Optimally Fair Coin Toss: Cleve’s Bound is Tight
October 6, 2008
Amin Saberi. Game Dynamics, Equilibrium Selection and Network Structure
September 29, 2008
Flavio Chierichetti. Gossiping in Social Networks
September 15, 2008
Alan Frieze. Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
2007
May 14, 2007
Allan Borodin. Greedy algorithms and other simple greedybased algorithms for simple (to define) optimization problems
May 7, 2007
Lenore Cowen. Compact Routing from Theory to Practice
May 3, 2007
Ramin Zabih. Flowbased optimization methods in computer vision
April 30, 2007
Ueli Maurer. Indistinguishability Amplification
April 23, 2007
Phil Klein. A planargraph decomposition, and its application to TSP and Steiner Tree
April 16, 2007
Sergey Yekhanin. New Locally Decodable Codes and Private Information Retrieval Schemes
April 2, 2007
Martin Wainwright. Analysis of MAXXORSAT and its Generalizations, with Application to Distributed Compression and "Dirty Paper" Coding
March 12, 2007
Gopal Pandurangan. Efficient Distributed Approximation Algorithms for Minimum Spanning Trees
February 26, 2007
Shanghua Teng. Game and Market Equilibria
February 12, 2007Ankit Patel. The Theory of Desynchronization: SelfOrganizing Algorithms for Periodic Resource Scheduling
February 5, 2007
Salil Vadhan. Unbalanced Expanders and Randomness Extractors from ParvareshVardy Codes