Theory of Computing 

Computer Science 6810
Cornell University
Spring 2009


Instructor: Rafael Pass

Time: TR 1:25-2:40
Place: 111 Upson
Course Web page: http://www.cs.cornell.edu/courses/cs6810/2009sp/

 

TA: Muthu Venkitasubramaniam

Office Hours: TBA
Place: TBA

Overview

Graduate introductory class in computational complexity. Principal topics include:

  1. Time and space complexity,
  2. Non-uniform models of computation and circuit lower bounds,
  3. Non-determinism and alternation,
  4. Counting problems,
  5. Randomness and pseudo randomness,
  6. Hardness amplification,
  7. Interactive proofs,
  8. Probabilistically checkable proofs and inapproximability.

Prerequisites

CS 3810 and CS 4820 or 6820 or permission of instructor. (COM S 381 or 481 and COMS S 482 or 681 or permission of instructor.)

 

The main skills that will be assumed from these courses are: 1) the ability to understand and write formal mathematical definitions and proofs and 2) comfort with reasoning about algorithms, such as proving their correctness and analyzing their running times. It is also important that you are familiar with basic probability, and basic complexity classes such as P and NP.

Course Administration

We are using the course management system, CMS.  Please login to http://cms.csuglab.cornell.edu/ and check whether you are registered. There will be a list of courses you are registered for, and Com S 6810 should be one of them.  If not, please send your full name and Cornell netid to the TA so they can register you.  You can check your grades and submit homework in CMS. 

Grading

There will be roughly 3-4 homeworks and a final project. Students are also required to scribe lecture notes. A first draft of the scribe notes should be handed in within 24 hours of the lecture. Use this template to scribe.

 

HW 1 is due on Feb 3. A handout on notation and basic probability.

 

Homeworks need to be handed in before the beginning of class. Additionally, you have a total of 4 “late-days” that you can use throughout the semester.

Homework Policy

You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to a member of the course staff.
Assignments will be posted in CMS. Submit hardcopy in class or to the TA by the due date, or as a .pdf, .ps, .doc, or .txt file in CMS.
Typed problem sets are strongly preferred.

Reading  

There is no single required text. You may find the following books to be useful references. Note, however, that we will not always be following the same notational conventions as these books.

 

ˇ        Dexter Kozen, Theory of Computation.

ˇ        Oded Goldreich, Computational Complexity: A Conceptual Approach. A draft of the book is available online.

Topics Outline (subject to change)

  • Intro and Basic Resources:
    1. Computational Resources, Reductions, NP-completeness [Chap 1&2 in AB]
    2. Diagonalization, time hierarchies for DTIME and NTIME, Ladner’s Rhm, Relativization [Chap 3 in AB]
    3. Space Complexity. The class NSPACE. Savitch’s Thm, Immerman-Szelepcsényi Thm. [Chap 4 in AB]
  • Alternation and Non-uniformity [Chap 5 & 6 in AB]
    1. The polynomial hierarchy (PH), PSPACE complete problems
    2. Circuits, The class P/poly. Karp-Lipton Thm.
  • Randomness [Chap 7 in AB]
    1. Polynomial identity testing,
    2. The classes RP, BPP. Amplification.
    3. Adleman and Lauteman-Sipser Thms.
  • Counting [Chap 17 in AB]
    1. #P-completeness. The Permanent problem
    2. approximate counting with NP oracle
    3. Unique SAT and Valiant-Vazirani’s Thm.
  • Interactive Proofs [Chap 8 in AB]
    1. Interactive proofs, The Graph Non-Iso protocol.
    2. Public vs private coins, perfect completeness
    3. Error-reduction, collapsing rounds, co-NP ⊆ AM => PH collapses.
    4. Set lower-bound protocol.
    5. IP = PSPACE, instance-checkers.
  • PCP's and Inapproximability. [Chap 11 & 22 in AB]
    1. Basics of PCP, connection to inapprox
    2. NP ⊆ PCP(poly,O(1))
    3. Linearity testing, The Fourier technique
    4. (Maybe Dinur’s PCP)
  • Average-case hardness [Chap 7 & 8 in Goldreich]
    1. OWF vs hard functions.
    2. Hardness amplification of OWF
    3. Yao's XOR lemma
    4. Hard-core bits, The Goldreich-Levin Thm
    5. Psedorandomness, Blum-Micali, Derandomization of BPP.
    6. Nisan-Wigderson generator
    7. Worst-case to Average-case reductions. On the possibility of basing OWF on NP ≠ P.
  • More on P v.s. NP.
    1. Circuit lower-bounds. Hastad’s switching lemma. Unconditional derandomization.
    2. Natural proofs
    3. Impaglizzo's worlds.

Lecture Notes

Please note that the scribe notes are only rough drafts of the lectures.