PhD CS – Theory Body of Knowledge


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.


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


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

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