TY - GEN
T1 - Optimal short-circuit resilient formulas
AU - Braverman, Mark
AU - Efremenko, Klim
AU - Gelles, Ran
AU - Yitayew, Michael A.
N1 - Funding Information:
Funding Mark Braverman: Supported in part by an NSF CAREER award (CCF-1149888), NSF CCF-1525342, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Klim Efremenko: Supported in part by the Israel Science Foundation (ISF) through grant No. 1456/18. Ran Gelles: Supported in part by the Israel Science Foundation (ISF) through grant No.1078/17.
Funding Information:
Mark Braverman: Supported in part by an NSF CAREER award (CCF-1149888), NSF CCF-1525342, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. Klim Efremenko: Supported in part by the Israel Science Foundation (ISF) through grant No. 1456/18. Ran Gelles: Supported in part by the Israel Science Foundation (ISF) through grant No. 1078/17.
Publisher Copyright:
© Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew; licensed under Creative Commons License CC-BY 34th Computational Complexity Conference (CCC 2019).
PY - 2019/7/1
Y1 - 2019/7/1
N2 - 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.
AB - 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.
KW - Circuit complexity
KW - Coding theory
KW - Interactive coding
KW - Karchmer-Wigderson games
KW - Noise-resilient circuits
UR - http://www.scopus.com/inward/record.url?scp=85070725359&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070725359&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CCC.2019.10
DO - 10.4230/LIPIcs.CCC.2019.10
M3 - Conference contribution
AN - SCOPUS:85070725359
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th Computational Complexity Conference, CCC 2019
A2 - Shpilka, Amir
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th Computational Complexity Conference, CCC 2019
Y2 - 18 July 2019 through 20 July 2019
ER -