## 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.

## Calendar

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