Youtor
A Combinatorial Proof of the ChernoffHoeffding Bound Valentine Kabanets
>> YOUR LINK HERE: ___ http://youtube.com/watch?v=JpGrQQrJ7jI
Valentine Kabanets • Simon Fraser University; Institute for Advanced Study • March 30, 2010 • We give a simple combinatorial proof of the Chernoff-Hoeffding concentration • bound for sums of independent Boolean random variables. Unlike the standard • proofs, our proof does not rely on the method of higher moments, but rather uses • an intuitive counting argument. In addition, this new proof is constructive in the • following sense: if the given random variables fail the concentration bound, then • we can efficiently find a subset of the variables that are statistically dependent. • As easy corollaries, we also get concentration bounds for [0, 1]-valued random • variables, martingales (Azuma’s inequality), and expander walks (from the hitting • property of expander walks). • We also give applications of these concentration results to direct product theorems • in complexity. In many areas of complexity theory, we want to make a somewhat • hard problem into a reliably hard problem. An immediate motivation for this type • of hardness amplification comes from cryptography and security. For example, • CAPTCHAs are now widely used to distinguish human users from artificially • intelligent “bots”. However, current CAPTCHAs are neither impossible for a • bot to solve some significant fraction of the time, nor reliably solved by human • users. Can we make a CAPTCHA both reliably hard for bots and reliably easy • for humans? • The main tools for hardness amplification are direct product theorems, where we • show that a feasible solver’s probability of solving many instances of a problem is • significantly smaller than their probability of solving a single instance. In other • words, if f(x) is hard for a constant fraction of x’s, fk(x1, ..xk) = f(x1) â—¦ f(x2).. â—¦ • f(xk) is hard on almost every tuple x1, ...xk. While intuitive, direct product • theorems are not always true and do not not always have the intuitive parameters • even if true. • We give simple reductions between the different varieties of direct product the- • orems: the xor lemma, standard direct product and thresholded direct product. • (This builds on recent work of Unger). • Joint work with Russell Impagliazzo. • For more videos, visit http://video.ias.edu
#############################
