## Abstract

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 show that if f:{0,1}^{n}→{0,1} and are known, the best function construction, F, is often not the trivial one. In particular, in many cases the best F cannot be written as a composition of f with some functions, 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 110-biased copies we need from each input to reliably compute f using the best (randomized) recovery function F, and we denote by l_{triv}(f) the analogous number for the trivial construction, then l_{triv}(f)=Θ(l(f)). Moreover, both quantities are in Θ(logS(f)), where S(f) is the sensitivity of f. A quantity related to l(f) is D_{stat,}^{rand}(f)=min∑ _{i=1}^{n}l_{i}, where l_{i} is the number of 110-biased copies of x_{i} such that the above number of readings is sufficient to recover f with high probability. This quantity was first introduced by Reischuk and Schmeltz [14] in order to provide lower bounds for the noisy circuit size of f. In this article we give a complete characterization of D_{stat,}^{rand}(f) through a combinatorial lemma that can be interesting on its own right.

Original language | English (US) |
---|---|

Pages (from-to) | 149-170 |

Number of pages | 22 |

Journal | Theoretical Computer Science |

Volume | 321 |

Issue number | 1 |

DOIs | |

State | Published - Jun 16 2004 |

Event | Latin American Theoretical Informatics - Cancun, Mexico Duration: Apr 3 2002 → Apr 6 2002 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Keywords

- Boolean functions
- Linear programming
- Randomized functions
- Sensitivity