@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",

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",

note = "Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 ; Conference date: 01-07-1994 Through 01-07-1994",

}