CS 294:  Theoretical Computer Science’s Greatest Hits

Meeting:  320 Soda,   Monday 3-6pm


This is a graduate-level seminar class covering great papers in theoretical computer science in the last 10-15 years. The goal is to highlight the broad trends and grand challenges of theoretical computer science today.

Each week, one student will present one of the papers to the class.  

The goal of the presentation is to set up the context of the paper, why it is important?  what is the broader revolution it spurred or is it part of, or what grand challenge is it aimed at?   Then, to the extent possible, outline the technical details in a 1.5 to 2.5 hour talk.  In addition to learning about recent results, a goal of this course is to stimulate further research on open problems related to the paper.

Walk-ins Welcome! 

Tentative Schedule:




Jan 25

Prasad. R


SL = L

Derandomized Squaring of Graphs

Eyal Rozenman, Salil Vadhan.


Feb 1

Prasad.  R

Prerequisite:  random walks, basic linear algebra, expander graphs, analysis of random walks using spectral  techniques.

Suggested Reading  for Prerequisites:   Chap 2, Sec 3.1,3.2 in Expander Graphs & their Applications.



SL = L (continues)


Feb 8

Jonah & Manuel


Feb 22

Tselil & Paul

Computing Maximum Flow

Feb 29

Fotis & Jing Cheng

Computational Phase Transitions.

March 7

Pasin & Prasad. R


LP Size Lower Bounds

March 14

Peihan & Ben Caulfield

Fully-Homomorphic Encryption

March 28

Vrettos & Sayan

Interlacing Polynomials

April 4


Sam & David Dinh


Solving Laplacian Linear Systems

April 11


Antares & Xingyou



Unique Games Conjecture


April 18


Preetum & Chenyang


SDP Size Lower Bounds

April 25


Aaron & Richard


Navigating Central Path with Electrical Flows:from Flows to Matchings and Back by Aleksander Madry


Suggested Papers:

Here is a preliminary list of papers to choose from ( I will add a few more soon).  Feel free to suggest a paper not on the list.


·         Solving Lagrangian Linear Systems


A simple, combinatorial algorithm for solving SDD systems in nearly-linear time.

Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu

·         SL = L


Undirected ST-Connectivity in Log Space

Omer Reingold


·         Homomorphic Encryption


Efficient Fully Homomorphic Encryption from (Standard) LWE

Zvika Brakerski, Vinod Vaikuntanathan.


·         Unique Games Conjecture & Optimal Hardness for MaxCut


Optimal Inapproximability Results for MaxCut and other 2-Variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O Donnell.


·         Computational Phase Transition


Computational Transition at the Uniqueness Threshold

Allan Sly


·         QIP = PSPACE


Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous.


·         ACC lower bounds

Non-Uniform ACC Circuit Lower Bounds

Ryan Williams


·         Interlacing Polynomials


Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

Adam Marcus, Dan Spielman, Nikhil Srivastava


·         Information Complexity vs Communication complexity


How to Compress Interactive Communication

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao


·         Sparsest Cut


Expander Flows, Geometric Embeddings and Graph Partitioning

Sanjeev Arora, Satish Rao, Umesh Vazirani


·         Nash is PPAD complete

The complexity of computing Nash equilibria.

Constantinos Daskalakis,  Paul W Goldberg, Christos H Papadimitrou.


·         Oblivious Routing


Optimal hierarchical decompositions for congestion minimization in networks. 

Harald Racke


·         Computing Maximum Flow


Nearly Maximum Flows in Nearly Linear Time.

Jonah Sherman


·         Alternate Proof of PCP Theorem


The PCP Theorem by Gap Amplification.

Irit Dinur


·         Indistinguishability Obfuscation


Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits

Sanjam Garg,Craig Gentry,Shai Halevi,Mariana Raykova,Amit Sahai,Brent Waters


·        k-SAT Threshold


Proof of Satisfiability Conjecture for large k

Jian Ding, Allan Sly, Nike Sun


·        Two Source Extractors


Explicit Two-Source Extractors & Resilient Functions

Eshan Chattopadhyay, David Zuckerman


·        Lower bounds on size of LPs


Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf


·         Lower bounds on size of SDPs


Lower bounds on the size of semidefinite programming relaxations

James Lee, Prasad Raghavendra, David Steurer