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(logs)}\) 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+e}\). 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.