PhD CS – Theory Body of Knowledge

Algorithms

Randomized Algorithms

Principal Source: Motwani and Raghavan, Randomized Algorithms

Original Papers:

• 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).

Approximation Algorithms

Principal Source: Vazirani, Approximation Algorithms

Original Papers:

• 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.

Cryptography

• 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  
• M. Bellare and P. Rogaway's lecture notes
  Especially Chapters 1 (Introduction) and 3 (Pseudorandom Functions)

Complexity

Principal Sources:

• 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 AC⁰ 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.

Uniform complexity

• 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 Σ₂∩Π₂
• 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.