- Time
- 3:00 - 4:00 PM, Friday, December 3, 2010
- Place
- CSE 305
- Speaker
- Valentine Kabanets, Simon Fraser University
## Abstract

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.