@inproceedings{efremenko2022circuits,
author = {Efremenko, Klim and Haeupler, Bernhard and Kalai, Yael Tauman and Kamath, Pritish and Kol, Gillat and Resch, Nicolas and Saxena, Raghuvansh},
title = {Circuits Resilient to Short-Circuit Errors},
booktitle = {STOC 2022},
year = {2022},
month = {June},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/circuits-resilient-to-short-circuit-errors/},
}