Parallel selection
Yossi Azar, Nicholas Pippenger
Discrete Applied Mathematics
This paper explores the connections between two areas pioneered by Shannon: the transmission of information with a fidelity criterion, and the realization of Boolean functions by networks and formulae. We study three phenomena: 1. The effect of the relative number of O's and l's in a function's table on its complexity. 2. The effect of the number of unspecified entries in a partially specified function's table on its complexity. 3. The effect of the number of errors allowed in the realization of a function on its complexity. Our main result is a precise version of the following statement: The complexity of approximately realizing a partially specified Boolean function, in whose table a fraction d of the entries are unspecified and a fraction p of the specified entries are l'swith errors allowed in a fraction not more than e of the specified entries, is less by the factor (1 -d) [H(p) - H(e)] (where H(z) = -z log2z -(1 -z) log2 (1 -z) is the binary entropy function) than the complexity of exactly realizing an arbitrary fully specified Boolean function. We also give an intuitively appealing information-theoretic interpretation of the result. © 1977 Springer-Verlag New York Inc.
Yossi Azar, Nicholas Pippenger
Discrete Applied Mathematics
Maria Klawe, Wolfgang J. Paul, et al.
STOC 1984
Nicholas Pippenger
FOCS 1984
Nicholas Pippenger
Journal of Computer and System Sciences