Circuits resilient to short-circuit errors

Klim Efremenko; Bernhard Haeupler; Yael Tauman Kalai; Pritish Kamath; Gillat Kol; Nicolas Resch; Raghuvansh R. Saxena

doi:10.1145/3519935.3520007

Circuits resilient to short-circuit errors

Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

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.

Original language	English (US)
Title of host publication	STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Stefano Leonardi, Anupam Gupta
Publisher	Association for Computing Machinery
Pages	582-594
Number of pages	13
ISBN (Electronic)	9781450392648
DOIs	https://doi.org/10.1145/3519935.3520007
State	Published - Sep 6 2022
Externally published	Yes
Event	54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy Duration: Jun 20 2022 → Jun 24 2022

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Country/Territory	Italy
City	Rome
Period	6/20/22 → 6/24/22

All Science Journal Classification (ASJC) codes

Software

Keywords

Circuit Complexity
Error Resilient Computation
Short Circuit Errors

Access to Document

10.1145/3519935.3520007

Cite this

Efremenko, K., Haeupler, B., Kalai, Y. T., Kamath, P., Kol, G., Resch, N., & Saxena, R. R. (2022). Circuits resilient to short-circuit errors. In S. Leonardi, & A. Gupta (Eds.), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (pp. 582-594). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3519935.3520007

@inproceedings{9e852ca39d3741f18ba2e787c3943ee9,

title = "Circuits resilient to short-circuit errors",

abstract = "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.",

keywords = "Circuit Complexity, Error Resilient Computation, Short Circuit Errors",

author = "Klim Efremenko and Bernhard Haeupler and Kalai, {Yael Tauman} and Pritish Kamath and Gillat Kol and Nicolas Resch and Saxena, {Raghuvansh R.}",

note = "Publisher Copyright: {\textcopyright} 2022 ACM.; 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 ; Conference date: 20-06-2022 Through 24-06-2022",

year = "2022",

month = sep,

day = "6",

doi = "10.1145/3519935.3520007",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "582--594",

editor = "Stefano Leonardi and Anupam Gupta",

booktitle = "STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing",

}

Efremenko, K, Haeupler, B, Kalai, YT, Kamath, P, Kol, G, Resch, N & Saxena, RR 2022, Circuits resilient to short-circuit errors. in S Leonardi & A Gupta (eds), STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 582-594, 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, Rome, Italy, 6/20/22. https://doi.org/10.1145/3519935.3520007

Circuits resilient to short-circuit errors. / Efremenko, Klim; Haeupler, Bernhard; Kalai, Yael Tauman et al.
STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Stefano Leonardi; Anupam Gupta. Association for Computing Machinery, 2022. p. 582-594 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

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 -

Efremenko K, Haeupler B, Kalai YT, Kamath P, Kol G, Resch N et al. Circuits resilient to short-circuit errors. In Leonardi S, Gupta A, editors, STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2022. p. 582-594. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3519935.3520007

Circuits resilient to short-circuit errors

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this