Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-166 | 9th March 2017 20:38

Optimal Resilience for Short-Circuit Noise in Formulas

RSS-Feed




Revision #1
Authors: Mark Braverman, Ran Gelles, Michael A. Yitayew
Accepted on: 9th March 2017 20:38
Downloads: 804
Keywords: 


Abstract:

Paper is withdrawn due to an error. Claim 3.6 of the previous version has a mistake in its proof. As a consequence, Theorem 1.1 is incorrect.


Paper:

TR16-166 | 1st November 2016 09:47

Optimal Resilience for Short-Circuit Noise in Formulas





TR16-166
Authors: Mark Braverman, Ran Gelles, Michael A. Yitayew
Publication: 1st November 2016 13:14
Downloads: 1261
Keywords: 


Abstract:

We show an efficient method for converting a logic circuit of gates with fan-out 1 into an equivalent circuit that works even if some fraction of its gates are short-circuited, i.e., their output is short-circuited to one of their inputs. Our conversion can be applied to any circuit with fan-in $k \ge 2$, yielding a resilient circuit whose size is polynomial in the size of the (non-resilient) input circuit.

The resilient circuit gives the correct output as long as less than 1/3 of the gates in any of its input-to-output paths are corrupted. Furthermore, we prove that a resilience level of 1/3 is optimal (maximal) for this type of faulty gates. This fully answers an open question by Kalai et al. (FOCS 2012).



ISSN 1433-8092 | Imprint