Greatest Hits of TCS (or This Really IS a TCS Blog, I Swear!)

This semester Prasad Raghavendra is holding a course called Theoretical Computer Science’s Greatest Hits.  It seems like it’s going to be a lot of fun!

Anywho, I thought I’d keep you folks all up to date and give a synopsis of each session.  This is of course for your benefit to get an idea of the landscape of TCS and not at all my selfish attempt to force myself to have a responsibility to read and understand the material…

(I hope to blog about other things than this in the meantime too…but that may fall by the wayside a little bit this semester.  That’s why categories and tags are great!  You can always find which topic that you like me blogging about even when I go on a binge of a topic you might not be interested in!)

This course is essentially a reading group; there’s a (subjective) list of the greatest hits of TCS (within the last 10 or 15 years or so) and the students read whichever one they’re most curious about and present it to the class.  It’s a 3 hour Monday class and we plan to generally go over one paper (greatest hit) per week.

My plan is to make a post once a week giving a summary of the greatest hit and what was covered.  This is my plan…so I’m sure God is having a little laugh to herself right now.

But, if things go well, I’ll be learning, you’ll be learning, everybody wins.

A note about the class: What I love most about this class is that Prasad is putting heavy weight onto learning about the results in the context of TCS landscape and wants us to give the picture of why each result is considered important and what led up to it and what it inspired.  So a good portion of these results should be based on the TCS culture and human aspect, which I absolutely love.

And Prasad has set a strong example with a great beginning by giving the first presentation (on the SL=L result which I’ll discuss in my next post) and a beautiful amount of background and context.  This is going to be exciting!

That being said, it’s hard to say who the audience is.  Well…actually, it’s not hard to say.  The audience is the people that gather into Soda 320 at 3pm on Mondays.  That’s the audience; this is what Prasad said.  With a title like TCS’s Greatest Hits, it got a bit of interest.  From hardcore theory people to systems people that thought it would be a good survey class.  So it’s a wide-ish audience and the TCS background is meant to be minimal-ish but some heavy duty TCS ideas and intuitions are still being thrown around (even if they are kinda from the ground up).  That being said, Prasad said we should make our presentations with this audience in mind…”this audience” meaning these specific people sitting in the room.  So, my blogging about this may be a little bit of a mismatch of audience but we’ll bear through it.

Finally, as a disclaimer, I’m going to relieve myself of all responsibility and say I may not be entirely faithful to either punctuality in blogging or the presentations themselves.  I may skip things, I may add things, I may focus on what I know least about, I may focus on what I know most about.  I hope to really bring out the context of these works and give a sketch of how the result was achieved (which is what we’re meant to do in the course) but the format and focuses of how I do that will emerge as I start doing them.

Prasad has started the course off by proving Omer Reingold’s Gödel-Prize-Winning result that SL=L (although we’re doing it via the perspective of Rozenman and Vadhan in a “simplified” proof).  This first talk will span two classes and after it’s done I will post about it.  I’m thinking about following up the next week with by presenting (and then blogging) the result of QIP=PSPACE.  Below is the current (preliminary) list of papers we may want to read.


Note that this is not the order they will be in (the list and order may be updated as they happen though).  Let’s have fun!

  • Solving Laplacian 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


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

This entry was posted in Intermediate, Landscape, TCS and tagged , , , . Bookmark the permalink.

One Response to Greatest Hits of TCS (or This Really IS a TCS Blog, I Swear!)

  1. Pingback: Greatest Hits of TCS: SL=L | On The Shoulders Of Windmills

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s