<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
Given a Boolean circuit C, we wish to convert it to a circuit C′ that computes the same function as C even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs. Can we design such a resilient circuit C′ whose size is roughly comparable to that of C? Prior work gave a positive answer for the special case where C is a formula. We study the general case and show that any Boolean circuit C of size s can be converted to a new circuit C′ of quasi-polynomial size sO(logs) that computes the same function as C even if a 1/51 fraction of the gates on any root-to-leaf path in C′ are short circuited. Moreover, if the original circuit C is a formula, the resilient circuit C′ is of near-linear size s1+є. The construction of our resilient circuits utilizes the connection between circuits and DAG-like communication protocols, originally introduced in the context of proof complexity.
004
004
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |