For every $0 < R < 1$ and $\eps > 0$, we present an explicit
construction of error-correcting codes of rate $R$ that can be list
decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.
These codes achieve the ``capacity'' for decoding from {\em ... more >>>

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with ... more >>>