### 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 2^{O}(√lg lg n) lg n have been discovered. These networks are the only known sorting networks of depth o(lg^{2}n) 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.

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings |

Editors | Serge Abiteboul, Eli Shamir |

Publisher | Springer Verlag |

Pages | 618-629 |

Number of pages | 12 |

ISBN (Print) | 9783540582014 |

DOIs | |

State | Published - 1994 |

Event | Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 - Jerusalem, Isr Duration: Jul 1 1994 → Jul 1 1994 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 820 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 |
---|---|

City | Jerusalem, Isr |

Period | 7/1/94 → 7/1/94 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'A super-logarithmic lower bound for hypercubic sorting networks'. Together they form a unique fingerprint.

## Cite this

*Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings*(pp. 618-629). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 820 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-58201-0_103