# Optimal Short-Circuit Resilient Formulas

## Author(s): Braverman, Mark; Efremenko, Klim; Gelles, Ran; Yitayew, Michael A

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1sc17
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorEfremenko, Klim-
dc.contributor.authorGelles, Ran-
dc.contributor.authorYitayew, Michael A-
dc.date.accessioned2021-10-08T19:44:52Z-
dc.date.available2021-10-08T19:44:52Z-
dc.date.issued2019en_US
dc.identifier.citationBraverman, Mark, Klim Efremenko, Ran Gelles, and Michael A. Yitayew. "Optimal Short-Circuit Resilient Formulas." 34th Computational Complexity Conference (CCC) 137 (2019): pp. 10:1--10:22. doi:10.4230/LIPIcs.CCC.2019.10en_US
dc.identifier.issn1868-8969-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1sc17-
dc.description.abstractWe 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.en_US
dc.format.extent10:1--10:22en_US
dc.language.isoen_USen_US
dc.relation.ispartof34th Computational Complexity Conference (CCC)en_US
dc.rightsFinal published version. This is an open access article.en_US
dc.titleOptimal Short-Circuit Resilient Formulasen_US
dc.typeConference Articleen_US
dc.identifier.doi10.4230/LIPIcs.CCC.2019.10-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat