Theory of Computation Seminar

General Information

Location: Pierce 213 (Brooks Room). Time: Mondays, 1-2:30
Mailing List: Click here to receive information about future talks via email.

If you are interested in giving a talk, please contact Thomas or Jelani.


Monday, August 31, 2015. Madhu Sudan. Communication Amid Uncertainty

Monday, September 21, 2015. Ryan O'Donnell.

Monday, October 5, 2015. Phil Klein.

Monday, October 26, 2015. Elad Hazan.

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

Monday, November 23, 2015. Yin Tat Lee.

Monday, November 30, 2015. David Shmoys.

Monday, December 7, 2015. Boaz Barak.

Other Seminars of Interest

CRCS Lunch Seminar
Harvard CS Colloquium
Harvard EconCS Seminar
Harvard Math Seminar
Microsoft Research Colloquium
MIT Algorithms & Complexity Seminar
MIT Crypto & Information Security Seminar
MIT Theory of Computation Colloquium
MSR/MIT Theory Reading Group

Previous Talks

Monday, May 11, 2015. Anupam Gupta. The Independent Set problem on Degree-d Graphs
Monday, May 4, 2015. Shay Solomon. Dynamic Maximum Matching and Related Problems
Monday, April 27, 2015. Hammurabi Mendes. Multidimensional $\epsilon$-Approximate Agreement and Computability in Byzantine Systems
Monday, April 13, 2015. Chandra Chekhuri. Recent progress in structure of large treewidth graphs and some applications
Monday, March 30, 2015. Bobby Kleinberg. Secretary Problems with Non-Uniform Arrival Order
Monday, March 9, 2015. Marco Gaboardi. Relational verification of Differential Privacy and Mechanism Design...for a theory audience
Monday, March 2, 2015. Tsvi Kopelowitz. Higher lower bounds from the 3SUM conjecture
Monday, February 2, 2015. CS Colloquium: Omer Reingold. Randomness vs. Memory: A Treasure(s) Hunt
Monday, January 26, 2015. Yi Li. For-all Sparse Recovery in Near-Optimal Time
Wednesday, January 21, 2015. CS Colloquium: Cynthia Dwork. Privacy in the Land of Plenty

Monday, December 15, 2014. Zeev Dvir. Private Information Retrieval with 2-Servers and sub-polynomial communication
Monday, December 8, 2014. Omri Weinstein. Approximating the Best Nash Equilibrium in n^{o(log n)}-Time Breaks ETH.
Monday, December 1, 2014. CS Colloquium: Boaz Barak. Proofs for Algorithms, Algorithms from Proofs.
Monday, December 1, 2014. Seth Pettie. Randomized Symmetry Breaking and the Constructive Lovász Local Lemma
Monday, November 24, 2014. Jan Vondrak. Fast algorithms for optimization of submodular functions
Thursday, November 20, 2014. CS Colloquium: Christopher Moore. Physics-inspired Algorithms and Phase Transitions in Community Detection.
Monday, November 17, 2014. CS Colloquium: Yael Tauman Kalai. Delegating Computation.
Monday, November 17, 2014. Gillat Kol. Exponential Separation of Information and Communication.
Monday, November 17, 2014. CRCS Lunch Seminar: Babis Tsourakakis. Algorithm Design for Large-Scale Datasets.
Friday, November 14, 2014. Avi Wigderson. Points, Lines and Ranks of design matrices
Th/Fri, November 13-14, 2014. Ahlfors Lectures: Avi Wigderson. Randomness/Permanent and Determinant: Non-Identical Twins
Monday, November 10, 2014. CS Colloquium: Madhu Sudan. Communication Amid Uncertainty.
Monday, November 10, 2014. Chris Musco. Graph Sparsification in the Streaming Model.
Thursday, November 6, 2014. CS Colloquium: Michael Kearns. Games, Networks, and People.
Monday, November 3, 2014. Pranjal Awasthi. Learning Halfspaces with Noise.
Thursday, October 30, 2014. CS Colloquium: Richard Baraniuk. Learning Near-Isometric Linear Embeddings.
Monday, October 27, 2014. Sofya Raskhodnikova. Constant-Time Testing and Learning Algorithms for Image Properties.
Friday, October 24, 2014. EconCS Seminar: Rafael Frongillo. Risk Dynamics in Trade Networks.
Thursday, October 16, 2014. CS Colloquium: Ankur Moitra. New Algorithms for Nonnegative Matrix Factorization and Beyond.
Thursday, October 9, 2014. CS Colloquium: Ron Fagin. Applying Theory to Practice (and Practice to Theory).
Wednesday, October 8, 2014. CMSA Colloquium: Salil Vadhan. The Computational Complexity of Data Privacy.
Monday, October 6, 2014. Aaron Sidford. Path-Finding Methods for Linear Programming.
Monday, September 29, 2014. Applied Math Colloquium: Rachel Ward. Linear Dimensionality Reduction via Random Projections.
Monday, September 29, 2014. Eli Gafni. The Coordinated-Attack Problem Revisited.
Monday, September 29, 2014. CRCS Lunch Seminar: Or Sheffet. Utilitarian Models of Privacy Loss and Social Choice.
Monday, September 22, 2014. Emanuele Viola. Local Reductions.
Monday, September 15, 2014. CRCS Lunch Seminar: Itai Ishlagi. Unbalanced Matching Markets.
Friday, September 12, 2014. EconCS Seminar: Moshe Babaioff. Bertrand Networks.

Friday, 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.
Tuesday, April 8, 2014. Raef Bassily. Causal Erasure Channels.
Thursday, April 3, 2014. CS Colloquium: David Soloveichik. Engineering Intelligent Molecular Systems.
Tuesday, March 25, 2014. Aleksandar Nikolov. Approximating Hereditary Discrepancy via Small Width Ellipsoids.
Monday, March 24, 2014. CRCS Lunch Seminar: David Xiao. Understanding Incentives for Privacy-Aware Individuals.
Tuesday, March 11, 2014. Michael Forbes. Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order.
Thursday, February 27, 2014. CS Colloquium: Raluca Ada Popa. Building Systems that Compute on Encrypted Data.
Tuesday, February 25, 2014. Mark Zhandry. Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation.
Friday, February 14, 2014. EconCS Seminar: Pavel Hubacek. Single Round Delegation with Sublinear Verification.
Tuesday, February 11, 2014. Justin Thaler. On Interactivity in Arthur-Merlin Communication and Stream Computation.
Wednesday, January 29, 2014. CRCS Lunch Seminar: Jon Ullman. Privacy and the Complexity of Simple Queries.
Tuesday, January 28, 2014. Vladimir Braverman. Approximating Large Frequency Moments with O(n^{1-2/k}) Bits.
Tuesday, December 3, 2013. Aravindan Vijayaraghavan. Smoothed analysis and uniqueness of tensor decompositions.
Thursday, November 21, 2013. CS Colloquium: Tim Roughgarden. Beyond the worst case in auctions, graph partitioning, and social networks.
Wednesday, November 20, 2013. CRCS Lunch Seminar: Scott Kominers. Theory, practice, and engineering in (generalized) matching market design.
Tuesday, November 19, 2013. Ying Xiao. Fourier Principal Component Analysis.
Tuesday, November 12, 2013. Grigory Yaroslavtsev. Testing properties under Lp distances.
Tuesday, November 5, 2013. Adam Smith. Privacy, stability and high-dimensional sparse regression.
Thursday, October 31, 2013. CS Colloquium: Aleksander Madry. (Electrical) Flows and graph algorithms.
Tuesday, October 15, 2013. Yaron Singer. Adaptive seeding in social networks.
Thursday, October 10, 2013. CS Colloquium: Christos Papadimitriou. Computational insights and the theory of evolution.
Monday, October 7, 2013. Huy Nguyen. Approximate near neighbor search: Beyond locality sensitive hashing.
Thursday, October 3, 2013. CS Colloquium: Garud Iyengar. First-order algorithms for convex optimization.
Tuesday, October 1, 2013. Siu-On Chan. Approximate constraint satisfaction requires large LP relaxations.
Thursday, September 26, 2013. CS Colloquium: Craig Gentry. A cryptographic approach to software obfuscation.
Tuesday, September 17, 2013. Jelani Nelson. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings.

Friday, May 17, 2013. Daniel Reichman. Contagious Sets in Expanders.
Friday, May 10, 2013. Udi Wieder. How to approximate a set without knowing its size in advance.
Friday, April 26, 2013. Lorenzo Orecchia. From Online Learning to Optimization and Back: the Power of Regularization.
Friday, April 12, 2013. Colin Jia Zheng. A Uniform Min-Max Theorem with Applications in Cryptography.
Friday, March 29, 2013. Eric Blais. Approximating boolean functions with depth-2 circuits.
Friday, March 15, 2013. David Xiao. Some optimal lower bounds for privacy in communication games.
Friday, March 1, 2013. Thomas Steinke. Unconditional Pseudorandom Generators for Small-Space Computation
Friday, February 15, 2013. Justin Thaler. Practical Verified Computation with Streaming Interactive Proofs
Friday, February 1, 2013. Brendan Juba. Efficient Reasoning in PAC Semantics

Monday, December 10, 2012. Grigory Yaroslavtsev. Learning and Testing Submodular Functions
Monday, December 3, 2012. Madhav Jha. Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.
Monday, November 19, 2012. Eli Ben-Sasson. A new family of locally correctable codes based on degree-lifted algebraic geometry codes
Monday, November 5, 2012. Greg Valiant. Finding Correlations, Learning Juntas, and the Closest Pair Problem
Thursday, October 18, 2012. Irit Dinur. Direct Products of Proofs and Gap Amplification
Monday, October 15, 2012. Jon Ullman. Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard
Monday, October 1, 2012. Karthekeyan Chandrasekaran. A Polynomial-Time Cutting Plane Algorithm for Matching
Monday, September 17, 2012. Andrew Wan. Pseudorandomness for Linear Length Branching Programs and Stack Machines

Thursday, November 10, 2011. Vitaly Feldman. Bounds on complexity of SQ learning and
Friday, October 7, 2011. Varun Kanade. Evolution with Recombination
Wednesday, September 14, 2011. Shachar Lovett. Existence of small families of t-wise independent permutations and t-designs via local limit theorems

Friday, May 13, 2011. Dana Moshkovitz. Hardness of Approximately Solving Linear Equations over Reals
Thursday, May 5, 2011. Virginia Vassilevska Williams. Path, Matrix, and Triangle Problems: Algorithms and Equivalences
Friday, April 29, 2011. Graham Cormode. Distributed Summaries
Friday, April 22, 2011. Kai-Min Chung. Memory Delegation
Monday, April 11, 2011. Mayank Varia. Studies in Program Obfuscation
Friday, March 11, 2011. Yevgeniy Dodis. Leftover Hash Lemma, Revisited
Friday, February 25, 2011. Seth Pettie. Everything you always wanted to know about Davenport-Schinzel sequences, but were afraid to ask
Thursday, February 17, 2011. David Steurer. On the Complexity of Graph Expansion and the Unique Games Conjecture
Monday, February 14, 2011. Ryan Williams. Algorithms, Obstructions, and Beating Exhaustive Search
Thursday, February 10, 2011. Shubhangi Saraf. High-rate Codes with Sublinear-time Decoding
Thursday, February 3, 2011. Jelani Nelson. Sketching and Streaming Algorithms
Monday, January 31, 2011. Mark Braverman Information and interactive communication
Friday, January 28, 2011. Martin Suchara. BGP Safety with Spurious Updates - The Conditions of BGP Convergence

Friday, November 19, 2010. Adam Kalai. Dueling Algorithms
Friday, October 29, 2010. David Steurer. Subexponential Algorithms for Unique Games and Related Problems
Friday, October 15, 2010. Tal Moran. On Complete Primitives for Fairness
Friday, October 1, 2010. Brendan Juba. Universal Semantic Communication
Monday, September 13, 2010. Chen Avin. Random walks techniques for (wireless) networks

Tuesday, June 29, 2010. Manoj Prabhakaran. Cryptographic Complexity and Computational Intractability
Monday, May 17, 2010. Raghu Meka. Pseudorandom Generators for Polynomial Threshold Functions
Monday, April 26, 2010. Jonathan Ullman. PCPs and the Hardness of Generating Private Synthetic Data
Monday, April 12, 2010. Justin Thaler. Streaming Graph Computations with a Helpful Advisor
Monday, April 5, 2010. Shubhangi Saraf. Blackbox Polynomial Identity Testing for Depth 3 Circuits
Monday, March 29, 2010. Giorgos Zervas. Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank
Monday, February 8, 2010. Steven (Shlomo) Gortler. Characterizing the Universal Rigidity of Generic Frameworks
Monday, February 1, 2010. Kai-Min Chung. Security Amplification and Parallel Repetition Theorems

Wednesday, November 18, 2009. Sergei Vassilvitskii. A Model of Computation for MapReduce
Wednesday, November 4, 2009. Niv Buchbinder. The Randomized k-Server Conjecture (Online Algorithms meet Linear Programming)
Wednesday, October 21, 2009. Varun Kanade. Potential-based agnostic boosting
Friday, October 9, 2009. Harvey M. Friedman. Decision Procedures for Verification
Wednesday, September 23, 2009. Justin Thaler. Graph Covers and Quadratic Minimization

Thursday, April 30, 2009. Jennifer Chayes. IIC/CS colloquium
Wednesday, April 29, 2009. Guy Rothblum. On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results (CRCS Privacy and Security Lunch Seminar)
Monday, April 20, 2009. Alex Samorodnitsky. Counting Magic Squares
Wednesday, April 15, 2009. Katrina Ligett. Differentially private approximation algorithms
Monday, April 6, 2009. Alex Slivkins. Multi-Armed Bandits in Metric Space
Monday, March 30, 2009. David Choi. Sample Complexity Bounds for Link Prediction
Wednesday, March 11, 2009. Ketan Mulmuley. On P vs NP, Geometric Complexity, and the Riemann Hypothesis
Thursday, February 26, 2009. Muthu Muthukrishnan. See the departmental colloquium series
Monday, February 23, 2009. Zhenming Liu. Designing Floating Codes for Expected Performance
Friday, February 20, 2009. David Xiao. On the Black-box Complexity of PAC Learning

Monday, December 8, 2008. Yuri Gurevich. Proof of Church’s Thesis
Monday, December 1, 2008. Luca Trevisan. Regularity, boosting, and efficiently simulating every high entropy distribution
Monday, November 10, 2008. Kai-Min Chung. Tight Bounds for Hashing Block Sources
Monday, November 3, 2008. Ran Raz. Parallel Repetition of Two Prover Games: A Survey, Application, and a Counterexample to Strong Parallel Repetition.
Monday, October 20, 2008. Tal Moran. An Optimally Fair Coin Toss: Cleve’s Bound is Tight
Monday, October 6, 2008. Amin Saberi. Game Dynamics, Equilibrium Selection and Network Structure
Monday, September 29, 2008. Flavio Chierichetti. Gossiping in Social Networks
Monday, September 15, 2008. Alan Frieze. Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time

Monday, May 14, 2007. Allan Borodin. Greedy algorithms and other simple greedy-based algorithms for simple (to define) optimization problems
Monday, May 7, 2007. Lenore Cowen. Compact Routing from Theory to Practice
Thursday, May 3, 2007. Ramin Zabih. Flow-based optimization methods in computer vision
Monday, April 30, 2007. Ueli Maurer. Indistinguishability Amplification
Monday, April 23, 2007. Phil Klein. A planar-graph decomposition, and its application to TSP and Steiner Tree
Monday, April 16, 2007. Sergey Yekhanin. New Locally Decodable Codes and Private Information Retrieval Schemes
Monday, April 2, 2007. Martin Wainwright. Analysis of MAX-XORSAT and its Generalizations, with Application to Distributed Compression and "Dirty Paper" Coding
Monday, March 12, 2007. Gopal Pandurangan. Efficient Distributed Approximation Algorithms for Minimum Spanning Trees
Monday, February 26, 2007. Shanghua Teng. Game and Market Equilibria
Monday, February 12, 2007. Ankit Patel. The Theory of Desynchronization: Self-Organizing Algorithms for Periodic Resource Scheduling
Monday, February 5, 2007. Salil Vadhan. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes

Fall '06
Spring '06
Fall '05