# School of Mathematics

## 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.

## Product Rules in Semidefinite Programming

## Pseudorandom Generators for Regular Branching Programs

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$

## Extremal Problems for Convex Lattice Polytopes

In this survey I will present several extremal problems, and some solutions, concerning convex lattice polytopes.

A typical example is to determine the smallest area that a convex lattice polygon can have if it has exactly n vertices.

## Behavioral Experiments in Strategic Networks

## Computational Complexity and Information Asymmetry in Financial Products

Collateralized Default Obligations (CDOs) and related financial derivatives have been at the center of the last financial crisis and subject of ongoing regulatory overhaul.

## A Theory of Cryptographic Complexity

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.