2010 Barbados Workshop on Computational Complexity

2010 Barbados Workshop on Computational Complexity

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

    Important Information for Participants