Optimal short-circuit resilient formulas

Mark Braverman, Klim Efremenko, Ran Gelles, Michael A. Yitayew

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate’s inputs. A recent result by Kalai et al. [FOCS 2012] converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction 1/6 of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction 1/5 of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction 1/5 of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.

Original languageEnglish (US)
Title of host publication34th Computational Complexity Conference, CCC 2019
EditorsAmir Shpilka
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771160
DOIs
StatePublished - Jul 1 2019
Event34th Computational Complexity Conference, CCC 2019 - New Brunswick, United States
Duration: Jul 18 2019Jul 20 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume137
ISSN (Print)1868-8969

Conference

Conference34th Computational Complexity Conference, CCC 2019
CountryUnited States
CityNew Brunswick
Period7/18/197/20/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Circuit complexity
  • Coding theory
  • Interactive coding
  • Karchmer-Wigderson games
  • Noise-resilient circuits

Fingerprint Dive into the research topics of 'Optimal short-circuit resilient formulas'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Efremenko, K., Gelles, R., & Yitayew, M. A. (2019). Optimal short-circuit resilient formulas. In A. Shpilka (Ed.), 34th Computational Complexity Conference, CCC 2019 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 137). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CCC.2019.10