Prerequisites: A course in Computer Theory
and a course in Analysis of Algorithms.
Description:
Review of elementary complexity theory: Theorems
of Savitch and Immerman/Szelepcsenyi. Las Vegas vs Monte Carlo
probabilistic algorithms. Arthur-Merlin protocols. Game-Theoretic
techniques. The Probabilistic Method. Markov Chains, Random Walks,
Expander Graphs. Algebraic Techniques. PCP and efficient proof
verification. Applications to various problems.
Texts:
R. Motwani and P. Raghavan. Randomized Algorithms.
1995. Cambridge University Press.
N. Alon and J. Spencer. The Probabilistic Method.
2nd Edition. 2001. Wiley.
