Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-013 | 18th February 2025 11:59

Polynomial Size, Short-Circuit Resilient Circuits for NC

RSS-Feed




TR25-013
Authors: Raghuvansh Saxena, Yael Tauman Kalai
Publication: 18th February 2025 16:12
Downloads: 74
Keywords: 


Abstract:

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 are short-circuited, i.e., their output is replaced with the value of one of its inputs, where $d$ is the depth of the circuit and $\epsilon > 0$ is a fixed constant.

Previously, such a result was known for formulas (Kalai-Lewko-Rao, FOCS 2012). It was also known how to convert general circuits to error resilient ones whose size is quasi-polynomial in the size of the original circuit (Efremenko et al.~STOC 2022). The reason both these works do not extend to our setting is that there may be many paths from the root to a given gate, and the resilient circuits needs to "remember" a lot of information about these paths, which causes it to be large. Our main idea is to reduce the amount of this information at the cost of increasing the depth of the resilient circuit.



ISSN 1433-8092 | Imprint