Circuits resilient to short-circuit errors

Given a Boolean circuit C, we wish to convert it to a circuit C that computes the same function as C even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we design such a resilient circuit C whose size is roughly comparable to that of C? Prior work [KLR12, BEGY19] gave a positive answer for the special case where C is a formula.

We study the general case and show that any Boolean circuit C of size s can be converted to a new circuit C of quasi-polynomial size s O(log s) that computes the same function as C even if a 1/51 fraction of the gates on any root-to-leaf path in C are short circuited. Moreover, if the original circuit C is a formula, the resilient circuit C is of near-linear size s 1+ . The construction of our resilient circuits utilizes the connection between circuits and dag-like communication protocols [Raz95, Pud10, Sok17], originally introduced in the context of proof complexity.