From: Ashish Sabharwal (ashish@cs.washington.edu)
Date: Mon Jan 12 2004 - 15:45:05 PST
UW CSE Theory Seminar: A Theorist's Toolkit
TIME : Tuesday, Jan 13, 1:30-2:20 pm
PLACE : EE1 037
SPEAKER: Ashish Sabharwal
TITLE : Probabilistic Tail Bounds and Pairwise Independence
ABSTRACT: 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.
-------------------
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Mon Jan 12 2004 - 15:45:16 PST