Title: Constructive Proofs of Concentration Bounds
Speaker: Russell Impagliazzo, University of California, San Diego
Date: Wednesday, November 10, 2010 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We give simple, combinatorial proofs of various concentration bounds, which say that random variables from certain classes are highly concentrated around their expected values. Examples include Chernoff bounds for the sums of independent random variables, Azuma's inequality for Martingales, and the Chernoff bound for expander walks. Unlike the standard proofs, our proof does not use the method of higher moments, but rather uses a simple reduction from the probability that subsets are entirely one to a concentration bound.
In addition, our proof is constructive in the following sense: if the sum of the given random variables is not concentrated around the expectation, then we can efficiently find (with high probability) a sub- set of the random variables that are positively correlated. This gives a reduction from Thresholded Direct Product theorems to Direct Product Theorems, applicable in almost any context. Informally, a Direct Product Theorem says that the complexity of solving all k instances of a somewhat hard problem increases expo- nentially with k; a Threshold Direct Product Theorem says that it is exponentially hard in k to even solve any fraction of the given k instances of a hard problem significantly larger than for a single instance. Thresholded Direct Product theorems are useful to distinguish between a legitimate user who is imperfect and an attacker that is significantly worse. For example, a human user might be unable to solve CAPTTCHA problems all of the time, but still be significantly better than any AI bot. Thresholded direct products give a way to make the CAPTTCHA both reliably easy for humans and reliably hard for bots. We show the equivalence between optimal Direct Product Theorems and optimal Threshold Direct Product Theo- rems. We also get a simple constructive proof of Unger's result saying that XOR Lemmas imply Threshold Direct Product.
Joint with Valentine Kabanets, SFU