The Michael Erceg Public Lecture Event as iCalendar

21 March 2018

6:15pm

Venue: Lecture Theatre MLT2

Location: First Floor, Building 303, 38 Princes Street, City Campus

Host: Department of Mathematics

Cost: FREE (Refreshments will be served prior to the lecture at 5pm in our Level 4 Common Space)

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


Symmetry versus Regularity: The Graph Isomorphism Problem

Can you tell if two networks are the same, apart from the naming of their nodes? This simple question, called the “Graph Isomorphism Problem”, has been a source of fascination in computational complexity theory because of its unsettled complexity status within the P/NP theory.

Arguably, the question boils down to closing the gap between two notions that go back to antiquity: symmetry and regularity.

The mathematical discipline that formalises symmetry is “group theory,” and “combinatorics” is the area that deals with regularity.

A combination of methods of these fields has led to recent progress on the question.

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:

The Michael Erceg Senior Visiting Fellowship is made possible by generous support from the Margaret and John Kalman Charitable Trust