CS 579 Computational Complexity

Fall 2012

Instructor: Alexandra Kolla
Wed-Fri 12:30 - 13:45
SC 1103
Office Hours: Fri 11:00-12:00
(Please send me an email if you would like to meet at a different time).

Announcements

  • As a reminder, there is class on Friday, December 14. Same time, same room.
  • Please submit your slides and write-ups for your final project by the end of next week!
  • Homework set 2 is out and it is due by Friday, November 30.
  • NO CLASS on Wednesday, 10/31.
  • NO CLASS (and no office hours) on Friday, 10/5.
  • New Deadline for Homework 1 is Wednesday, 10/10 at midnight.
  • Homework set 1 is out and it is due by Friday 10/5.
  • Office hours changed to Friday, same time. Come to the Theory seminar instead on Wednesday 11:00-12:00.

    Class Description

    Computational Complexity examines the resources that are needed to solve computational problems we are interested in. Those resources include but are not limited to running time, memory, amount of communication. One of the main points of focus of computational complexity is the distinction between "tractable" problems, which can be solved "efficiently" by existing or conceivable computational models and "intractable" problems, whose solution requires an unreasonably large amount of resources. This course will have two main parts. During the first part, we will study rather "basic" concepts such as time, space, P versus NP, polynomial hierarchy, the power of randomness in algorithms, the complexity of counting problems, and the average-case complexity of problems. During the second part, we will explore more recent material such as PCP and hardness of approximation, circuit lower bounds, derandomization and average-case complexity, quantum complexity theory.

    Homeworks and Exams

  • There will be two to three Homework sets and a Final Project.
  • Homework policy: Each student is expected to present an individual write up. Please give credit wherever credit is due (collaborators, online sources...).
    Some of the solutions to the problems might be available online, I advise against looking them up.
  • Homework 1 is due October 5.
  • Homework 1 will be graded out of 100 points. As you will see, if you do all the problems, you will get 110 points. You can either choose to leave any 10 pt. problem out, or just try them all out for extra credit.
  • It would be greatly appreciated, though it is not necessary, if you type up the solutions and either email them to me or print them out and hand them over.
  • Each of you is required to give me an individual write-up.
  • If you work with a partner, please acknowledge them in your write-up.
  • Homework 2 is due November 30.
  • Same rules as for Homework 1.

    Useful Books and Lecture Notes

  • Computational Complexity: a Modern Approach. Sanjeev Arora and Boaz Barak.
  • Online version of the book.
  • Lecture notes (i) , lecture notes (ii) , Lecture notes (iii) from several different classes by Luca Trevisan .

    Lectures

    Date Topics Reading
    Lecture 0:
    August 29    		 Overview of Complexity Theory, Course Plan.
  • class slides
    • Lecture 1:
    August 31    		 P and NP, Deterministic Time Hierarchy Theorem.
  • class slides
  • See also chapters 2,3 from Arora-Barak
    • Lecture 2:
    September 5    		 Space complexity.
  • class slides
  • See also chapter 4 from Arora-Barak
    • Lecture 3:
    September 7    		 NL=coNL, Polynomial Hierarchy.
  • class slides
  • See also chapters 4,5 from Arora-Barak
    • Lecture 4:
    September 12    		 Boolean Circuits.
  • class slides
  • See also chapter 6 from Arora-Barak
    • Lecture 5:
    September 14    		 Randomized Computation.
  • class slides
  • See also chapter 7 from Arora-Barak
    • Lecture 6:
    September 19    		 Randomized Reductions and Valiant-Vazirani.
  • class slides
  • See also chapters 7,17 from Arora-Barak
    • Lecture 7:
    September 21    		 #P and Approximate Counting.
  • class slides
  • See also chapter 17 from Arora-Barak and these lecture notes.
    		•
    Lecture 8:
    September 26    		 Interactive Proofs.
  • class slides
  • See also chapter8 from Arora-Barak.
    • Lecture 9:
    September 28    		 IP=PSPACE,Part I.
  • class slides
  • See also chapter8 from Arora-Barak.
    • Lecture 10:
    October 3    		 IP=PSPACE,Part II.
  • class slides
  • See also chapter8 from Arora-Barak.

    • October 5    		 NO CLASS
    Lecture 11:
    October 10    		 Expansion and Eigenvalues.
  • class slides
  • See also this blog post
    • Lecture 12:
    October 12    		 Random Walks and Eigenvalues.
  • class slides
  • See also these and these lecture notes
    • Lecture 13:
    October 17    		 Quasi-random Properties of Expanders.
  • class slides
  • See also these and these lecture notes
    • Lecture 14:
    October 19    		 Expanders from Cayley Graphs.
  • class slides
  • See also these lecture notes
    • Lecture 15:
    October 24    		 Zig-Zag Product.
  • See these lecture notes
    • Lecture 16:
    October 26    		 STUCONN in L.
  • class slides
  • See also these lecture notes
    • Lecture 17:
    November 2    		 PCP and Hardness of Approximation.
  • class slides
  • See also chapter 11 from Arora-Barak.
    • Lecture 18:
    November 7    		 Hastad's PCP Verifier.
  • class slides
  • See also these lecture notes
    • Lecture 19:
    November 9    		 Introduction to Quantum Computing.
  • class slides
  • See also these lecture notes
    • Lecture 20:
    November 14    		 Unitary Transformations, Bell States.
  • class slides
  • See also these lecture notes
    • Lecture 21:
    November 16    		 Hilbert Spaces, Tensor Products, Quantum Teleportation.
  • class slides
  • See also these lecture notes