activity
20142016
most citedTwenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)

39 citations · 42 across the 4 of their papers we have counts for

collaborators

5 papers

cs.DS2016

Logic Programming with Graph Automorphism: Integrating naut with Prolog (Tool Description)

Michael Frank, Michael Codish

This paper presents the plnauty~library, a Prolog interface to the nauty graph-automorphism tool. Adding the capabilities of nauty to Prolog combines the strength of the "generate…

cs.AI2015★ 1 cited

Computing the Ramsey Number R(4,3,3) using Abstraction and Symmetry breaking

Michael Codish, Michael Frank, Avraham Itzhakov +1

The number is often presented as the unknown Ramsey number with the best chances of being found "soon". Yet, its precise value has remained unknown for almost 50 years.…

cs.CC2015

When Six Gates are Not Enough

Michael Codish, Luís Cruz-Filipe, Michael Frank +1

We apply the pigeonhole principle to show that there must exist Boolean functions on 7 inputs with a multiplicative complexity of at least 7, i.e., that cannot be computed with onl…

cs.AI2014★ 2 cited

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…

cs.DM2014★ 39 cited

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…