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 proceedingConference contribution

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 languageEnglish (US)
Title of host publicationSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
EditorsStefano Leonardi, Anupam Gupta
PublisherAssociation for Computing Machinery
Pages582-594
Number of pages13
ISBN (Electronic)9781450392648
DOIs
StatePublished - Sep 6 2022
Event54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy
Duration: Jun 20 2022Jun 24 2022

Publication series

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

Conference

Conference54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Country/TerritoryItaly
CityRome
Period6/20/226/24/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Circuit Complexity
  • Error Resilient Computation
  • Short Circuit Errors

Fingerprint

Dive into the research topics of 'Circuits resilient to short-circuit errors'. Together they form a unique fingerprint.

Cite this