Combinatorics, Groups, Algorithms, and Complexity

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

Problems of combinatorial optimization, especially problems for graphs (cliques, coloring, matchings, paths, cuts, etc.) have for decades been among the central subjects of study both in the theory of algorithms and in complexity theory; in return, complexity theory has provided fundamental new insights into the nature of these problems. This interaction was critical at the genesis of the P vs NP problem four decades ago, underwent a second revolution in the wake of interactive proofs and the modern theory of approximation algorithms, and continues to this date with the study of the striking effects of the Unique Games Conjecture on the landscape of approximation algorithms in combinatorial optimization.

Combinatorial models of computation (circuits, branching programs, communication complexity, etc.) have given rise to some of the most exciting developments in complexity theory, and continue to pose some of the most daunting challenges. Probabilistic and extremal combinatorics have provided many of the basic tools for theoretical computer science, and conversely, work driven by questions of complexity theory has contributed to progress on central questions in combinatorics (e.g. on explicit Ramsey constructions).

While this conference continues to explore the interactions between combinatorics and theoretical computer science, it will be the first conference to highlight the role of group theory in this web.

Cayley graphs and vertex-transitive graphs have for a long time provided a link between combinatorics and group theory; they have also been studied in the context of interconnection networks and serve as a fertile ground to study the mixing rate of random walks, loi Pinel ancien, an area of intense study in the theory of computing for its connection to approximate counting; group theoretic expander constructions are household tools in complexity theory and have helped infuse new blood into the classical theory of error-correcting codes, itself noted for its deep connections to group theory; the construction of zig-zag products of graphs, motivated in part by the notion of semidirect products of groups, has lead to a recent breakthrough in space complexity; complexity theoretic thinking has taken root in computational group theory; a complexity theoretic study of groups has served as one of the motivations behind interactive proofs; interactive and holographic proofs have spawned new areas of coding theory (locally testable and locally correctable codes) and contributed to the rise of a new paradigm in decision tree complexity (property testing); discrete Fourier transform, a group theoretic concept, has been central to the study of the complexity of Boolean functions as well as to holographic proofs; Weil's character sum estimates serve as powerful derandomization tools; groups continue to serve as models for the comparison of complexity classes; group theory was found to be at the heart of the graph isomorphism problem, one of the few classical combinatorial search problems of unsettled complexity status; combinatorial methods and asymptotic thinking, to no small extent inspired by algoritmic questions, are partly responsible for the rise of the area of asymptotic group theory; the probabilistic method and the study of random structures, both pioneered by Paul Erdős in combinatorics, have become standard tools in algorithms and complexity theory and have impacted asymptotic group theory; group representations have recently been connected to fast matrix multiplication; the unitary group is the central medium of computation in quantum computing, an area where the hidden subgroup problem has emerged to a prominent status - just to name a few of the connections.

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 year of Laci Babai's 60th birthday.


Ákos Seress (Ohio State University)
Mario Szegedy (Rutgers)


The following is a partial list of confirmed speakers at the meeting:
Scott Aaronson (MIT)
Miklós Abért (Rényi Inst., Budapest)
Robert Bailey (Regina, Canada)
Robert Beals (CCR - Princeton)
Peter J. Cameron (Queen Mary, London)
Sourav Chakraborty (CWI, Amsterdam)
Paolo Codenotti (Chicago)
Alla Detinko (Galway, Ireland)
Oren Dinai (Geneva)
John Dixon (Carleton, Ottawa)
Lance Fortnow (Northwestern)
Zoltán Füredi (UIUC)
Martin Fürer (Penn State)
Anna Gál (U Texas - Austin)
Chris Godsil (Waterloo)
Igor Gorodezky (Cornell)
Ronald L. Graham (UCSD)
Péter Hajnal (Szeged, Hungary)
Tom Hayes (U New Mexico)
Harald Helfgott (Bristol, U.K.)
Gábor Hetyei (Charlotte NC)
Wilfried Imrich (Leoben, Austria)
Gábor Ivanyos (SzTAKI, Budapest)
William M. Kantor (U Oregon)
Martin Kassabov (Cornell)
Subhash Khot (NYU)
Shiva Kintali (GA Tech)
Raghav Kulkarni (Chicago)
Sandy Kutin (CCR - Princeton)
Satya V. Lokam (MS Research - Bangalore)
Alex Lubotzky (Hebrew U)
Eugene M. Luks (U Oregon)
Bojan Mohar (Simon Fraser, BC, Canada)
Dhruv Mubayi (U Illinois, Chicago)
Lale Ozkahya (UIUC)
Jaroslav Nešetřil (Charles U, Prague)
Péter P. Pálfy (Rényi Inst., Budapest)
Toniann Pitassi (Toronto)
Cheryl E. Praeger (Western Australia)
László Pyber (Rényi Inst., Budapest)
Alexander Razborov (Chicago)
Lajos Rónyai (SzTAKI, Budapest)
Alex Russell (U Connecticut)
Ákos Seress (Ohio State)
Aner Shalev (Hebrew U)
Janos Simon (Chicago)
Daniel Štefankovič (Rochester, N.Y.)
Madhu Sudan (MIT)
Zoran Sunic (Texas A&M;)
Mario Szegedy (Rutgers)
Éva Tardos (Cornell)
Gábor Tardos (Simon Fraser, BC, Canada & Rényi Inst., Budapest)
Evelina Toumpakari (Oxford)
György Turán (U Illinois, Chicago & Szeged, Hungary)
Emanuele Viola (Northeastern U, Boston)
Avi Wigderson (IAS, Princeton)
James B. Wilson (Ohio State)