Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SHORT-CIRCUIT ERRORS:
Reports tagged with Short-circuit errors:
TR25-013 | 18th February 2025
Raghuvansh Saxena, Yael Tauman Kalai

Polynomial Size, Short-Circuit Resilient Circuits for NC

We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to $\epsilon d$ gates on every root-to-leaf path ... more >>>




ISSN 1433-8092 | Imprint