Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with error-correcting code:
TR95-052 | 4th October 1995
Douglas R. Stinson

On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

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

TR11-150 | 4th November 2011
Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

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

ISSN 1433-8092 | Imprint