TY - GEN

T1 - Circuits resilient to short-circuit errors

AU - Efremenko, Klim

AU - Haeupler, Bernhard

AU - Kalai, Yael Tauman

AU - Kamath, Pritish

AU - Kol, Gillat

AU - Resch, Nicolas

AU - Saxena, Raghuvansh R.

N1 - Publisher Copyright:
© 2022 ACM.

PY - 2022/9/6

Y1 - 2022/9/6

N2 - 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. Can we design such a resilient circuit C′ whose size is roughly comparable to that of C? Prior work 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 sO(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 s1+". The construction of our resilient circuits utilizes the connection between circuits and DAG-like communication protocols, originally introduced in the context of proof complexity.

AB - 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. Can we design such a resilient circuit C′ whose size is roughly comparable to that of C? Prior work 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 sO(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 s1+". The construction of our resilient circuits utilizes the connection between circuits and DAG-like communication protocols, originally introduced in the context of proof complexity.

KW - Circuit Complexity

KW - Error Resilient Computation

KW - Short Circuit Errors

UR - http://www.scopus.com/inward/record.url?scp=85132689174&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132689174&partnerID=8YFLogxK

U2 - 10.1145/3519935.3520007

DO - 10.1145/3519935.3520007

M3 - Conference contribution

AN - SCOPUS:85132689174

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 582

EP - 594

BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Leonardi, Stefano

A2 - Gupta, Anupam

PB - Association for Computing Machinery

T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022

Y2 - 20 June 2022 through 24 June 2022

ER -