Douglas R. Stinson

In this primarily expository

paper, we discuss the connections between two popular and useful

tools in theoretical computer science, namely,

universal hashing and pairwise

independent random variables; and classical combinatorial stuctures

such as error-correcting codes, balanced incomplete block designs,

difference matrices

...
more >>>

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code

$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,

using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>