ECCC-Report TR16-166https://eccc.weizmann.ac.il/report/2016/166Comments and Revisions published for TR16-166en-usThu, 09 Mar 2017 20:38:41 +0200
Revision 1
| Optimal Resilience for Short-Circuit Noise in Formulas |
Mark Braverman,
Ran Gelles,
Michael A. Yitayew
https://eccc.weizmann.ac.il/report/2016/166#revision1
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.Thu, 09 Mar 2017 20:38:41 +0200https://eccc.weizmann.ac.il/report/2016/166#revision1
Paper TR16-166
| Optimal Resilience for Short-Circuit Noise in Formulas |
Mark Braverman,
Ran Gelles,
Michael A. Yitayew
https://eccc.weizmann.ac.il/report/2016/166We 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).Tue, 01 Nov 2016 13:14:52 +0200https://eccc.weizmann.ac.il/report/2016/166