# Theory of Computation Seminar

## 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 Vassilevska-Williams. Fixed-parameter dynamic algorithms

### 2016

May 9, 2016

Heng Guo. Random Cluster Dynamics at q = 2 is Rapidly Mixing

April 25, 2016

Li-Yang Tan. An Average-Case Depth Hierarchy Theorem for Boolean Circuits

April 11, 2016

David Zuckerman. Explicit Two-Source Extractors and Resilient Functions

March 28, 2016

Ryan Williams. Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three 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. k-Median Clustering on Data Streams

### 2015

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

### 2014

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.

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

### 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 Ben-Sasson. A new family of locally correctable codes based on degree-lifted 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 Polynomial-Time 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 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

### 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 Pay-Per-Bid Auctions: How Swoopo Makes Bank

February 8, 2010

Steven (Shlomo) Gortler. Characterizing the Universal Rigidity of Generic Frameworks

February 1, 2010

Kai-Min 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 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

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

Kai-Min 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 greedy-based algorithms for simple (to define) optimization problems

May 7, 2007

Lenore Cowen. Compact Routing from Theory to Practice

May 3, 2007

Ramin Zabih. Flow-based optimization methods in computer vision

April 30, 2007

Ueli Maurer. Indistinguishability Amplification

April 23, 2007

Phil Klein. A planar-graph 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 MAX-XORSAT 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: Self-Organizing Algorithms for Periodic Resource Scheduling

February 5, 2007

Salil Vadhan. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes