Recovering from Adversarial Error in Boolean Circuits

We consider two different models for adversarial errors 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−ϵ) 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.