Groups, Graphs, Growth and Complexity
Budapest 13 July - 17 July 2020
If you already have an account, please login!
forgot your password?
Due to the current Covid-19 pandemic, the GGGC-20 conference has been canceled.
Currently the Covid-19 epidemic seems rather mild in Hungary, thanks to the smaller initial exposure and the strict public-health measures that are in place.
But given the continuing unpredictability of the situation, both in terms of the persistence of the epidemic and the public-health measures globally, we feel that hanging on to the idea of such a large gathering less than three months from now is not in the best interest of our community.
We made this decision in complete agreement with Laci Babai. We wish him and all our friends who have been preparing to greet him in Budapest good luck to pass safely through this uncertain period.
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.
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)
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)