@inproceedings{9ebe76bccb9448a58076dd99a0aeb9be,
title = "A super-logarithmic lower bound for hypercubic sorting networks",
abstract = "Hypercubic sorting networks are a class of comparator networks whose structure maps efficiently to the hypercube and any of its bounded degree variants. Recently, n-input hypercubic sorting networks with depth 2O(√lg lg n) lg n have been discovered. These networks are the only known sorting networks of depth o(lg2n) that are not based on expanders, and their existence raises the question of whether a depth of O(lg n) can be achieved by any hypercubic sorting network. In this paper, we resolve this question by establishing an Ω (lg n lg lg n/lg lg lg n) lower bound on the depth of any n-input hypercubic sorting network. Our lower bound can be extended to certain restricted classes of non-oblivious sorting algorithms on hypercubic machines.",
author = "Plaxton, {C. Greg} and Torsten Suel",
note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 ; Conference date: 01-07-1994 Through 01-07-1994",
year = "1994",
doi = "10.1007/3-540-58201-0_103",
language = "English (US)",
isbn = "9783540582014",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "618--629",
editor = "Serge Abiteboul and Eli Shamir",
booktitle = "Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings",
}