Coherent configurations and Graph Isomorphism: The emergence of the Johnson graphs Event as iCalendar

21 March 2018

1pm

Venue: Room 257

Location: Level Two, Building 303, 38 Princes Street, City Campus

Host: Department of Mathematics

Cost: FREE - all welcome

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

 

Abstract

In this talk Professor László (Laci) Babai will discuss combinatorial aspects of recent progress on the Graph Isomorphism problem.

Highly regular edge-colorings of the directed complete graph, called "coherent configurations'', play a central role.

Apart from some motivating examples, no group theory will be used in this talk.

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: