TR22-050 Authors: Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

Publication: 17th April 2022 16:20

Downloads: 171

Keywords:

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+\epsilon}$. 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.