Optimal short-circuit resilient formulas

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

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

1 Scopus citations


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
StatePublished - Jul 1 2019
Externally publishedYes
Event34th Computational Complexity Conference, CCC 2019 - New Brunswick, United States
Duration: Jul 18 2019Jul 20 2019

Publication series

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


Conference34th Computational Complexity Conference, CCC 2019
Country/TerritoryUnited States
CityNew Brunswick

All Science Journal Classification (ASJC) codes

  • Software


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


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

Cite this