CS 294:  Theoretical Computer Science’s Greatest Hits

Meeting:  320 Soda,   Monday 3-6pm

Overview:

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:

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

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

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