Kolloquiumsvortrag: Prof. Dr. Peter Schneider-Kamp

11.04.2014 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2

Titel: The Quest for Optimal Sorting Networks




Recent work identifying depth-optimal n-channel sorting networks for n=9 is based on exploiting symmetries of the first two layers. Very recently, an approach based on generating two-layer prefixes modulo symmetries and using encodings to the SAT problem settles depth-optimality for n=13 (and, consequently also for, n=16). However, the naive generate-and-test approach applied there does not scale beyond n=13. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by more than three orders of magnitude for n=13 and easily scales until n=40.

Prof. Dr. M. Hanus

Diesen Termin meinem iCal-Kalender hinzufügen