Name
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 showt hat if f : 0, 1n → 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 1
10-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 Θ(log S(f)), where S(f) is the sensitivity of f. A quantity related to l(f) is D
rand
stat,(f) = min∑n
i=1
l
i, where l
i is the number of 0.1-biased copies of x
i, 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 D
rand
stat,(f) through a combinatorial lemma, that can be interesting on its own right.
|
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.tcs.2003.07.001 | Theoretical Computer Science - Latin American theorotical informatics |
Keywords | Field | DocType |
Boolean function,10-biased copy,best F,best function construction,randomized F,trivial construction,multiple faulty copy,individual input bit,Computing Boolean function,analogous number,input bit,majority value | Boolean function,Discrete mathematics,Combinatorics,Well-defined,Biased Estimation,Completeness (statistics),Deterministic system (philosophy),Lemma (mathematics),Mathematics | Journal |
Volume | Issue | ISSN |
321 | 1 | Theoretical Computer Science |
ISBN | Citations | PageRank |
3-540-43400-3 | 5 | 0.49 |
References | Authors | |
12 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mario Szegedy | 1 | 3358 | 325.80 |
| Xiaomin Chen | 2 | 43 | 6.18 |
| XM Chen | 3 | 5 | 0.49 |