Princeton University
Computer Science Dept.

Computer Science 593
Advanced Topics in Theory of Algorithms
Probabilistic Techniques

Bernard Chazelle

Fall 1997
Various topics in computational complexity, the analysis of algorithms, and other areas of theoretical computer science. Prerequisite: COS 487 or equivalent.

THE DISCREPANCY METHOD

Discrepancy theory has provided theoretical computer science with tools of stunning power.
What is discrepancy theory? Why is it so useful in complexity theory? These are some of the questions the course will attempt to answer.
Among the topics discussed:
Tail estimates, martingales, bounded independence
Orthogonal functions, Fourier analysis
Extremal graph theory, integral geometry
Pseudo-random number generations, derandomization
Markov chains, expanders, isoperimetric inequalities
Lower bound techniques
Spaces of finite VC dimension
Circuit complexity, communication complexity

Lectures: Friday 1:30--4:50pm, room 301 in Computer Science Building.

Bernard Chazelle, 404 CS Building, 258-5380, chazelle@cs