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

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₁, ..x_k) = f(x₁) â—¦ f(x₂).. â—¦
f(x_k) is hard on almost every tuple x₁, ...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.