Chernoff's bound states that for any A⊂[N] the probability a
random k-tuple s∈([N]k) correctly `samples' A (i.e. that the
density of A in s is close to its mean) decays exponentially in the
dimension k. In 1987, Ajtai, Komlos, and Szemeredi proved...
