Title: Recovering from Adversarial Error in Boolean Circuits.

We consider two different models for adversarial errors in circuits
and show how to design circuits that can recover from such errors.

In the first work, we show how to efficiently convert any boolean
formula F into a boolean formula E that is resilient to
short-circuit errors (as introduced by Kleitman et al.). A gate
has a short-circuit error when the value it computes is replaced by
the value of one of its inputs.

We guarantee that E computes the same function as F, as long as at
most (1/10 - epsilon) of the gates on each path from the output to an
input have been corrupted in E. The corruptions may be chosen
adversarially, and may depend on the formula E and even on the input.
We obtain our result by extending the Karchmer-Wigderson connection
between formulas and communication protocols to the setting of
adversarial error. This enables us to obtain error-resilient formulas
from error-resilient communication protocols.

In the second work, we assume that the input has been encoded using a
suitable error correcting code C. We show that given any boolean
circuit F, one can design a layered circuit E such that E applied to
the encoded input produces an output that is close to the error
corrected version of the output of F, as long as at most a constant
fraction of the gates in each layer of the circuit are corrupted (the
corruptions may be arbitrary).

The first result is joint work with Yael Kalai and Allison Lewko. The
second is joint work with Aram Harrow and Matthew Hastings.