10:00 to 11:00 O Regev ([Tel Aviv])Quantum one-way communication can be exponentially stronger than classical communication In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only O(log n) qubits, but for which any classical (randomized, bounded-error) protocol requires poly(n) bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. In other words, can quantum one-way communication be exponentially stronger than classical two-way communication? Here we settle this question in the affirmative. Based on joint work with Bo'az Klartag. NOTE: This talk is about lower bounds for *classical* communication complexity; no knowledge of quantum communication complexity is assumed or required. INI 1 11:00 to 11:30 Morning Coffee 11:30 to 12:30 E Friedgut ([HUJI])Dictatorships and juntas in the symmetric group One of the main themes of using discrete harmonic analysis in combinatorial settings, is detecting structures, (or functions) that essentially depend on few coordinates. The Fourier characterization of these juntas is usually expressed by the fact that the Fourier transform is concentrated on low levels. In this talk I will study the question of the analog of this phenomenon in the symmetric group. INI 1 12:30 to 13:30 Lunch at Wolfson Court 14:00 to 15:00 J Håstad (KTH NADA)On the usefulness of predicates One successful application of discrete harmonic analysis has been the analysis of Max-CSPs, maximum constraint satisfaction problems. In the Max-CSP defined by a predicate P of arity k we are presented with a list of k-tupels of literals and the goal is to find assignments to the variables in order to maximize the number of resulting k-bit strings that satisfy P. A predicate P is approximation resistant if, even for instances where the optimal assignments satisfies (almost) all constraints, it is infeasible to do find an assignment that satisfies substantially more constraints than what is obtained by picking a random assignment. We study a more general question of given the promise of the existence of an assignment that satisfies all the constraints given by P, to efficiently finding an assignment that satisfies a weaker predicate (or more general function) Q. In particular we say P is useless if it is infeasible to do substantially better than random for any Q. In this talk we describe this framework and derive results on uselessness based on NP ≠ P and the Unique Games Conjecture. INI 1 15:00 to 15:30 Afternoon Tea 15:30 to 16:30 R Servedio ([Columbia])Influences and Boolean functions representations More than twenty years ago the important work of Kahn, Kalai and Linial gave general bounds on the influence of variables in arbitrary Boolean functions over the discrete hypercube. In theoretical computer science, though, often one is interested in particular types of "simple" Boolean functions such as constant-depth circuits, decision trees, low-degree polynomial threshold functions, etc. This additional structure raises the possibility that refined influence bounds can be obtained, and indeed it turns out that this is sometimes the case. This talk will give an overview of several such results and their applications, with an emphasis on currently open questions and directions for future work. INI 1 16:30 to 17:30 N Anantharaman ([Paris-Sud])The semiclassical limit for eigenfunctions of the laplacian : a survey This will be a (non exhaustive) survey talk about the behaviour of eigenfunctions of the laplacian on a compact manifold, in the asymptotic regime where the eigenvalue goes to infinity. The issue of quantum ergodicity'' is to understand the places where the eigenfunctions can concentrate. Recently, there has been increasing interest about possible analogues for the discrete laplacian on finite graphs (for instance, with the work of Brooks and Lindenstrauss). According to the physics literature, the interesting asymptotic regime to look at is the case of families of graphs whose size goes to infinity. As far as graphs are concerned, the talk will contain more open questions than results. INI 1 17:45 to 18:45 Football game at Churchill College 18:45 to 19:30 Dinner at Wolfson Court (residents only)
 10:00 to 11:00 WT Gowers ([Cambridge])Proving theorems inside sparse random sets In 1996 Kohayakawa, Luczak and Rödl proved that Roth's theorem holds almost surely inside a subset of {1,2,...,n} of density Cn^{-1/2}. That is, if A is such a subset, chosen randomly, then with high probability every subset B of A of size at least c|A| contains an arithmetic progression of length 3. (The constant C depends on c.) It is easy to see that the result fails for sparser sets A. Recently, David Conlon and I found a new proof of this theorem using a very general method. As a consequence we obtained many other results with sharp bounds, thereby solving several open problems. In this talk I shall focus on the case of Roth's theorem, but the generality of the method should be clear from that. INI 1 11:00 to 11:30 Morning Coffee 11:30 to 12:30 J Bennett ([Birmingham])The Brascamp--Lieb inequalities and the restriction problem for the Fourier transform The Brascamp--Lieb inequalities simultaneously generalise classical inequalities in analysis such as the multilinear Holder, Young convolution and Loomis--Whitney inequalities. In this talk we will describe certain geometric and combinatorial generalisations of these multilinear inequalities which arise naturally in harmonic analysis and PDE. Particular emphasis will be placed on their intimate connected with the recent restriction theory of the Fourier transform. INI 1 12:30 to 13:30 Lunch at Wolfson Court 13:30 to 15:00 Free time 15:00 to 15:30 Afternoon Tea 15:30 to 16:30 P Raghavendra ([Georgia Tech])Expansion of small sets in graphs A small set expander is a graph where every set of sufficiently small size has near perfect edge expansion. This talk concerns the computational problem of distinguishing a small set-expander, from a graph containing a small non-expanding set of vertices. This problem henceforth referred to as the Small-Set Expansion problem has proven to be intimately connected to the complexity of large classes of combinatorial optimization problems. More precisely, the small set expansion problem can be shown to be directly related to the well-known Unique Games Conjecture -- a conjecture that has numerous implications in approximation algorithms. In this talk, we motivate the problem, and survey recent work consisting of algorithms and interesting connections within graph expansion, and its relation to Unique Games Conjecture. INI 1 16:30 to 17:30 C Garban ([ENS Lyon])High frequency criteria for Boolean functions (with an application to percolation) Assume you are given a certain Boolean function f: {0,1}^n -> {0,1} and you are suspecting that it is a high frequency'' one. It is a non-trivial problem to localize at a low cost' where the Spectral mass'' lies. Of course, one could compute the Fourier-Walsh coefficients one at a time, but in the generic case this would take forever and this is the kind of techniques we are trying to avoid by looking for a low cost' criterion. In this talk, I will survey different criteria or techniques which enables one to detect whether a Boolean function is of high frequency or not. To give an example of such a criterion, the first result in this direction is due to Benjamini, Kalai and Schramm. It states that if the Boolean function f is such that its individual influences are small'' (in a precise L^2 way), then the function has to be of high frequency with a quantitative bound on how high the spectrum is. Most of these criteria have been discovered while analyzing the percolation case. Indeed any geometrical event about configurations of percolation can be written as a Boolean function where each bit'' determines whether its corresponding edge (or site) is open or closed. It turns out that at criticality, these Boolean functions are of very high frequency. In other words, percolation is very sensitive to small perturbations at the critical point. Since it is very hard to compute all the Fourier coefficients of such functions, several tools have been developed in the literature to understand the Fourier spectrum of percolation. Interestingly, most of these tools can be simply stated and are not specifically designed for percolation. Therefore, the purpose of this talk will be to expose these criteria in an accessible way, with the hope that some of them could be used elsewhere. INI 1 18:45 to 19:30 Dinner at Wolfson Court (residents only)