# Workshop Programme

## for period 28 March - 1 April 2011

### Discrete Harmonic Analysis

28 March - 1 April 2011

Timetable

Monday 28 March | ||||

09:00-09:55 | Registration | |||

09:55-10:00 | Welcome from Sir David Wallace (INI Director) | |||

10:00-11:00 | Kalai, G (HUJI & Yale) |
|||

Threshold behaviour | Sem 1 | |||

In the lecture I will describe some results and problems regarding threshold behavior of Boolean and other functions. 1. Sharp threshold, the equal-slice measure and the Shapley value: Result: Boolean functions with diminishing threshold window are precisely Boolean functions with diminishing maximum Shapley value. Problem: Close the exponential gap in the quantitative version of this result, 2. Sharp threshold for larger alphabets (with Elchanan Mossel) We show that sharp threshold behavior for monotone Boolean functions with symmetry extends to a larger alphabet. Large alphabets offer new challenges and new phenomena. 3. Problems about the relation between the expectation threshold and the threshold for graph properties and Boolean functions. (with Jeff Kahn). When probabilities get tiny matters are more difficult and more interesting. |
||||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Latala, R (Warsaw) |
|||

Tail and moment estimates for Rademacher chaos | Sem 1 | |||

We present two-sided estimates of moments and tails of polynomial chaoses of order at most three generated by Rademacher sequence (i.e. a sequence of independent symmetric random variables taking values +/-1). The estimates involve only deterministic quantities and are optimal up to universal constants. This is a joint work with R Adamczak (Warsaw). |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | O'Donnell, R (Carnegie Mellon) |
|||

The Fourier Entropy-Influence conjecture for certain classes of Boolean functions | Sem 1 | |||

In this talk we report some progress on Friedgut and Kalai's "Fourier Entropy-Influence Conjecture". We verify the conjecture for symmetric functions, read-once decision trees, and certain generalizations of these classes. Joint work with John Wright and Yuan Zhou of Carnegie Mellon University. |
||||

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Tetali, P (Georgia Tech) |
|||

Transportation and related inequalities in discrete spaces | Sem 1 | |||

Following exciting developments in the continuous setting of manifolds (and other geodesic spaces), in joint works with various collaborators, I have explored discrete analogs of the interconnection between several functional inequalities in discrete spaces; such inequalities include concentration, transportation, displacement convexity and modified versions of the logarithmic Sobolev inequality. I will attempt to review some of these connections and illustrate with examples. Computational aspects of the underlying functional constants and other open problems will also be mentioned. |
||||

17:00-18:00 | Wigderson, A (IAS, Princeton) |
|||

The power and weakness of randomness, when you are short on time (Rothschild Lecture) | Sem 1 | |||

Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I'll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms efficient. Time permitting, I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs. |
||||

18:00-18:30 | Welcome wine reception & Posters session | |||

18:45-19:30 | Dinner at Wolfson Court (residents only) |

Tuesday 29 March | ||||

10:00-11:00 | Regev, O (Tel Aviv) |
|||

Quantum one-way communication can be exponentially stronger than classical communication | Sem 1 | |||

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

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Friedgut, E (HUJI) |
|||

Dictatorships and juntas in the symmetric group | Sem 1 | |||

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

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Håstad, J (KTH NADA) |
|||

On the usefulness of predicates | Sem 1 | |||

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

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Servedio, R (Columbia) |
|||

Influences and Boolean functions representations | Sem 1 | |||

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

16:30-17:30 | Anantharaman, N (Paris-Sud) |
|||

The semiclassical limit for eigenfunctions of the laplacian : a survey | Sem 1 | |||

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

17:45-18:45 | Football game at Churchill College | |||

18:45-19:30 | Dinner at Wolfson Court (residents only) |

Wednesday 30 March | ||||

10:00-11:00 | Lugosi, G (Barcelona) |
|||

Sharp threshold for percolation on expanders | Sem 1 | |||

In this joint work with I. Benjamini, S. Boucheron, and R. Rossignol, we study the appearance of the giant component in random subgraphs of a given finite graph G = (V,E) in which each edge is present independently with probability p. We show that if G is an expander with vertices of bounded degree, then for any c in (0,1), the property that the random subgraph contains a giant component of size c|V | has a sharp threshold. The main technical tools are based on variance inequalities for functions of independent random variables. |
||||

11:00-11:30 | Group Photo and Morning Coffee | |||

11:30-12:30 | Dai Pra, P (Padova) |
|||

Convex decay of entropy in interacting systems | Sem 1 | |||

For a Markov process, the exponential decay of relative entropy with respect to the invariant measure corresponds to a functional inequality sometimes called "Modified logarithmic Sobolev inequality" (MLSI). We consider a stronger inequality, that, besides exponential decay, implies that the relative entropy is convex in time. The advantage of this inequality is that it can be obtained, for some systems of interacting particle, via a Bakry-Emery-type approach, avoiding more complicated martingale methods. After having illustrated this approach, I will present some recent progresses on the subject, obtained in collaboration with G. Posta. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Open problems session | |||

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Khot, S (Courant Institute) |
|||

A two prover one round game with strong soundness | Sem 1 | |||

We show that for any large integer q, it is NP-hard to distinguish whether a two prover one round game with q^6 answers has value close to 1 or at most O(1/q). The result is obtained by combining two new techniques: (i) An Inner PCP based on the "point versus subspace" test for linear functions. The test is analyzed Fourier analytically. (ii) The Outer/Inner PCP composition that relies on a certain "sub-code covering" property for Hadamard codes. As an application, we show that unless NP has quasi-polynomial time deterministic algorithms, the Quadratic Programming Problem is inapproximable within factor (\log n)^{1/6 - o(1)}. The talk should be self-contained. Joint work with Muli Safra |
||||

16:30-17:30 | Sanders, T (Cambridge) |
|||

Somewhere between Freiman's theorem and the Polynomial Freiman-Ruzsa conjecture | Sem 1 | |||

Freiman's theorem describes the structure of sets of integers having small doubling which enjoys numerous applications in additive combinatorics. While the result is qualitatively comprehensive, a truer picture is suggested by the Polynomial Freiman-Ruzsa conjecture, and in this talk we shall discuss how a remarkable new technique of Croot and Sisask can be used in conjunction with a trick of Lopez and Ross to provide much clearer quantitative information. We shall focus on the model finite field setting where there are few prerequisites and the details are the cleanest. |
||||

19:30-22:00 | Conference Dinner at Selwyn College |

Thursday 31 March | ||||

10:00-11:00 | Gowers, WT (Cambridge) |
|||

Proving theorems inside sparse random sets | Sem 1 | |||

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

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Bennett, J (Birmingham) |
|||

The Brascamp--Lieb inequalities and the restriction problem for the Fourier transform | Sem 1 | |||

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

12:30-13:30 | Lunch at Wolfson Court | |||

13:30-15:00 | Free time | |||

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Raghavendra, P (Georgia Tech) |
|||

Expansion of small sets in graphs | Sem 1 | |||

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

16:30-17:30 | Garban, C (ENS Lyon) |
|||

High frequency criteria for Boolean functions (with an application to percolation) | Sem 1 | |||

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

18:45-19:30 | Dinner at Wolfson Court (residents only) |

Friday 1 April | ||||

10:00-11:00 | Mossel, E (Weizmann Institute of Science) |
|||

On reverse hypercontractive inequalities | Sem 1 | |||

A hyper-contractive inequality for an operator T states that |Tf|_q \leq |f|_p where q > p > 1 for all functions f. Hyper contractive inequalities play a crucial role in analysis in general and in discrete Fourier analysis in particular. A reverse hyper-contractive inequality for the operator T states that |Tf|_q \geq |f|_p for q < p < 1 (q and p can be negative) and all strictly positive functions f. The first reverse hyper-contractive inequalities were proved by Borell more than 2 decades ago. While these inequalities may look obscure, they have been used for the solution of a number of problems in the last decade. I will survey applications of the inequalities and discuss new results relating reverse hyper-contractive inequalities to hyper-contractive, Log-Sobolev and Poincare inequalities as well as some new applications. This is a joint work with K Oleszkiewicz (Warsaw) and A Sen (Cambridge). |
||||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Kindler, G (HUJI) |
|||

A quantitative version of the Gibbard-Satterthwaite theorem | Sem 1 | |||

Consider an election between q alternatives, where each of the voters rank the different alternatives, and the winner is determined according to some predefined function of this voting profile. Such a social choice function is called manipulable, if a situation might occur where a voter who knows the rankings given by other voters can change her ranking in a way that does not reflect her true preference, but which leads to an outcome that is more desirable to her. Gibbard and Satterthwaite proved that any social choice function where more than two alternatives can be selected is manipulable, unless it is a dictatorship (where the outcome of the election only depends on the choices of one voter). In the case where the social choice function is neutral, namely when it is invariant under changing the names of the alternatives, we prove a lower bound on the fraction of manipulable preference profiles which is inverse polynomial in the number of voters and alternatives. Our proof in fact does not rely on discrete harmonic analysis - finding an analytic version of the proof would be the role of the audience. Joint work with Marcus Isaksson and Elchanan Mossel. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Chatterjee, S (Courant Institute) |
|||

Large Deviation Principle for the Erdös-Renyi random graph | Sem 1 | |||

What does an Erdos-Renyi graph look like when a rare event happens? I will describe an answer to this question when p is fixed and n tends to infinity by establishing a large deviation principle under an appropriate topology. The formulation and proof of the main result uses the recent development of the theory of graph limits by Lovasz and coauthors and Szemeredi's regularity lemma from graph theory. As a basic application of the general principle, we work out large deviations for the number of triangles in G(n,p). Surprisingly, even this simple example yields an interesting double phase transition. This is based on joint work with S. R. S. Varadhan. |
||||

15:00-15:30 | Afternoon Tea | |||

18:45-19:30 | Dinner at Wolfson Court (residents only) |