The 22nd McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 28th to March 7th, 2010. Participants are expected to arrive on Sunday afternoon, February 28th. The subject of this year's workshop will be additive combinatorics and group representation.
Ben J. Green
University of Cambridge
Arithmetic Combinatorics
The theme will be various types of approximate algebraic structure - approximate groups, approximate homomorphisms, and approximate polynomials. We will be asking (and partially answering!) the following basic questions:Along the way various somewhat surprising connections between the different objects will be uncovered.
- What are the right definitions of these things?
- To what extent does an approximate object resemble an exact one? Can one "roughly classify" approximate groups and approximate polynomials?
- What are the applications to theoretical computer science and number theory?
Topics to be covered will be roughly as follows.
APPROXIMATE HOMOMORPHISMS. The 99% theory: linearity testing and the Blum- Luby-Rubinfeld test. The 1% theory: Freiman homomorphisms and results of Ruzsa. The Polynomial Freiman-Ruzsa conjecture. Discussion of the Hyers-Ulam stability problem.
APPROXIMATE GROUPS. The 99% theory: results of Freiman and Fournier. Cooperman's "Fibonacci cube" algorithm for generating a random element of a black box group. The 1% theory: the Freiman-Ruzsa theorem. Nonabelian generalisations including Helfgott's theorem and applications to expanders.
APPROXIMATE POLYNOMIALS. The 99% theory: polynomiality testing. The 1% theory: Gowers norms, inverse theorems, inverse conjectures and applications to number theory.
Avi Wigderson
Institute for Advanced Study
Representation theory of finite groups, and applications
The plan is to explain some of the rudiments of this beautiful theory, and in what sense it generalizes the usual Fourier transform from Abelian to non Abelian groups. Then we'll demonstrate the usefulness of this theory (in particular, understanding the group algebra, its decomposition, and dimensions of irreducible representations) to several applications. These applications will be mainly (but not only) to understanding expansion and random walks in groups (some related to arithmetic combiantorial problems). The applications include (we will not be able to cover all..)
- Expanding generators for every group [Alon-Roichman]
- Importance of the minimal dimension to expansion and equations over groups [Sarnak-Xue, Bourgain-Gamburd, Gowers, Babai-Nikolov-Pyber]
- Importance of the maximal dimension to fast matrix multiplication [Cohn-Umans, Cohn-Kleinberg-Szegedy-Umans]
- Expanding generators for non-simple groups [Alon-Lubotzky-W, Meshulam-W]
- Card shuffling, and random walks on the symmetric group [Diaconis-Shahshahani, Kassabov]