Michael Viderman

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)

proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of ...
more >>>

Chin Ho Lee, Emanuele Viola

We exhibit $\epsilon$-biased distributions $D$

on $n$ bits and functions $f\colon \{0,1\}^n

\to \{0,1\}$ such that the xor of two independent

copies ($D+D$) does not fool $f$, for any of the

following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is ... more >>>

Joshua Cook, Dana Moshkovitz

Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient randomized decoders that run in time $n^{1+o(1)}$ and space $n^{o(1)}$. In this work we focus on deterministic decoding.

Gronemeier showed that any non-adaptive deterministic decoder for a good code running ...
more >>>