1 Search Results for "Yitayew, Michael A."

Document
DOI: 10.4230/LIPIcs.CCC.2019.10
Optimal Short-Circuit Resilient Formulas

Authors: Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

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.
Cite as

Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew. Optimal Short-Circuit Resilient Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{braverman_et_al:LIPIcs.CCC.2019.10,
  author =	{Braverman, Mark and Efremenko, Klim and Gelles, Ran and Yitayew, Michael A.},
  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 =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.10},
  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}
}
  • Refine by Author
  • 1 Braverman, Mark
  • 1 Efremenko, Klim
  • 1 Gelles, Ran
  • 1 Yitayew, Michael A.

  • Refine by Classification
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Interactive computation

  • Refine by Keyword
  • 1 Circuit Complexity
  • 1 Coding Theory
  • 1 Interactive Coding
  • 1 Karchmer-Wigderson Games
  • 1 Noise-Resilient Circuits

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact