Celebrating Laci Babai's 70th birthday

A powerful web of interconnections among the areas in the title has been built over the past decades, with a transformative effect on each area.

Asymptotic rates of growth is a central theme connecting these areas.  It has been the focus of Erdős-style graph theory and combinatorics, and this aspect made it highly relevant to the theory of algorithms and complexity theory.  Structures in graphs (cliques, colorings, matchings, paths, cuts, etc.) commonly studied in combinatorial optimization have been among the central objects of study both in the theory of algorithms and in complexity theory; in return, complexity theory, including the theory of interactive proofs, has provided fundamental new insights into the nature of these structures.

While numerous conferences have explored the connections between combinatorics and complexity theory, few have been devoted to the links of these areas to group theory, a central theme of this meeting.   The emerging field of (sparse) graph limits is tied to group actions.   While asymptotic group theory took a boost from the Classification of Finite Simple Groups, elementary methods of combinatorics, graph theory, and linear algebra have added to the arsenal, expanding the scope of the study from highly symmetrical to highly regular structures, including coherent configurations.   Growth of subsets in graphs and the closely related concept of the mixing rate of random walks are ubiquitous in complexity theory; constructions of highly expanding graphs are based on or inspired by group theory.  The asymptotic theory of permutation groups and of coherent configurations is at the heart of recent progress on the Graph Isomorphism problem.  An exciting era of rates of growth in finitely generated groups started with Gromov's celebrated theorem on polynomial word growth.  Local expansion of finite vertex-transitive graphs yields performance guarantees of algorithms in computational group theory.   And the list goes on...

The meeting will bring together scholars and students in the areas in the title. It is our hope that the conference will inspire new links and further cross-fertilization.

Not coincidentally, the meeting will take place during the week before Laci Babai's 70th birthday.

 

Principal speakers

  • Scott Aaronson*  (U Texas - Austin)

  • Ágnes Backhausz (Rényi Institute, Budapest)

  • Jin-yi Cai  (U Wisconsin - Madison)

  • Peter Cameron (U St. Andrews, UK)

  • Sean Eberhard (Cambridge, UK)

  • Peter Frankl  (Tokyo)

  • Martin Fürer (Penn State)

  • Chris Godsil (U Waterloo)

  • Harald Helfgott* (U Göttingen & CNRS)

  • Alexander A. Ivanov (Imperial Coll., London)

  • Martin Kassabov (Cornell)

  • Martin Liebeck  (Imperial Coll., London)

  • Nati Linial  (Hebrew U, Jerusalem)

  • Alex Lubotzky (Hebrew U, Jerusalem)

  • Bojan Mohar  (Simon Fraser U, BC, Canada)

  • Jarik Nešetřil (Charles U, Prague)

  • Péter Pál Pach  (Budapest U Tech & Econ) 

  • Cheryl Praeger (U Western Australia, Perth)

  • Pavel Pudlák (Czech Acad Sci, Prague)

  • László Pyber (Rényi Institute, Budapest)

  • Alexander Razborov (U Chicago)

  • Aner Shalev (Hebrew U, Jerusalem)

  • Alexander Sherstov (UCLA)

  • Madhu Sudan (Harvard)

  • Balázs Szegedy (Rényi Institute, Budapest)

  • Mario Szegedy (Rutgers)

  • Éva Tardos (Cornell)

  • Gábor Tardos (Rényi Institute, Budapest)

  • Shang-Hua Teng (U Southern California)

  • Matthew Tointon (Cambridge)

* tentative

Organizing committee

  • Miklós Abért (co-chair - Rényi Institute, Budapest)

  • László Lovász (chair - Eötvös U, Budapest)

  • Dezső Miklós (local arrangements chair - Rényi Institute, Budapest)

  • Péter P. Pálfy (Rényi Institute, Budapest)

  • László Pyber (Rényi Institute, Budapest)

  • Lajos Rónyai (Budapest U Tech & Econ)

  • Gábor Somlai (secretary - Eötvös U, Budapest)