# Theory of Computation Seminar ## Past TOC Seminars Open all sections Close all sections ### 2019 expand\_more 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 expand\_more 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 Bill Fefferman - ["Quantum Supremacy" and the Complexity of Random Circuit Sampling](/toc-seminar-17-18/#bfucb) May 7, 2018 Matteo Riondato - [Sampling-based Approximation Algorithms for Data Analysis using Rademacher Averages](/toc-seminar-17-18/#mrts) April 16, 2018 Alina Ene - [Towards faster and optimal algorithms for submodular maximization](/toc-seminar-17-18/#aebu) April 2, 2018 Gil Cohen - [Hitting Sets with Near-Optimal Error for Read-Once Branching Programs](/toc-seminar-17-18/#gcpu) March 26, 2018 Jeremy Fineman - [Nearly Work-Efficient Parallel Algorithm for Digraph Reachability](/toc-seminar-17-18/#jfgu) February 26, 2018 Greg Bodwin - [The Distance Oracle Hierarchy](/toc-seminar-17-18/#gbmit) February 12, 2018 Ola Svensson - [A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem](/toc-seminar-17-18/#osepfl) January 29, 2018 Sebastien Bubeck - [k-server and metrical task systems via multiscale entropic regularization](/toc-seminar-17-18/#sbmsr) ### 2017 expand\_more November 27, 2017 Kasper Green Larsen - [Constructive Discrepancy Minimization with Hereditary L2 Guarantees](/toc-seminar-17-18/#klau) November 20, 2017 Moses Charikar - [Hashing-based-Estimators for Kernel Density in High Dimensions](/toc-seminar-17-18/#mcsu) November 6, 2017 Dmitriy Zhuk - [A proof of CSP Dichotomy conjecture](/toc-seminar-17-18/#dzmsu) October 23, 2017 Rocco Servedio - [Learning Sums of Independent Commonly Supported Integer Random Variables (SICSIRVs)](/toc-seminar-17-18/#rscu) September 25, 2017 Uri Stemmer - [Practical Locally Private Heavy Hitters](/toc-seminar-17-18/#ushu) September 11, 2017 Noah Stephens-Davidowitz - [On the Quantitative Hardness of CVP](/toc-seminar-17-18/#nsdpu) May 8, 2017 Kunal Talwar - [Two approaches to (Deep) Learning with Differential Privacy](/toc-seminar-16-17#ktgr) May 1, 2017 Shubhangi Saraf - [Incidence geometry, rank bounds for design matrices, and applications](/toc-seminar-16-17#ssru) April 17, 2017 Swastik Kopparty - [Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound](/toc-seminar-16-17#skru) April 10, 2017 Ben Rossman - [University of Toronto](/toc-seminar-16-17#brut) March 20, 2017 Ilias Diakonikolas. [Computational Efficiency and Robust Statistics](/toc-seminar-16-17#idusc) February 27, 2017 Thomas Rothvoss. [A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies](/toc-seminar-16-17#truw) February 13, 2017 Vitaly Feldman. [Lower bounds against convex relaxations via the statistical query complexity](/toc-seminar-16-17#VFIBMR) January 30, 2017 Virginia Vassilevska-Williams. [Fixed-parameter dynamic algorithms](/toc-seminar-16-17#vvw) ### 2016 expand\_more December 12, 2016 Amit Daniely. [Learning Theory in the age of Neural Networks: Results and Challenges](/toc-seminar-16-17#adgr) November 14, 2016 Nikhil Bansal. [Discrepancy Algorithms beyond Partial Coloring](/toc-seminar-16-17#nbeut) November 7, 2016 Amin Saberi. [Thin Spanning Trees and Their Algorithmic Applications](/toc-seminar-16-17#assu) October 17, 2016 Huacheng Yu. [Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication](/toc-seminar-16-17#hysu) October 3, 2016 Mika Göös. [Extension Complexity of Independent Set Polytopes](/toc-seminar-16-17#mgh) September 26, 2016 Barna Saha. [Language Edit Distance, (min,+)-Matrix Multiplication & Beyond](/toc-seminar-16-17#bsuma) August 29, 2016 Daniel Kane. [A New Approach to Distribution Testing](/toc-seminar-16-17#dkucsd) May 9, 2016 Heng Guo. [Random Cluster Dynamics at q = 2 is Rapidly Mixing](/toc-seminar-15-16#guo) April 25, 2016 Li-Yang Tan. [An Average-Case Depth Hierarchy Theorem for Boolean Circuits](/toc-seminar-15-16#tan) April 11, 2016 David Zuckerman. [Explicit Two-Source Extractors and Resilient Functions](/toc-seminar-15-16#zuckerman) March 28, 2016 Ryan Williams. [Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits](/toc-seminar-15-16#williams) March 21, 2016 Mikkel Thorup. [The Power of Tabulation Hashing](/toc-seminar-15-16#thorup) March 7, 2016 Dana Moshkovitz. [Amplification and Derandomization Without Slowdown](/toc-seminar-15-16#moshkovitz) February 22, 2016 Sitan Chen. [Basis Collapse in Holographic Algorithms Over All Domain Sizes](/toc-seminar-15-16#chen) February 8, 2016 Harry Lang. [k-Median Clustering on Data Streams](/toc-seminar-15-16#lang) ### 2015 expand\_more December 7, 2015 Yin-Tat Lee. [Cutting Plane Method: A Faster Algorithm for Many (Combinatorial) Optimization Problems](/toc-seminar-15-16#lee) November 30, 2015 David Shmoys. [Smarter Tools for (Citi)bike-Sharing](/toc-seminar-15-16#shmoys) November 23, 2015 Boaz Barak. [Sum of Squares Lower Bounds for Planted Clique](/toc-seminar-15-16#barak) November 9, 2015 Sasha Razborov. [On the $AC^0$ Complexity of Subgraph Isomorphism](/toc-seminar-15-16#razborov) October 26, 2015 Elad Hazan. [Is Optimization Computationally Equivalent to Online Learning?](/toc-seminar-15-16#hazan) October 5, 2015 Philip Klein. [Approximation Schemes for Planar Graphs: A How-To Guide](/toc-seminar-15-16#klein) September 21, 2015 Ryan O'Donnell. [How to Refute a Random CSP](/toc-seminar-15-16#odonnell) August 31, 2015 Madhu Sudan. [Communication Amid Uncertainty](/toc-seminar-15-16#sudan)[ ](/seminar14-15#gupta) May 11, 2015 Anupam Gupta. [The Independent Set problem on Degree-d Graphs](/seminar14-15#gupta) May 4, 2015 Shay Solomon. [Dynamic Maximum Matching and Related Problems](/seminar14-15#solomon) April 27, 2015 Hammurabi Mendes. [Multidimensional $\\epsilon$-Approximate Agreement and Computability in Byzantine Systems ](/seminar14-15#mendes) April 13, 2015 Chandra Chekhuri. [Recent progress in structure of large treewidth graphs and some applications](/seminar14-15#chekhuri) March 30, 2015 Bobby Kleinberg. [Secretary Problems with Non-Uniform Arrival Order](/seminar14-15#kleinberg) March 9, 2015 Marco Gaboardi. [Relational verification of Differential Privacy and Mechanism Design...for a theory audience](/seminar14-15#gaboardi) March 2, 2015 Tsvi Kopelowitz. [Higher lower bounds from the 3SUM conjecture](/seminar14-15#kopelowitz) February 2, 2015 CS Colloquium: Omer Reingold. [Randomness vs. Memory: A Treasure(s) Hunt](http://www.seas.harvard.edu/calendar/event/81801) January 26, 2015 Yi Li. [For-all Sparse Recovery in Near-Optimal Time](/seminar14-15#li) January 21, 2015 CS Colloquium: Cynthia Dwork. [Privacy in the Land of Plenty](http://www.seas.harvard.edu/calendar/event/81731) ### 2014 expand\_more December 15, 2014 Zeev Dvir. [Private Information Retrieval with 2-Servers and sub-polynomial communication](/seminar14-15#dvir) [](/seminar14-15#dvir)December 8, 2014 Omri Weinstein. [Approximating the Best Nash Equilibrium in n^{o(log n)}-Time Breaks ETH.](/seminar14-15#weinstein) [](/seminar14-15#weinstein)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](/seminar14-15#pettie) November 24, 2014 Jan Vondrak. [Fast algorithms for optimization of submodular functions](/seminar14-15#vondrak) November 20, 2014 CS Colloquium: Christopher Moore. [Physics-inspired Algorithms and Phase Transitions in Community Detection.](http://www.seas.harvard.edu/calendar/event/80721) November 17, 2014 CS Colloquium: Yael Tauman Kalai. [Delegating Computation.](http://www.seas.harvard.edu/calendar/event/80891) November 17, 2014 Gillat Kol. [Exponential Separation of Information and Communication.](/seminar14-15#kol) November 17, 2014 CRCS Lunch Seminar: Babis Tsourakakis. [Algorithm Design for Large-Scale Datasets.](http://crcs.seas.harvard.edu/event/crcs-seminar-tbd-3) November 14, 2014 Avi Wigderson. [Points, Lines and Ranks of design matrices](http://www.math.harvard.edu/conferences/ahlfors14/) November 13-14, 2014 Ahlfors Lectures: Avi Wigderson. [Randomness/Permanent and Determinant: Non-Identical Twins](http://www.math.harvard.edu/conferences/ahlfors14/) November 10, 2014 CS Colloquium: Madhu Sudan. [Communication Amid Uncertainty.](http://www.seas.harvard.edu/calendar/event/80776) November 10, 2014 Chris Musco. [Graph Sparsification in the Streaming Model.](/seminar14-15#musco) November 6, 2014 CS Colloquium: Michael Kearns. [Games, Networks, and People.](http://www.seas.harvard.edu/calendar/event/80566) November 3, 2014 Pranjal Awasthi. [Learning Halfspaces with Noise.](/seminar14-15#awasthi) October 30, 2014 CS Colloquium: Richard Baraniuk. [Learning Near-Isometric Linear Embeddings.](http://www.seas.harvard.edu/calendar/event/80656) October 27, 2014 Sofya Raskhodnikova. [Constant-Time Testing and Learning Algorithms for Image Properties.](/seminar14-15#raskhodnikova) 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.](http://www.seas.harvard.edu/calendar/event/79856) October 9, 2014 CS Colloquium: Ron Fagin. [Applying Theory to Practice (and Practice to Theory).](http://www.seas.harvard.edu/calendar/event/79466) October 8, 2014 CMSA Colloquium: Salil Vadhan. The Computational Complexity of Data Privacy. October 6, 2014 Aaron Sidford. [Path-Finding Methods for Linear Programming.](/seminar14-15#sidford) September 29, 2014 Applied Math Colloquium: Rachel Ward. Linear Dimensionality Reduction via Random Projections. September 29, 2014 Eli Gafni. [The Coordinated-Attack Problem Revisited.](/seminar14-15#gafni) September 29, 2014 CRCS Lunch Seminar: Or Sheffet. [Utilitarian Models of Privacy Loss and Social Choice.](http://crcs.seas.harvard.edu/event/Or-Sheffet-Utilitarian-Models-of-Privacy-Loss-and-Social-Choice) September 22, 2014 Emanuele Viola. [Local Reductions.](/seminar14-15#viola) September 15, 2014 CRCS Lunch Seminar: Itai Ishlagi. [Unbalanced Matching Markets.](http://crcs.seas.harvard.edu/event/itai-ashlagi-crcs-seminar) September 12, 2014 EconCS Seminar: Moshe Babaioff. Bertrand Networks. May 16, 2014 Sjoerd Dirksen. [A Unified Approach to Dimensionality Reduction with Subgaussian Matrices. ](/seminar13-14#dirksen) Tuesday, May 6, 2014 Venkat Guruswami. [Polar codes: Reliable communication with complexity scaling polynomially in the gap to Shannon capacity. ](/seminar13-14#guruswami) Tuesday, April 22, 2014 Or Sheffet. [The Entropy Soon-To-Be-Method. ](/seminar13-14#sheffet) April 8, 2014 Raef Bassily. [Causal Erasure Channels. ](/seminar13-14#bassily) April 3, 2014 CS Colloquium: David Soloveichik. [Engineering Intelligent Molecular Systems.](http://www.seas.harvard.edu/calendar/event/77196) March 25, 2014 Aleksandar Nikolov. [Approximating Hereditary Discrepancy via Small Width Ellipsoids.](/seminar13-14#nikolov) March 24, 2014 CRCS Lunch Seminar: David Xiao. [Understanding Incentives for Privacy-Aware Individuals.](http://www.seas.harvard.edu/calendar/event/76921) March 11, 2014 Michael Forbes. [Hitting Sets for Multilinear Read-Once Algebraic Branching Programs, in any Order.](/seminar13-14#forbes) February 27, 2014 CS Colloquium: Raluca Ada Popa. [Building Systems that Compute on Encrypted Data.](http://www.seas.harvard.edu/calendar/event/76271) February 25, 2014 Mark Zhandry. [Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation.](/seminar13-14#zhandry) February 14, 2014 EconCS Seminar: Pavel Hubacek. [Single Round Delegation with Sublinear Verification.](http://www.eecs.harvard.edu/econcs/seminarAbstracts/Spring%202014/seminar_021414.htm) February 11, 2014 Justin Thaler. [On Interactivity in Arthur-Merlin Communication and Stream Computation.](/seminar13-14#thaler) January 29, 2014 CRCS Lunch Seminar: Jon Ullman. [Privacy and the Complexity of Simple Queries.](http://www.seas.harvard.edu/calendar/event/75616) January 28, 2014 Vladimir Braverman. [Approximating Large Frequency Moments with O(n^{1-2/k}) Bits.](/seminar13-14#braverman) ### 2013 expand\_more December 3, 2013 Aravindan Vijayaraghavan. [Smoothed analysis and uniqueness of tensor decompositions.](/smoothed-analysis-and-uniqueness-tensor-decompositions) November 21, 2013 CS Colloquium: Tim Roughgarden. [Beyond the worst case in auctions, graph partitioning, and social networks.](http://www.seas.harvard.edu/calendar/event/74156) November 20, 2013 CRCS Lunch Seminar: Scott Kominers. [Theory, practice, and engineering in (generalized) matching market design.](http://www.seas.harvard.edu/calendar/event/54826) November 19, 2013 Ying Xiao. [Fourier Principal Component Analysis.](/seminar13-14/#xiao) November 12, 2013 Grigory Yaroslavtsev. [Testing properties under Lp distances.](/seminar13-14/#yaroslavtsev) November 5, 2013 Adam Smith. [Privacy, stability and high-dimensional sparse regression.](/seminar13-14/#smith) October 31, 2013 CS Colloquium: Aleksander Madry. [(Electrical) Flows and graph algorithms.](http://www.seas.harvard.edu/calendar/event/54561) October 15, 2013 Yaron Singer. [Adaptive seeding in social networks.](/seminar13-14/#singer) October 10, 2013 CS Colloquium: Christos Papadimitriou. [Computational insights and the theory of evolution.](http://www.seas.harvard.edu/calendar/event/54466) October 7, 2013 Huy Nguyen. [Approximate near neighbor search: Beyond locality sensitive hashing.](/seminar13-14/#nguyen) October 3, 2013 CS Colloquium: Garud Iyengar. [First-order algorithms for convex optimization.](http://www.seas.harvard.edu/calendar/event/54176) October 1, 2013 Siu-On Chan. [Approximate constraint satisfaction requires large LP relaxations.](/seminar13-14/#chan) September 26, 2013 CS Colloquium: Craig Gentry. [A cryptographic approach to software obfuscation.](http://www.seas.harvard.edu/calendar/event/54471) September 17, 2013 Jelani Nelson. [OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings.](/seminar13-14/#nelson) May 17, 2013 Daniel Reichman. [Contagious Sets in Expanders. ](/12-13/Reichman.htm) May 10, 2013 Udi Wieder. [How to approximate a set without knowing its size in advance.](/12-13/Wieder.htm) April 26, 2013 Lorenzo Orecchia. [From Online Learning to Optimization and Back: the Power of Regularization.](/12-13/Orecchia.htm) April 12, 2013 Colin Jia Zheng. [A Uniform Min-Max Theorem with Applications in Cryptography.](/12-13/Zheng.htm) March 29, 2013 Eric Blais. [Approximating boolean functions with depth-2 circuits.](/12-13/Blais.htm) March 15, 2013 David Xiao. [Some optimal lower bounds for privacy in communication games.](/12-13/Xiao.htm) March 1, 2013 Thomas Steinke. [Unconditional Pseudorandom Generators for Small-Space Computation](/12-13/Steinke.htm) February 15, 2013 Justin Thaler. [Practical Verified Computation with Streaming Interactive Proofs](/12-13/Thaler.htm) February 1, 2013 Brendan Juba. [Efficient Reasoning in PAC Semantics](/12-13/Juba.html) ### 2012 expand\_more December 10, 2012 Grigory Yaroslavtsev. [Learning and Testing Submodular Functions](/12-13/Yaroslavtsev.html) December 3, 2012 Madhav Jha. [Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy.](/12-13/Jha.html) November 19, 2012 Eli Ben-Sasson. [A new family of locally correctable codes based on degree-lifted algebraic geometry codes](/12-13/BenSasson.html) November 5, 2012 Greg Valiant. [Finding Correlations, Learning Juntas, and the Closest Pair Problem](/12-13/Valiant.html) October 18, 2012 Irit Dinur. [Direct Products of Proofs and Gap Amplification](/12-13/Dinur.html) October 15, 2012 Jon Ullman. [Answering n^{2+o(1)} Counting Queries with Differential Privacy is Hard](/12-13/Ullman.html) October 1, 2012 Karthekeyan Chandrasekaran. [A Polynomial-Time Cutting Plane Algorithm for Matching](/12-13/Chandrasekaran.html) September 17, 2012 Andrew Wan. [Pseudorandomness for Linear Length Branching Programs and Stack Machines](/12-13/Wan.html) ### 2011 expand\_more November 10, 2011 Vitaly Feldman. [Bounds on complexity of SQ learning and ](/11-12/Feldman.htm) October 7, 2011 Varun Kanade. [Evolution with Recombination](/11-12/Kanade.html) September 14, 2011 Shachar Lovett. [Existence of small families of t-wise independent permutations and t-designs via local limit theorems](/11-12/Lovett.htm) [](/11-12/Lovett.htm)May 13, 2011 Dana Moshkovitz. [Hardness of Approximately Solving Linear Equations over Reals](/10-11/Moshkovitz.htm) May 5, 2011 Virginia Vassilevska Williams. [Path, Matrix, and Triangle Problems: Algorithms and Equivalences](/10-11/VW.htm) April 29, 2011 Graham Cormode. [Distributed Summaries](/10-11/Cormode.htm) April 22, 2011 Kai-Min Chung. [Memory Delegation](/10-11/Chung.htm) April 11, 2011 Mayank Varia. [Studies in Program Obfuscation](/10-11/Varia.htm) March 11, 2011 Yevgeniy Dodis. [Leftover Hash Lemma, Revisited](/10-11/Dodis.htm) February 25, 2011 Seth Pettie. [Everything you always wanted to know about Davenport-Schinzel sequences, but were afraid to ask](/10-11/Pettie.html) February 17, 2011 David Steurer. [On the Complexity of Graph Expansion and the Unique Games Conjecture](/10-11/Steurer2.htm) February 14, 2011 Ryan Williams. [Algorithms, Obstructions, and Beating Exhaustive Search](/10-11/Williams.htm) February 10, 2011 Shubhangi Saraf. [High-rate Codes with Sublinear-time Decoding](/10-11/Saraf.htm) February 3, 2011 Jelani Nelson. [Sketching and Streaming Algorithms](/10-11/Nelson.htm) January 31, 2011 Mark Braverman [Information and interactive communication](/10-11/Braverman.html) January 28, 2011 Martin Suchara. [BGP Safety with Spurious Updates - The Conditions of BGP Convergence](/10-11/Suchara.html) ### 2010 expand\_more November 19, 2010 Adam Kalai. [Dueling Algorithms](/10-11/Kalai.html) October 29, 2010 David Steurer. [Subexponential Algorithms for Unique Games and Related Problem](/10-11/Steurer.html) [](/10-11/Steurer.html)October 15, 2010 Tal Moran. [On Complete Primitives for Fairness](/10-11/Moran.html) October 1, 2010 Brendan Juba. [Universal Semantic Communication](/10-11/Juba.html) September 13, 2010 Chen Avin. [Random walks techniques for (wireless) networks](/10-11/Avin.html) June 29, 2010 Manoj Prabhakaran. [Cryptographic Complexity and Computational Intractability ](/09-10/Prabhakaran.html) May 17, 2010 Raghu Meka. [Pseudorandom Generators for Polynomial Threshold Functions](/09-10/Meka.html) April 26, 2010 Jonathan Ullman. [PCPs and the Hardness of Generating Private Synthetic Data](/09-10/Ullman.html) April 12, 2010 Justin Thaler. [Streaming Graph Computations with a Helpful Advisor ](/09-10/Thaler2.html) April 5, 2010 Shubhangi Saraf. [Blackbox Polynomial Identity Testing for Depth 3 Circuits ](/09-10/Saraf.html) March 29, 2010 Giorgos Zervas. [Information Asymmetries in Pay-Per-Bid Auctions: How Swoopo Makes Bank](/09-10/Zervas.html) February 8, 2010 Steven (Shlomo) Gortler. [Characterizing the Universal Rigidity of Generic Frameworks](/09-10/Gortler.html) February 1, 2010 Kai-Min Chung. [Security Amplification and Parallel Repetition Theorems](/09-10/Chung.html) ### 2009 expand\_more November 18, 2009 Sergei Vassilvitskii. [A Model of Computation for MapReduce](/09-10/Vassilvitskii.html) November 4, 2009 Niv Buchbinder. [The Randomized k-Server Conjecture (Online Algorithms meet Linear Programming)](/09-10/Buchbinder.html) October 21, 2009 Varun Kanade. [Potential-based agnostic boosting](/09-10/Kanade.html) October 9, 2009 Harvey M. Friedman. [Decision Procedures for Verification](/09-10/Friedman.html) September 23, 2009 Justin Thaler. [Graph Covers and Quadratic Minimization](/09-10/Thaler.html) April 30, 2009 Jennifer Chayes. [IIC/CS colloquium](http://iic.harvard.edu/seminars/iic-colloquium-series-fall-2008-through-spring-2009/iic-cs-joint-colloquium-interdisciplina) April 29, 2009. Guy Rothblum. [On the Complexity of Differentially Private Data Release: Efficient Algorithms and Hardness Results](http://www.eecs.harvard.edu/theory/08-09/guy.html) (CRCS Privacy and Security Lunch Seminar) April 20, 2009 Alex Samorodnitsky. [Counting Magic Squares](http://www.eecs.harvard.edu/theory/08-09/alex.html) April 15, 2009 Katrina Ligett. [Differentially private approximation algorithms](http://www.eecs.harvard.edu/theory/08-09/Ligett.html) April 6, 2009 Alex Slivkins. [Multi-Armed Bandits in Metric Space](http://www.eecs.harvard.edu/theory/08-09/slivkins.html) March 30, 2009 David Choi. [Sample Complexity Bounds for Link Prediction](http://www.eecs.harvard.edu/theory/08-09/choi.html) March 11, 2009 Ketan Mulmuley. [On P vs NP, Geometric Complexity, and the Riemann Hypothesis](http://www.eecs.harvard.edu/theory/08-09/ketan.html) February 26, 2009 Muthu Muthukrishnan. See the [departmental colloquium series](http://www.seas.harvard.edu/cscolloquium/) February 23, 2009 Zhenming Liu. [Designing Floating Codes for Expected Performance](http://www.eecs.harvard.edu/theory/08-09/Liu.html) February 20, 2009 David Xiao. [On the Black-box Complexity of PAC Learning](http://www.eecs.harvard.edu/theory/08-09/Xiao.html) ### 2008 expand\_more December 8, 2008 Yuri Gurevich. [Proof of Church’s Thesis](http://www.eecs.harvard.edu/theory/08-09/Gurevich.html) December 1, 2008 Luca Trevisan. [Regularity, boosting, and efficiently simulating every high entropy distribution](http://www.eecs.harvard.edu/theory/08-09/Trevisan.html) November 10, 2008 Kai-Min Chung. [Tight Bounds for Hashing Block Sources](http://www.eecs.harvard.edu/theory/08-09/Chung.html) November 3, 2008 Ran Raz. Parallel [Repetition of Two Prover Games: A Survey, Application, and a Counterexample to Strong Parallel Repetition.](http://www.eecs.harvard.edu/theory/08-09/Raz.html) October 20, 2008 Tal Moran. [An Optimally Fair Coin Toss: Cleve’s Bound is Tight](http://www.eecs.harvard.edu/theory/08-09/tal.html) October 6, 2008 Amin Saberi. [Game Dynamics, Equilibrium Selection and Network Structure](http://www.eecs.harvard.edu/theory/08-09/saberi.html) September 29, 2008 Flavio Chierichetti. [Gossiping in Social Networks](http://www.eecs.harvard.edu/theory/08-09/chierichettiabs.html) September 15, 2008 Alan Frieze. [Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time](http://www.eecs.harvard.edu/theory/08-09/friezeabs.html) ### 2007 expand\_more May 14, 2007 Allan Borodin. [Greedy algorithms and other simple greedy-based algorithms for simple (to define) optimization problems](/06-07/borabs.html) May 7, 2007 Lenore Cowen. [Compact Routing from Theory to Practice](/06-07/cowabs.html) May 3, 2007 Ramin Zabih. [Flow-based optimization methods in computer vision](http://www.seas.harvard.edu/newsandevents/calendars/cscolloquia.html#E63830633) April 30, 2007 Ueli Maurer. [Indistinguishability Amplification](/06-07/mauabs.html) April 23, 2007 Phil Klein. [A planar-graph decomposition, and its application to TSP and Steiner Tree](/06-07/kleabs.html) April 16, 2007 Sergey Yekhanin. [New Locally Decodable Codes and Private Information Retrieval Schemes](/06-07/yekabs.html) April 2, 2007 Martin Wainwright. [Analysis of MAX-XORSAT and its Generalizations, with Application to Distributed Compression and "Dirty Paper" Coding](/06-07/waiabs.html) March 12, 2007 Gopal Pandurangan. [Efficient Distributed Approximation Algorithms for Minimum Spanning Trees](/06-07/panabs.html) February 26, 2007 Shanghua Teng. [Game and Market Equilibria](/06-07/tenabs.html) February 12, 2007Ankit Patel. [The Theory of Desynchronization: Self-Organizing Algorithms for Periodic Resource Scheduling](/06-07/patabs.html) [](/06-07/patabs.html)February 5, 2007 Salil Vadhan. [Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes](/06-07/vadabs.html) ## **[Fall 2024](https://docs.google.com/document/d/1qBfsiK-NNe_dMIsShMSiJe5_Qsc2tmYJMSVzbsMw0RI/edit#heading=h.6c0r0a61enx8)**