@inproceedings{0519928624134980b1ded2a78c3309bf,

title = "Optimal short-circuit resilient formulas",

abstract = "We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate{\textquoteright}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.",

keywords = "Circuit complexity, Coding theory, Interactive coding, Karchmer-Wigderson games, Noise-resilient circuits",

author = "Mark Braverman and Klim Efremenko and Ran Gelles and Yitayew, {Michael A.}",

year = "2019",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.CCC.2019.10",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Amir Shpilka",

booktitle = "34th Computational Complexity Conference, CCC 2019",

address = "Germany",

note = "34th Computational Complexity Conference, CCC 2019 ; Conference date: 18-07-2019 Through 20-07-2019",

}