Description
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.