Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Symmetry and Similarity (Video Lecture)
Speaker:Martin Grohe
coming from:RWTH Aachen
Speakers Bio:
Event Type:Colloquium Lecture
Visibility:D1, D3, D4, RG1, MMCI, D2, INET, D5, SWS
We use this to send out email in the morning.
Level:MPI Audience
Language:English
Date, Time and Location
Date:Tuesday, 31 March 2020
Time:11:00
Duration:60 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:Video Lecture
Abstract
Symmetry is a fundamental concept in mathematics, the sciences, and beyond. Understanding their symmetries is often crucial for understanding mathematical structures. Computing the symmetries of a structure is essentially the same as deciding whether two structures are the same ("isomorphic"). Algorithmically, this is a difficult task that has received a lot of attention since the early days of computing. It is a major open problem in theoretical computer science to determine the precise computational complexity of this "Graph Isomorphism Problem".

One of the earliest applications of isomorphism testing was in chemistry, more precisely chemical information systems. Today, applications of isomorphism testing and symmetry detection are ubiquitous in computing. Prominent examples appear in optimisation, malware detection, and machine learning. However, in many of these applications, we only need to decide if two structures are sufficiently similar, rather than exactly the same. It turns out that determining how similar two structures are is an even harder computational problem than deciding whether they are isomorphic.

My talk will cover algorithmic aspects of symmetry and similarity, ranging from the fundamental complexity theoretic "Graph Isomorphism Problem" to applications in machine learning.

Contact
Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Kurt Mehlhorn, 03/17/2020 11:28 AM
  • Kurt Mehlhorn, 03/11/2020 08:57 AM -- Created document.