Circuits Resilient to Short-Circuit Errors - Efremenko, Klim; Haeupler, Bernhard; Kalai, Yael Tauman; Kamath, Pritish; Kol, Gillat; Resch, Nicolas; Saxena, Raghuvansh (STOC 2022, 2022)
Given a Boolean circuit , we wish to convert it to a circuit that computes the same function as 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 whose size is roughly comparable to that of ? Prior work [KLR12, BEGY19] gave a positive answer for the special case where is a formula. We study the general case and show that any Boolean circuit of size can be converted to a new circuit of quasi-polynomial size that computes the same function as even if a 1/51 fraction of the gates on any root-to-leaf path in are short circuited. Moreover, if the original circuit is a formula, the resilient circuit is of near-linear size . 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.