Course Syllabus

Jump to Today

W 1:25-2:45, MEB 3147 (LCR)

The seminar has two goals.  First, we will study some of the "classical" papers in theoretical computer science.  The topics will be broad, ranging from complexity theory to algorithms; the idea is to obtain a flavor of different areas.  Second, we will focus on how to "read" theory papers.  While reading in non-technical settings requires no serious thought, reading math/theory often needs a significant amount of (at least subconscious) planning.  

The Stages of Reading

  1. Identifying the main result(s) and contributions
  2. Extracting the skeleton of the paper (how the results and lemmas fit together)
  3. Identifying what background is needed, and what can be skipped on a first reading
  4. Translating math into words: understanding the deeper meaning of the algebra
  5. Relative importance of the different parts of a proof
  6. Being able to retell a proof as a “story”

Goals for each paper (week 1 and 2):

  1. Do steps 1 and 2 BEFORE week 1 of the paper. These will be discussed in class
  2. Step 3 will be discussed in class. Initially, we will provide help with background, but eventually we will expect you to find the relevant background and peruse it. 
  3. Steps 4 and 5 should be done before week 2 of the paper.
  4. Step 6 will be written up after week 2 of the paper. 

Reading Plan

 

Date

Topic

Reading

Aug 23

Semidefinite programming (MAX CUT and 3 coloring)

Papers on MAX CUT and 3-Coloring.

Aug 30

Interactive proofs

Paper of Lund et al.

Sep 6

(continued) Connection to PCPs and hardness of approximation

Sep 13

Complexity of Games and Nash Equilibria

Roughgarden's lecture notes (specifically Lecture 20)

Sep 20

 (continued) class PPAD

Sep 27

Linear and semidefinite programming hierarchies

 Paper of Guruswami and Sinop

Oct 4

(continued)

Oct 18

Data structure lower bounds using LSD (lop-sided set disjointness)

 Paper of Patrascu

Oct 25

(continued)

Nov 1

How hard is counting? #P-completeness 

Paper of Dyer, Frieze and Kannan

Nov 8

 (continued)

Nov 15

Cryptography implies that learning is hard

Paper of Klivans and Sherstov

(Alternately) paper of Daniely et al. 

Nov 29

Is 0.878.. the best approximation possible for MAXCUT?

Paper of Khot et al.

Dec 6

(continued)

 

Course Summary:

Date Details Due