Optimal Short-Circuit Resilient Formulas

Mark Braverman, Klim Efremenko, Ran Gelles +1

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) convert…