Short-Circuit Error Resilience in Boolean Formulas

Abstract

We investigate the problem of computing on boolean formulas in the presence of short circuit errors; these are errors that replace the output value of a gate by one of its input values. We show that any boolean formula F that computes a function f can be converted into a formula E that computes f even if up to ( 1 3 - ) of E's gates on each input to output path are short-circuited, for any > 0. The short-circuited gates and the exact errors may be chosen adversarily and may depend on input with no restriction. The size of E will be polynomial in the size of F, with dependence on . We also show that there is a function f such that no formula can compute f and tolerate 1 3 of its gates per input-to-output path being corrupted. This answers the question posed by Kalai et al[1] of nding the maximum constant fraction of short-circuit errors that can be tolerated per path in a formula, and improves their resilience factor of ( 1 10 - ). We obtain these results by showing a tight, error resilient version of the Karchmer-Wigderson connection between formulas and communication protocols, and applying this connection to recent results from interactive communication. 2