Course Overview

Post date: Jun 14, 2010 9:16:53 AM

We will cover basic paradigms, techniques to analyze randomized

algorithms, as well as applications, in an intermingled fashion.

Any such course can only cover a part of this field, and the

contents of this course are somewhat biased according to my taste.

The syllabus is broadly as follows; some of the material will be

determined according to the interests of the class.

Basic probability: the power of the linearity of expectation,

conditional probability, truncated inclusion-exclusion, some

common distributions;

Paradigms underlying randomized algorithms, including: abundance of

witnesses, symmetry-breaking, random sampling, and the probabilistic

method;

Randomized complexity classes;

Large-deviation bounds (showing that certain types of random variables

are typically very close to their expected value--such bounds are

of much use in analyzing randomized algorithms);

The method of conditional probabilities (converting certain classes

of randomized algorithms into efficient deterministic algorithms);

The Lovasz Local Lemma (a powerful tool to prove the existence of

some very low-probability events, with interesting applications,

e.g., to packet routing in networks);

Randomized approximation algorithms;

The FKG and Janson inequalities, and the Poisson paradigm (with

applications, e.g., to Steiner problems in networks);

Random graphs and expanders;

Applications: load-balancing, distributed contention resolution,

low-congestion routing in networks, network design etc.