[Proof Complexity] MIAO seminar Tue May 21 at 10:00 CEST with Markus Anders: Efficient algorithms for symmetry detection

[Jakob Nordström]

Dear all,

On Tuesday May 21 at 10:00 CEST (note the time!) we will have the pleasure of welcoming Markus Anders from Technische Universität Darmstadt, who will give a presentation titled "Efficient algorithms for symmetry detection". You find the abstract at the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. Local participants are warmly welcome to seminar room N116B at Universitetsparken 1. Other participants are equally warmly welcome to join virtually at https://lu-se.zoom.us/j/61925271827 . Please feel free to share this information with colleagues who you think might be interested. We are also hoping to record the seminar and post on the MIAO Research YouTube channel https://youtube.com/@MIAOresearch for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then, after a break, an optional ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners a self-contained overview of some exciting research results, and that listeners who got particularly interested will then get have the chance to really get into the technical details during the second half. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming MIAO seminars can be found at https://jakobnordstrom.se/miao-seminars/. If you do not wish to receive these announcements, or receive several copies of them, please send a message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

Tuesday May 21 at 10:00 (note the time!) in seminar room N116B, Universitetsparken 1, University of Copenhagen, and on Zoom
Efficient algorithms for symmetry detection
(Markus Anders, Technische Universität Darmstadt)

Exploitation of symmetry has a dramatic impact on the efficiency of algorithms in various fields. Before symmetries of a structure can be exploited, one first has to have algorithmic means to find the symmetries efficiently. Typically, this is achieved through modeling said structure as a graph, followed by an application of a practical graph isomorphism solver such as nauty, saucy, bliss, Traces, or dejavu.

In this talk, I will give an overview of recent progress on practical graph isomorphism solvers. I present a theoretical model which captures the backtracking behavior of all state-of-the-art solvers, within which we prove probabilistic strategies to be optimal up to logarithmic factors. Then, I briefly discuss the design of the practical solver dejavu, which is based on a near-optimal probabilistic backtracking strategy.

The material presented is based on joint work with Pascal Schweitzer.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se