Show simple item record

dc.contributor.authorSchmidt, Jeanette P.en_US
dc.contributor.authorSiegel, Alanen_US
dc.contributor.authorSrinivasan, Aravinden_US
dc.description.abstractChernoff-Hoeffding bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables. We present a simple technique which gives slightly better bounds than these and which, more importantly, requires only limited independence among the random variables, thereby importing a variety of standard results to the case of limited independence for free. Additional methods are also presented, and the aggregate results are very sharp and provide a better understanding of the proof techniques behind these bounds. They also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for jobshop scheduling. The "limited independence" result implies that weaker sources of randomness are sufficient for randomized algorithms whose analyses use the Chernoff-Hoeffding bounds; further, it leads to algorithms that require a reduced amount of randomness for any analysis which uses the Chernoff-Hoeffding bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.en_US
dc.format.extent3073204 bytes
dc.format.extent645694 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleChernoff-Hoeffding Bounds for Applications with Limited Independenceen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record