Toward a lower bound for sorting networks

DOI10.1007/978-1-4684-2001-2_12MaRDI QIDQ4999428zbMATH OpenOpenAlexFDO

Authors David C. van Voorhis

Publication date 6 July 2021

Published in Complexity of Computer Computations (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-1-4684-2001-2_12

Mathematics Subject Classification ID

Searching and sorting (68P10) Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1263220
• A Lower Bound on the Size of Shellsort Sorting Networks
• Area efficient layouts of the Batcher sorting networks
• Minimum Storage Sorting Networks
• Bitonic sorters of minimal depth

Cited in

(12)

• Formally proving size optimality of sorting networks
• Lower bounds for merging networks
• Formalizing size-optimal sorting networks: extracting a certified proof checker
• New Bounds on Optimal Sorting Networks
• Optimizing a Certified Proof Checker for a Large-Scale Computer-Generated Proof
• The Complexity of Sorting with Networks of Stacks and Queues
• On the analysis of sorting networks from the viewpoint of circuit theory
• A super-logarithmic lower bound for hypercubic sorting networks
• Improved sorting networks with O(log N) depth
• Constructing sorting networks from k-sorters
• Sorting nine inputs requires twenty-five comparisons
• Bounds on the size of test sets for sorting and related networks

This page was built for publication: Toward a lower bound for sorting networks

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