Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Adversarial noise:
TR05-133 | 17th November 2005
Venkatesan Guruswami, Atri Rudra

Explicit Capacity-Achieving List-Decodable Codes

Revisions: 1

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

TR10-164 | 4th November 2010
Falk Unger

Better gates can make fault-tolerant computation impossible

Revisions: 1

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

ISSN 1433-8092 | Imprint