An introduction to algorithmic aspects of symmetry and similarity, ranging from the fundamental complexity theoretic "Graph Isomorphism Problem" to applications in optimisation and machine learning
Strachey Lecture: Symmetry and Similarity
Symmetry is a fundamental concept in mathematics, science and engineering, and beyond. Understanding symmetries is often crucial for understanding structures. In computer science, we are mainly interested in the symmetries of combinatorial structures. Computing the symmetries of such 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".
Series:
People:
Oxford Unit:
Keywords:
More in this Series...
This series covers the Strachey Lectures, a series of termly computer science lectures named after Christopher Strachey, the first Professor of Computation at the University of Oxford.
Hosted by the Department of Computer Science, University of Oxford, the Strachey Lectures began in 1995 and have included many distinguished speakers over the years. The Strachey Lectures are generously supported by OxFORD Asset Management.