Toward a Lower Bound for Sorting Networks

DOI10.1007/978-1-4684-2001-2_12zbMath1467.68044OpenAlexW997071912MaRDI QIDQ4999428

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (4)

Optimizing a Certified Proof Checker for a Large-Scale Computer-Generated Proof ⋮ Formalizing Size-Optimal Sorting Networks: Extracting a Certified Proof Checker ⋮ Formally proving size optimality of sorting networks ⋮ Sorting nine inputs requires twenty-five comparisons

This page was built for publication: Toward a Lower Bound for Sorting Networks