CS 6520 - Computational Complexity

Spring 2008


A list of possible term paper topics 


Complexity of Satisfiability
Reading:
  1. D. van Melkebeek. A Survey of Lower Bounds for Satisfiability and Related Problems. 

Complexity of Counting
This is a very important basic topic that is not covered in the course. Reading:
  1. Chapter 9 of Arora-Barak.
  2. Section 6.2 of Goldreich.
These sections cover, among other important things, the class #P introduced by Valiant, Valiant's Theorem that Permanent is #P-Complete, approximate counting and uniform generation, and Toda's Theorem. 

Expanders and Applications
Reading:
  1. S. Hoory, N. Linial and A. Wigderson. Expander graphs and their applications.
  2. Notes for Lectures 7 - 9 from the course CS 225: Pseudorandomness at Harvard University taught by Salil Vadhan.
The excellent survey and lecture notes cover, among other important things, basic properties of expanders, explicit constructions of constant-degree expanders (in particular the Margulis/Gaber-Galil construction, and the Reingold-Vadhan-Wigderson construction based on the zig-zag product) and their analysis, and applications including Reingold's deterministic Logspace algorithm for USTCONN. I highly recommend these topics. 

Conditional Derandomization of BPP
Reading:
  1. Notes for Lectures 17 - 21 and 14 - 15 from the course CS 225: Pseudorandomness at Harvard University taught by Salil Vadhan.
  2. Chapters 16 and 17 of Arora-Barak.
The lecture notes of Vadhan and the chapters of Arora-Barak cover, among other important things, the Nisan-Wigderson generator, the work of Impagliazzo and Wigderson on hardness amplification, and a recent work of Sudan, Trevisan and Vadhan which gives an elegant, completely different and much simpler proof of the Impagliazzo-Wigderson result. 

Unconditional Derandomization of Space-Bounded Computation
Reading:
  1. N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica 12(4): 449-461, 1992.
    See also Sections 16.6 - 16.7 of Arora-Barak.
  2. N. Nisan. RL is in SC. Computational Complexity 4: 1-11, 1994.
  3. N. Nisan and D. Zuckerman. Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1): 43-52, 1996.
  4. M. Saks and S. Zhou. BPSpace(S) is in DSPACE(S^{3/2}). J. Comput. Syst. Sci. (JCSS) 58(2):376-403, 1999. 

Proofs of the PCP Theorem
Reading:
  1. See Arora's Ph.D. thesis for the original proof the PCP Theorem.
  2. For Dinur's new proof of the PCP Theorem, see Dinur's original paper, and these exellents notes of Guruswami and O'Donnell. 

Hardness of Approximation
Reading:
  1. Lectures notes of this course at Georgia Tech taught by Subhash Khot, and this course at University of Washington taught by Guruswami and O'Donnell.
  2. See also the references therein.

I highly recommend that you read Hastad's 3-bit PCP and tight hardness result for MAX-3LIN, Feige's result for Set Cover, and the result of Khot, Kindler, Mossel and O'Donnell for MAX-CUT assuming the Unique Game Conjecture. 

Raz's Parallel Repetition Theorem
The Parallel Repetition Theorem, proven by Raz, is an indispensable tool and perhaps the most important theorem for hardness of approximation besides the PCP Theorem. Most results in hardness of approximation today are proven using the Label Cover Problem and the Parallel Repetition Theorem as the starting point. Raz's original proof of the theorem is difficult. Very recently Raz's proof has been slightly simplified and improved by the following two elegant papers:
  1. T. Holenstein. Parallel repetition: simplifications and the no-signaling case.
  2. A. Rao. Parallel Repetition in Projection Games and a Concentration Bound. 

Circuit Lower Bounds
Reading:
  1. Some important results not covered in the course. References to be added...
  2. A. Razborov and S. Rudich. Natural Proofs. This paper concerns some limitations of the current techniques for proving circuit lower bounds. 

Communication Complexity
Reading:
  1. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997. An excellent book.
  2. See also these notes of Raz, and Chapter 12 of Arora-Barak. 

Algebraic Complexity
Reading:
  1. References to be added... 

Complexity of Lattice Problems
Reading:
  1. Lecture notes of the course Lattices in Computer Science at Tel-Aviv University taught by Oded Regev.
  2. O. Goldreich and S. Goldwasser. On the Limits of Non-Approximability of Lattice Problems.
  3. D. Aharonov and O. Regev. Lattice problems in NP intersect coNP.
  4. S. Khot. Hardness of approximating the shortest vector problem in lattices.
  5. I. Haviv and O. Regev. Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors.
  6. D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measure.
  7. C. Peikert. Limits on the Hardness of Lattice Problems in l_p Norms. 

Primarlity Testing
Reading:
  1. M. Rabin. Probabilistic algorithm for testing primality. J. Number Theory, 12:128-138, 1980.
    See also Chapter 10 of the book A Computational Introduction to Number Theory and Algebra by Shoup. This chapter gives a good exposition on the Miller-Rabin test and some applications.
  2. M. Agrawal and S. Biswas. Primality and Identity Testing via Chinese Remaindering.
  3. M. Agrawal and N. Kayal and N. Saxena. PRIMES is in P. This is the celebrated AKS algorithm.
  4. L. Adelman, C. Pomerance and R. Rumley. On distinguishing prime numbers from composite numbers. Annals of Mathematics, 117:173-206, 1983.
    For an improvement of the APR test by Cohen and Lenstra, see Section 9.1 of the book A Course in Computational Algebraic Number Theory by Henri Cohen. The APR test is a deterministic test whose time is "almost" polynomial. Although the running time falls slightly short of being polynomial, I think that it is as important and interesting as the AKS test. The APR test uses basic results and techniques from algebraic number theory, in particular the theory of cyclotomic fields, as well as Gauss-Jacobi sums. I wonder whether such ideas can be used to devise a different and faster deterministic polynomial-time algorithm for primality testing. 

Cryptography: One-way functions and pseudorandom generators
Reading:
  1. Chapters 2 and 3 of the book Foundations of Cryptography by Oded Goldreich.
  2. See also Chapter 10 of Arora-Barak. 

Cryptography: Zero-knowledge proofs
Reading:
  1. Chapter 4 of the book Foundations of Cryptography by Oded Goldreich. 

Average-Case Complexity
Reading:
  1. A. Bogdanov and L. Trevisan. Average-Case Complexity.