Blog Archives

Chernoff Bound

Consider the sum of a sequence of independent random variables. One may expect its distribution is concentrated around its expected value. This is characterized by the Chernoff bound, which gives exponentially decreasing bounds on tail distributions of the sum. Let

Tagged with:
Posted in Probability

Combinatorial Design and Pseudorandom Generator

For a set of size \(l\), choose \(m\) subsets each of size \(n\) such that each pair of subsets has intersection size at most \(d\). This gives a combinatorial design with parameters \((m,l,n,d)\). That is, we have \(I_1,\ldots, I_m \subseteq

Tagged with: , ,
Posted in Theory