TY - GEN

T1 - Computing Boolean functions from multiple faulty copies of input bits

AU - Szegedy, Mario

AU - Chen, Xiaomin

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.

PY - 2002

Y1 - 2002

N2 - Suppose, we want to compute a Boolean function f, but instead of receiving the input, we only get l ϵ-faulty copies of each input bit. A typical solution in this case is to take the majority value of the faulty bits for each individual input bit and apply f on the majority values. We call this the trivial construction. We showt hat if f: {0, 1}n → {0, 1} and ϵ are known, the best construction function, F, is often not the trivial. In particular, in many cases the best F cannot be written as a composition of some functions with f, and in addition it is better to use a randomized F than a deterministic one. We also prove, that the trivial construction is optimal in some rough sense: if we denote by l(f) the number of (Equation Presented) biased copies we need from each input to reliably compute f using the best (randomized) recovery function F, and w e denote by ltriv(f) the analogous number for the trivial construction, then ltriv(f) = Θ(l(f)). Moreover, both quantities are in Θ(log S(f)), where S(f) is the sensitivity of f. A quantity related to l(f) is (Equation Presented) where li is the number of 0.1-biased copies of xi, such that the above number of readings is already sufficient to recover f with high certainty. This quantity was first introduced by Reischuk et al. [14] in order to provide lower bounds for the noisy circuit size of f. In this article we give a complete characterization of (Equation Presented) through a combinatorial lemma, that can be interesting on its own right.

AB - Suppose, we want to compute a Boolean function f, but instead of receiving the input, we only get l ϵ-faulty copies of each input bit. A typical solution in this case is to take the majority value of the faulty bits for each individual input bit and apply f on the majority values. We call this the trivial construction. We showt hat if f: {0, 1}n → {0, 1} and ϵ are known, the best construction function, F, is often not the trivial. In particular, in many cases the best F cannot be written as a composition of some functions with f, and in addition it is better to use a randomized F than a deterministic one. We also prove, that the trivial construction is optimal in some rough sense: if we denote by l(f) the number of (Equation Presented) biased copies we need from each input to reliably compute f using the best (randomized) recovery function F, and w e denote by ltriv(f) the analogous number for the trivial construction, then ltriv(f) = Θ(l(f)). Moreover, both quantities are in Θ(log S(f)), where S(f) is the sensitivity of f. A quantity related to l(f) is (Equation Presented) where li is the number of 0.1-biased copies of xi, such that the above number of readings is already sufficient to recover f with high certainty. This quantity was first introduced by Reischuk et al. [14] in order to provide lower bounds for the noisy circuit size of f. In this article we give a complete characterization of (Equation Presented) through a combinatorial lemma, that can be interesting on its own right.

UR - http://www.scopus.com/inward/record.url?scp=23044534750&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044534750&partnerID=8YFLogxK

U2 - 10.1007/3-540-45995-2_47

DO - 10.1007/3-540-45995-2_47

M3 - Conference contribution

AN - SCOPUS:23044534750

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 539

EP - 553

BT - LATIN 2002

A2 - Rajsbaum, Sergio

PB - Springer Verlag

T2 - 5th Latin American Symposium on Theoretical Informatics, LATIN 2002

Y2 - 3 April 2002 through 6 April 2002

ER -