An Improved Lower Bound for Sorting Networks

DOI10.1109/TC.1972.5009021MaRDI QIDQ5646780zbMATH OpenFDO

Authors David C. van Voorhis

Publication date 1972

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TC.1972.5009021

Mathematics Subject Classification ID

Cited in

(5)

• Efficient monotone circuits for threshold functions
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Sorting networks: to the end and back again
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• Sorting nine inputs requires twenty-five comparisons

This page was built for publication: An Improved Lower Bound for Sorting Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5646780)