39 citations · 161 across the 21 of their papers we have counts for
5 papers · 1 filter
Breaking Symmetries in Graph Search with Canonizing Sets
Avraham Itzhakov, Michael Codish
There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of th…
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.…
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…
Sorting Networks: to the End and Back Again
Michael Codish, Luís Cruz-Filipe, Thorsten Ehlers +2
This paper studies new properties of the front and back ends of a sorting network, and illustrates the utility of these in the search for new bounds on optimal sorting networks. Se…
Applying Sorting Networks to Synthesize Optimized Sorting Libraries
Michael Codish, Luís Cruz-Filipe, Markus Nebel +1
This paper shows an application of the theory of sorting networks to facilitate the synthesis of optimized general purpose sorting libraries. Standard sorting libraries are often b…