License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2019.10
URN: urn:nbn:de:0030-drops-108326
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10832/
Go to the corresponding LIPIcs Volume Portal

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

Optimal Short-Circuit Resilient Formulas

pdf-format:
LIPIcs-CCC-2019-10.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{braverman_et_al:LIPIcs:2019:10832,
  author =	{Mark Braverman and Klim Efremenko and Ran Gelles and Michael A. Yitayew},
  title =	{{Optimal Short-Circuit Resilient Formulas}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Amir Shpilka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10832},
  URN =		{urn:nbn:de:0030-drops-108326},
  doi =		{10.4230/LIPIcs.CCC.2019.10},
  annote =	{Keywords: Circuit Complexity, Noise-Resilient Circuits, Interactive Coding, Coding Theory, Karchmer-Wigderson Games}
}

Keywords: Circuit Complexity, Noise-Resilient Circuits, Interactive Coding, Coding Theory, Karchmer-Wigderson Games
Collection: 34th Computational Complexity Conference (CCC 2019)
Issue Date: 2019
Date of publication: 16.07.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI