TY - JOUR

T1 - On probabilistic networks for selection, merging, and sorting

AU - Leighton, T.

AU - Ma, Y.

AU - Suel, T.

N1 - Funding Information:
⁄The first author was supported by ARPA Contracts N00014-91-J-1698 and N00014-92-J-1799. The second author’s work was done while at Stanford University supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship, and while at MIT supported by ARPA Contracts N00014-91-J-1698 and N00014-92-J-1799. The work of the third author was done while at the NEC Research Institute, and while at the University of Texas at Austin supported by the Texas Advanced Research Program under Grant No. ARP-93-003658-461.

PY - 1997

Y1 - 1997

N2 - We study comparator networks for selection, merging, and sorting that output the correct result with high probability, given a random input permutation. We prove tight bounds, up to constant factors, on the size and depth of probabilistic (n, k)-selection networks. In the case of (n, n/2)-selection, our result gives a somewhat surprising bound of Θ(n log log n) on the size of networks of success probability in [δ, 1 - 1/poly (n)], where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size Θ(n log n). We also prove tight bounds, up to lower-order terms, on the size and depth of probabilistic merging networks of success probability in [δ, 1 - 1/poly(n)], where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least 1 - 1/poly(n) and nearly logarithmic depth.

AB - We study comparator networks for selection, merging, and sorting that output the correct result with high probability, given a random input permutation. We prove tight bounds, up to constant factors, on the size and depth of probabilistic (n, k)-selection networks. In the case of (n, n/2)-selection, our result gives a somewhat surprising bound of Θ(n log log n) on the size of networks of success probability in [δ, 1 - 1/poly (n)], where δ is an arbitrarily small positive constant, thus comparing favorably with the best previously known solutions, which have size Θ(n log n). We also prove tight bounds, up to lower-order terms, on the size and depth of probabilistic merging networks of success probability in [δ, 1 - 1/poly(n)], where δ is an arbitrarily small positive constant. Finally, we describe two fairly simple probabilistic sorting networks of success probability at least 1 - 1/poly(n) and nearly logarithmic depth.

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

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

U2 - 10.1007/s002240000068

DO - 10.1007/s002240000068

M3 - Article

AN - SCOPUS:0031260812

VL - 30

SP - 559

EP - 582

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 6

ER -