Andrew Chi-Chih Yao
Foong Frances Yao
Abstract
Let M(m, n) be the minimum number or comparators needed in an (m, n)-merging network. It is shown that M(m, n) ≥ n(lg(m + 1))/2, which implies that Batcher's merging networks are optimal up to a factor of 2 + ε for almost all values of m and n. The limit rm = limn→∞ M(m, n)/n is determined to within 1. It is also proved that M(2, n) = [3n/2].
- 1 BATCHER, K E Sorting networks and their apphcatlons Proc AFIPS 1968 SJCC, Vol 32, AFIPS Press, Montvale, N J , pp 307-314Google Scholar
- 2 FLOYD, R W Permuting reformation in ldeahzed two-level storage In Complexity of Computer Computations, R E Miller and J W Thatcher, Eds, Plenum Press, 1972, pp 105-110Google Scholar
- 3 KNUTH, D E The Art of Computer Programming, Vol 1, 2nd ed Addison-Wesley, Reading, Mass, 1973 Google Scholar
- 4 KNUTH, D E The Art of Computer Programming, Vol 3 Addison-Wesley, Reading, Mass , 1973 Google Scholar
Index Terms
- Lower Bounds on Merging Networks
Recommendations
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
We give a general transformation that turns polynomial-size Frege proofs into subexponential-size AC0-Frege proofs. This indicates that proving truly exponential lower bounds for AC0-Frege is hard, as it is a long-standing open problem to prove ...
Exponential lower bounds for AC0-Frege imply superpolynomial frege lower bounds
ICALP'11: Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part IWe give a general transformation which turns polynomialsize Frege proofs to subexponential-size AC0-Frege proofs. This indicates that proving exponential lower bounds for AC0-Frege is hard, since it is a longstanding open problem to prove super-...
Lower Bounds for Merging Networks
A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging ...
Comments