Markus Anders

(AG Algorithmics and Complexity, Prof. Schweitzer)
hosted by PhD Program in CS @ TU KL

"Search Problems in Trees with Symmetries: near optimal traversal strategies for individualization-refinement algorithms"

The graph isomorphism problem captures the essence of symmetry detection in combinatorial structures. Since exploitation of symmetry can have a dramatic impact on the efficiency of algorithms in various fields, practical solvers have been developed for over 50 years. In this talk, I present a search problem on trees that closely captures the backtracking behavior of all current practical graph isomorphism algorithms. We derive novel probabilistic algorithms for which the running time is sublinear in the size of the trees, improving upon known backtracking techniques which incur linear cost. We prove that these algorithms are optimal up to logarithmic factors. Furthermore, we give tight linear lower bounds for deterministic algorithms.

Time:	Monday, 14.12.2020, 15:45
Place:	https://uni-kl-de.zoom.us/j/93969376626?pwd=ZmJ3MmExTmJ3alZ0c2YvZWNiYkhBQT09
Video:

Termin als Datei downloaden und in den Kalender importieren.