# Circuits resilient to short-circuit errors

## Author(s): Efremenko, Klim; Haeupler, Bernhard; Kalai, Yael Tauman; Kamath, Pritish; Kol, Gillat; et al

DownloadTo refer to this page use:

`http://arks.princeton.edu/ark:/88435/pr15m62696`

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. |

Publication Date: | Jun-2022 |

Citation: | Efremenko, Klim, Haeupler, Bernhard, Kalai, Yael Tauman, Kamath, Pritish, Kol, Gillat, Resch, Nicolas and Saxena, Raghuvansh R. "Circuits resilient to short-circuit errors." Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (2022): 582-594. doi:10.1145/3519935.3520007 |

DOI: | 10.1145/3519935.3520007 |

Pages: | 582 - 594 |

Type of Material: | Conference Article |

Series/Report no.: | STOC 2022; |

Journal/Proceeding Title: | Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing |

Version: | Author's manuscript |

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.