Algorithms for subitemset isomorphisms and applications to sorting networks

Abstract

Our work, presented in this thesis, is based on our curiosity for proving optimality of sorting networks. The only feasible method (so far) of proving optimality of sorting networks is to derive a so-called 'computer-assisted' proof. That is, running a program which walks through the entire search space, up to theoretically proven reductions, and checks if a sorting network of a given depth exists. Our primary objective is to find new search space reductions and prove them to be mathematically sound. Using our new machinery we derive new algorithms for finding optimal sorting networks. We begin our work by carefully analysing the state of the art approach (more than 25 years old) for proving optimal sorting networks. We develop fundamen tally new algorithms for proving optimality of sorting networks by starting with the very basic representation of comparator networks. We present a non-injective function that maps a comparator network to an itemset.