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, f^{k}(x_{1}, ..x_{k}) = f(x_{1}) â—¦ f(x_{2}).. â—¦

f(x_{k}) is hard on almost every tuple x_{1}, ...x_{k}. 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.

# A Combinatorial Proof of the Chernoff-Hoeffding Bound, With Applications to Direct-Product Theorems

Valentine Kabanets

Simon Fraser University; Institute for Advanced Study

March 30, 2010