- About the College
- Future Students
- Current Students
PhD CS – Theory Body of Knowledge
Principal Source: Motwani and Raghavan, Randomized Algorithms
- R. Karp and M. Luby, Approximation of number of solutions to DNF, J. Complexity, 1985.
- N. Alon, Expanders, Combinatorica, 1986.
- M. Jerrum and A. Sinclair, Approximating the Permanent, SICOMP 1989.
- D. Karger, Randomized min-cut, (see Karger and Stein, J. ACM., 1996).
Principal Source: Vazirani, Approximation Algorithms
- Leighton and Rao, An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problem, JACM 1999.
- Goemans and Williamson, Semidefinite programming for Max-Cut, JACM 1995.
- M. Goemans and D. Williamson, Primal-dual Approximation Algorithms for Constrained Forest Problems, SICOMP, 1995.
- O. Goldreich, Foundations of Cryptography;
Especially Sections 2.1-2.5, 3.1-3.6, 4.1-4.5, 4.7, 5.1-5.3, 6.1-6.4, 7.1
Especially Chapters 1 (Introduction) and 3 (Pseudorandom Functions)
- M. Sipser, Introduction to the theory of computation
- C. Papadimitriou, Computational Complexity
- Web resources: Lecture notes on computational complexity theory
- Original papers and surveys
Circuits: Lower Bounds and Characterizations
- Monotone circuits for Clique require exponential size by Razborov.
- Parity is not in AC0 by Hastad.
- Karp and Lipton, NP is in P/Poly implies that PH collapses to the second level.
Interactive Proof Systems
- Basics of PCP theorem and applications to hardness of approximation
- IP = PSPACE by Shamir.
- AM protocol for Graph Non-Isomorphism:
S. Goldwasser and M. Sipser. Private Coins versus Public Coins in Interactive Proof Systems. STOC 1986.
- Permanent is #P-Complete by L. Valiant.
- Toda's Theorem: PH is contained in P#P.
- Nondeterministic logarithmic space is closed under complement.
Probabilistic Computations and Derandomization
- Error amplification using random walks on expanders. Chapter 15 in Luby-Wigderson's notes on Pairwise Independence and Derandomization.
- BPP is contained in Σ2∩Π2
- Valiant-Vazirani: SAT is random reducible to Unique-SAT.
- RL is contained in SC by Nisan, and the precursor:
N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica 12(4): 449-461 (1992).
- Nisan and Wigderson, Hardness versus Randomness, Journal of Computer and System Science, Vol. 49, 149-167, 1994.