Groups, Graphs, Algorithms: The Graph Isomorphism Problem Event as iCalendar

12 March 2018

5pm

Venue: PLT1/303-G20

Location: Ground Floor, Building 303, City Campus

Host: Department of Mathematics

Cost: FREE (Refreshments to follow in the Level 4 Common Room)

Professor László Babai from the University of Chicago, USA
Professor László Babai from the University of Chicago, USA

 

Deciding whether or not two given finite graphs are isomorphic has for decades been known as one of a small number of natural computational problems with unsettled complexity status within the P/NP theory.

Building on a framework introduced in a seminal 1980 paper by Eugene M. Luks, recent algorithmic progress on this problem has involved an interplay between finite permutation groups, graphs, and algorithmic techniques such as the "Divide and Conquer'' principle.

This talk from our guest speaker, Professor László Babai from the University of Chicago, USA, will attempt to illustrate some of the components of this work.

All welcome. No prior knowledge of group theory, graphs, or algorithms will be assumed.

The presentation will be followed by refreshments in our Level 4 Common Room.

Our guest speaker

Professor László (Laci) Babai is the George and Elizabeth Yovovich Professor of Computer Science and Mathematics at the University of Chicago.

His research interests include complexity theory, algorithms, combinatorics, discrete mathematics, finite groups, and interactions among these.

He is a Fellow of the American Academy of Arts and Sciences, and the recipient of distinguished international prizes.

In November 2015 he announced a major and unexpected breakthrough: the Graph Isomorphism Problem can be solved in quasipolynomial

time.

During his first visit to New Zealand, he will give four lectures on this topic. The other lectures in this series are: