CSE P 590B Project

Spring 2006

The purpose of the project is to read original papers of some importance from the computational complexity literature and explain the results in a 20 minute talk at the end of the quarter. Some of these papers are quite difficult, and others are covered somewhat thoroughly in class. If you choose to work as a team of two, the talk will be 40 minutes.

1. NP-completeness

Steve Cook, The Complexity of Theorem-Proving Procedures <http://doi.acm.org/10.1145/800157.805047>, STOC 1971.
Richard Karp, Reducibility Among Combinatorial Problems, Proceedings of a Symposium on the Complexity of Computer Computations, 1972.
R. Ladner, On the Structure of Polynomial Time Reducibility <http://doi.acm.org/10.1145/321864.321877>, JACM 1975.
See Sipser , Chapter 7.3 - 5

2. Randomized Computation

J. Gill, Computational Complexity of Probabilistic Turing Machines, SIAM Journal on Computing, V.6(4), 675-695, 1977.
R. Motwani, P. Raghavan, Randomized Algorithms, Cambridge Press, 1995.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l7.ps
<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l7.ps>
See Sipser, Chapter 10.2

3. The Polynomial-Time Hierarchy

L. J. Stockmeyer, The Polynomial-Time Hierarchy, Theoretical Computer Science, V.3, 1-22, 1977.
A. K. Chandra, D. C. Kozen, L. J. Stockmeyer, Alternation, JACM, V.28, 114-133, 1981.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l9.ps
<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l9.ps>
See Sipser, Chapter 10.3

4. Interactive Proofs

S. Goldwasser, S. Micali, C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, SICOMP, V18, 186-208, 1989.
C. Lund, L. Fortnow, H. J. Karloff, N. Nisan, Algebraic Methods for Interactive Proof Systems, FOCS 1990, 2-10.
A. Shamir, IP=PSPACE, FOCS 1990, 11-15.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l11.ps
<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l11.ps>
See Sipser, Chapter 10.3

5. Public-Coin Interactive Proofs

L. Babai, Trading Group Theory for Randomness, STOC 1985, 421-429.
S. Goldwasser, M. Sipser, Private Coins versus Public Coins in Interactive Proof Systems, STOC 1986, 59-68.

6. Zero-Knowledge Proofs

S. Goldwasser, S. Micali, C. Rackoff, The Knowledge Complexity of Interactive Proof Systems, SICOMP, V18, 186-208, 1989.
O. Goldreich, S. Micali, A. Wigderson, Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems, JACM, V.38(3), 691-729, 1991.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l24.ps
<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l24.ps>
See Sipser, Chapter 10.4

7. Probabilistic Checkable Proof (PCP)

S. Arora, S. Safra, Probabilistic Checking of Proofs; A New Characterization of NP, FOCS 1992, 2-13.
S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof Verification and Hardness of Approximation Problems, FOCS 1992, 14-23.
I. Dinur, The PCP Theorem by Gap Amplification, STOC 2006.
Goldreich's lecture notes:
http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l12.ps
<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l12.ps>

8. Hardness of Approximation

U. Feige, S. Goldwasser, L. Lovasz, S. Safra, M. Szegedy, Interactive Proofs and the Hardness of Approximating Cliques, JACM, V.43(2), 268-292, 1996.
J. Hastad, Clique is Hard to Approximate Within n^1 -epsilon , FOCS 1996, 627-636.
D. Hochbaum, Approximation Algorithms for NP-Hard Problems, Wadsworth Publishing Company, 1996.
See Sipser, Chapter 10.1

9. Circuit Depth and Space Complexity

A. Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6:733-744, 1977.
S. A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, Vol. 64, Nos. 1-3, 1985.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l29.ps
<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l29.ps>
See Sipser, Chapter 9.3

10. #P Complexity

L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189--201, 1979.
L. Stockmeyer. The Complexity of Approximate Counting. STOC 1983.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l10.ps
<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l10.ps>

11. Non-Uniform Polynomial Time

R.M. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. STOC 1980, 302—309.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l8.ps<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l8.ps>

12. Polynomial Space

W. Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities, Journal of Computer and System Sciences, 1970.
L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time. STOC 1973, 1-9.
R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--103. 1972.
T. J. Schaefer, On the Complexity of Some Two-Person Perfect-Information Games, J. Comput. System Sci., 16 (1978), pp. 185--225.
See Sipser, Chapter 8.1 - 3

13. Relativization

T. Baker, J. Gill, R. Solovay, Relativization of the P=?NP Question, SICOMP, V.4(4), 431-442, 1975.
C. Bennett, J. Gill, Relative to a Random Oracle A, P^A≠NP^A ≠coNP^A with Probability one, SICOMP, V.10(1), 96-113, 1981.
Goldreich's lecture notes: http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l33.ps<http://www.wisdom.weizmann.ac.il/%7Eoded/PS/CC/l33.ps>
See Sipser, Chapter 9.2

14. Complexity of Logic

M. J. Fischer and M. O. Rabin. Super-exponential complexity of Presburger arithmetic. In Complexity of Computation, volume VII of SIAM-AMS Proceedings, pages 27–41. American Mathematical Society, 1974.
M. J. Fischer and R. E. Ladner. Propositional dynamic logic of regular programs. J. Comput.Syst. Sci., 18(2):194–211, 1979.
See Sipser, Chapter 6.2

15. Information Complexity

Ming Li, Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1997.
Peter Grunwald, Paul Vitanyi, Shannon Information and Kolmogorov Complexity. Available at http://arxiv.org/pdf/cs.IT/0410002
See Sipser, Chapter 6.4.

16. Quantum Computing

Jacob West, The Quantum Computer. http://www.cs.caltech.edu/~westside/quantum-intro.html
P. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, FOCS 1994.
A. Ekert and R. Jozsa, Quantum Computation and Shor's Factoring Algorithm, Review of Modern Physics, 68, 733-753, 1996.
Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000.

17. History of Computing

The Universal Computer by Martin Davis
Algorithmics: The Spirit of Computing by David Harel
The New Turing Omnibus: Sixty-six Excursions in Computer Science by A.K. Dewdney