Circuits resilient to short-circuit errors
METADATA ONLY
Loading...
Author / Producer
Date
2022-06
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
582 - 594
Publisher
Association for Computing Machinery
Event
54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Error resilient computation; Short circuit errors; Circuit complexity
Organisational unit
08730 - Gruppe Häupler / Group Häupler