Workshop IV: Analytical Methods in Combinatorics, Additive Number Theory and Computer Science

December 1 - 4, 2009

Overview

Recently the applications of analytical tools, in particular methods of harmonic analysis and spectral techniques, lead to several major breakthroughs on problems in combinatorics, Discrete Probability, Additive Number Theory and Computer Science. In additive combinatorics there has been much progress in understanding the combinatorial structures arising from arithmetic operations, using techniques from Fourier analysis. It started with the new proofs of Freiman’s structure theorem and Szemeredi’s theorem on arithmetic progressions that are more efficient and easier to understand than the original ones, culminating with the recent result of Green and Tao on arithmetic progressions of primes. In yet another exciting development Bourgain gave non-trivial estimates for short exponential sums, the question that withstood all previous attempts to solve it.

In computer science Kahn, Kalai and Linial were the first to use harmonic analysis and in particular hypercontractive inequalities to prove some general theorems on boolean functions. Over the years this approach proved itself to be very fruitful leading to numerous results on the complexity of boolean functions, hardness of approximation, lower bounds on distortion for metric embeddings and new results in extremal set theory. Analytical tools were also used efficiently to study the so called threshold phenomena in various random systems. This is a setting when the probability of some event changes rapidly from zero to one as some underlying parameters change. This phenomenon plays an important role in discrete probability, statistical physics, computer science and economics.

This workshop will focus on the interplay between Combinatorics, Discrete Probability, Additive Number Theory and Computer Science with emphasis on a wide spectrum of analytical tools that are used there. One of the declared aims of the workshop is to foster interaction between researchers in these areas, discuss recent progress and communicate new results and ideas. We would also like to utilize this forum to make the state-of-the-art analytical techniques accessible to a broader audience, in particular graduate students.

Organizing Committee

Irit Dinur (Weizmann Institute of Science)
Ben Green (University of Cambridge)
Gil Kalai, Chair (Hebrew University)
Alex Samorodnitsky (Hebrew University)
Terence Tao (University of California, Los Angeles (UCLA))
Van Vu (Rutgers University)