Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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

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.

Pseudorandom Generators for Regular Branching Programs

Amir Yehudayoff
Institute for Advanced Study
March 16, 2010

We shall discuss new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is (either 0 or) 2. For every width d and length n, the pseudorandom generator uses a seed of length $O((log d + log log n + log(1/p)) log n)$ to produce $n$ bits that cannot be distinguished from a uniformly random string by any regular width $d$ length $n$ read-once branching program, except with probability $p > 0$

A Theory of Cryptographic Complexity

Manoj M. Prabhakaran
University of Illinois at Urbana-Champaign
March 1, 2010

In this talk, I shall describe an ongoing project to develop a complexity theory for cryptographic (multi-party computations. Different kinds of cryptographic computations involve different constraints on how information is accessed. Our goal is to qualitatively -- and if possible, quantitatively -- characterize the "cryptographic complexity" (defined using appropriate notions of reductions) of these different modes of accessing information. Also, we explore the relationship between such cryptographic complexity and computational intractability.