Revision #1 Authors: Mark Braverman, Ran Gelles, Michael A. Yitayew

Accepted on: 9th March 2017 20:38

Downloads: 804

Keywords:

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.

TR16-166 Authors: Mark Braverman, Ran Gelles, Michael A. Yitayew

Publication: 1st November 2016 13:14

Downloads: 1261

Keywords:

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).