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 {\em somewhat} hard problem into a {\em reliably} hard problem. An immediate motivation for this type of {\em 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 {\em 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) \circ f(x_2)..\circ 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 theorems: the xor lemma, standard direct product and thresholded direct product. (This builds on recent work of Unger).
Joint work with Russell Impagliazzo.