CS 294:
Theoretical Computer Science’s Greatest Hits
Meeting: 320 Soda, Monday 36pm
Overview:
This is a graduatelevel seminar class
covering great papers
in theoretical computer science in the last 1015 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.
Walkins Welcome!
Tentative Schedule:
Date 
Speaker 
Paper 
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 
QIP* = PSPACE 
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 
FullyHomomorphic 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
nearlylinear time.
Jonathan A. Kelner, Lorenzo Orecchia,
Aaron Sidford, Zeyuan Allen Zhu
·
SL = L
Undirected STConnectivity 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 2Variable CSPs?
Subhash Khot, Guy Kindler, Elchanan
Mossel, Ryan O Donnell.
·
Computational Phase Transition
Computational Transition at the Uniqueness Threshold
Allan Sly
·
QIP = PSPACE
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay,
John Watrous.
·
ACC lower bounds
NonUniform
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
·
kSAT Threshold
Proof of
Satisfiability Conjecture for large k
Jian Ding, Allan Sly,
Nike Sun
·
Two Source Extractors
Explicit
TwoSource 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