39 citations · 161 across the 21 of their papers we have counts for
6 papers · 1 filter
Optimal-Depth Sorting Networks
Daniel Bundala, Michael Codish, Luís Cruz-Filipe +2
We solve a 40-year-old open problem on the depth optimality of sorting networks. In 1973, Donald E. Knuth detailed, in Volume 3 of "The Art of Computer Programming", sorting networ…
Sorting Networks: the End Game
Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp
This paper studies properties of the back end of a sorting network and illustrates the utility of these in the search for networks of optimal size or depth. All previous works focu…
Solving Graph Coloring Problems with Abstraction and Symmetry
Michael Codish, Michael Frank, Avraham Itzhakov +1
This paper introduces a general methodology, based on abstraction and symmetry, that applies to solve hard graph edge-coloring problems and demonstrates its use to provide further…
Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)
Michael Codish, Luís Cruz-Filipe, Michael Frank +1
This paper describes a computer-assisted non-existence proof of nine-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found…
The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes
Michael Codish, Luis Cruz-Filipe, Peter Schneider-Kamp
Previous work identifying depth-optimal -channel sorting networks for is based on exploiting symmetries of the first two layers. However, the naive generate-an…
Boolean Equi-propagation for Concise and Efficient SAT Encodings of Combinatorial Problems
Amit Metodi, Michael Codish, Peter James Stuckey
We present an approach to propagation-based SAT encoding of combinatorial problems, Boolean equi-propagation, where constraints are modeled as Boolean functions which propagate inf…