Ashish Sabharwal
University of Washington

Probabilistic Tail Bounds and Pairwise Independence

Probabilistic reasoning is one of the most important tools in a theorist's toolkit. Starting with basics such as linearity of expectation, the talk will review common distribution tail bounds (Markov's, Chebychev's, Chernoff's), and describe the construction and applications of pairwise independent random variables.

The probabilistic method is often used to prove the existence of combinatorial objects satisfying a desired property (e.g. a max-cut of size at least |E|/2). This is done by simply proving that the average object constructed at random satisfies the property. Tail bounds can sometimes be used to show further that most such random objects do not deviate much from the property, leading to efficient randomized constructions and threshold results. If the construction permits, using pairwise independence can substantially reduce the size of the underlying sample space, resulting in efficient de-randomization. Independent of this, pairwise independence can in general be used to boost the success probability of randomized algorithms without costing too many additional random bits.