# Seminars (DAN)

Videos and presentation materials from other INI events are also available.

Search seminar archive

Event When Speaker Title Presentation Material
DANW01 10th January 2011
10:00 to 11:00
B Bukh Complexity of spatial embeddings of graphs
We introduce a measure of topological complexity of an embedding of a graph into R^3. We show that the notion strengthens the crossing number for graph embeddings in R^2, and that the complexity of expander graphs is high, as expected. We will also discuss the questions related to generalisations to higher dimensions. Joint work with Alfredo Hubard.
DANW01 10th January 2011
11:30 to 12:30
Vertex sparsifiers: New results from old techniques (and some open questions)
Given a capacitated graph G = (V,E) and a set of terminals $K \subseteq V$, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a simple'' graph? What if we allow H to be a convex combination of simple graphs? And is the question easier if we wanted H to maintain the distances among the terminals (rather than flows)?

Joint work with Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam-Cohen and Kunal Talwar.
DANW01 10th January 2011
14:00 to 15:00
N Linial Topology and probability? What a strange combination...
I will talk about various ways in which the probabilistic method can be applied to study various problems in topology.
DANW01 10th January 2011
15:30 to 16:30
Hilbert space compression of groups and dimension growth
I am going to talk about joint results with Arzhantseva, Guba, Drutu and Dranishnikov. It turned out that the same method is used to compute the Hilbert compression of a group (in particular, the Thompson group F) and its dimension growth. Some open problems will be discussed also.
DANW01 10th January 2011
16:30 to 17:30
Duality for Lipschitz p-summing operators
A theorem of J. Bourgain states that any finite metric space can be embedded into a Hilbert space with distortion proportional to the logarithm of the number of points. In fact Bourgain's embedding has a richer structure, that of a Lipschitz p-summing operator. These operators were introduced by J. Farmer and W. B. Johnson, and generalize the concept of a linear p-summing operator between Banach spaces . In this talk we identify the dual of the space of Lipschitz p-summing operators from a fi nite metric space to a normed space, answering a question of Farmer and Johnson. Furthermore, we use it to give a characterization of the non-linear concept of Lipschitz p-summing operator between metric spaces in terms of linear operators between certain Banach spaces.
DANW01 11th January 2011
10:00 to 11:00
Discrete differentiation and local rigidity of smooth sets in the plane
We exhibit an infinite doubling metric space whose n-point subsets require distortion sqrt(log n/log log n) to embed into L_1. This nearly matches the upper bound of sqrt(log n) (Gupta-Krauthgamer-Lee 2003) and improves over the best previous bound of (log n)^c for some c > 0 (Cheeger-Kleiner-Naor 2009). Furthermore, this offers a nearly tight integrality gap for a weak version of the Goemans-Linial SDP for Sparsest Cut, matching the upper bound of Arora-Lee-Naor (2005). We discuss how our results might lead to a resolution of the full Goemans-Linial conjecture.

Following the general approach developed by Cheeger and Kleiner (2006), our lower bound uses a differentiation argument to achieve local control on the cut measure, followed by a classification step of the cuts that can appear. In order to get tight bounds, the classification step has to deal with sets which satisfy only a weak average regularity assumption, meaning that we have to control not just "99%-structured sets," but "1%-structured" sets as well. This weak regularity is achieved via a random differentiation argument which measures the variation of the function along randomly chosen subdivisions of geodesics.

Our lower bound space is a 2-dimensional complex which takes inspiration from both the Heisenberg group and the diamond graphs.

This is joint work with James R. Lee (University of Washington).
DANW01 11th January 2011
11:30 to 12:30
M Mendel Ultrametric subsets with large Hausdorff dimension
We show that for any 1>ε>0, any metric space X contains a subset Y which is O(1/ε) equivalent to an ultrametric and dimH(Y)>(1-ε)dimH(X), where dimH is the Hausdorff dimension. The dependence on ε is tight up-to a constant multiplicative factor.

This result can be viewed as high distortion metric analog of Dvoretzky theorem. Low distortion analog of Dvoretzky theorem is impossible since there are examples of compact metric spaces of arbitrary large Hausdorff dimension for which any subset that embeds in Hilbert space with distortion smaller than 2 must have zero Hausdorff dimension.
DANW01 11th January 2011
14:00 to 15:00
Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
The celebrated dimension reduction lemma of Johnson and Lindenstrauss has numerous computational and other applications. Due to its application in practice, speeding up the computation of a Johnson-Lindenstrauss style dimension reduction is an important question. Recently, Dasgupta, Kumar, and Sarlos (STOC 2010) constructed such a transform that uses a sparse matrix. This is motivated by the desire to speed up the computation when applied to sparse input vectors, a scenario that comes up in applications. The sparsity of their construction was further improved by Kane and Nelson (ArXiv 2010).

We improve the previous bound on the number of non-zero entries per column of Kane and Nelson. We also improve the amount of randomness needed to generate the matrix. Our results are obtained by connecting the moments of an order 2 Rademacher chaos to the combinatorial properties of random Eulerian multigraphs. Estimating the chance that a random multigraph is composed of a given number of node-disjoint Eulerian components leads to a new tail bound on the chaos. Our estimates may be of independent interest, and as this part of the argument is decoupled from the analysis of the coefficients of the chaos, we believe that our methods can be useful in the analysis of other chaoses.

Joint work with Vladimir Braverman and Rafail Ostrovsky.
DANW01 11th January 2011
15:30 to 16:30
N Alon A non-linear lower bound for planar epsilon-nets
After a brief description of the notion of epsilon-nets for range spaces and of the main known results about them, I will show that the minimum possible size of an epsilon-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/epsilon. This settles a problem raised by Matousek, Seidel and Welzl in 1990.
DANW01 11th January 2011
16:30 to 17:30
A Valette Behaviour of Hilbert compression for groups, under group constructions
If $(X,d)$ is a metric space, the Hilbert compression of $X$ is the supremum of all $\alpha$'s for which there exists a Lipschitz embedding $f$ from X to a Hilbert space, such that $C.d(x,y)^\alpha \leq \|f(x)-f(y)\|$ for every $x,y\in X$. When $G$ is a finitely generated group, Hilbert compression is a quasi-isometry invariant which has been related to concepts such as exactness, amenability, Haagerup property. In this survey talk, we will review the known results about the range of this invariant, then we will move on to some recent results (due to Naor-Peres, Li, Dreesen) on the behaviour of Hilbert compression under various group constructions (wreath products, free and amalgamated products, HNN-extensions, etc...).
DANW01 12th January 2011
10:00 to 11:00
Norm Estimation, Precision Sampling, and Rademacher Type
We describe new algorithms to compute norms of a vector in a stream, which can be seen as linear embeddings into certain low-dimensional "computational spaces". In particular, we show that for a variety of settings, simple algorithms follow from the application of a single simple probabilistic technique, called Precision Sampling. These settings include classic scenarios such as l_p norms for p\in(0,2] and p>2, as well as mixed norms l_p(l_q). In the latter case, we show how (a natural generalization of) the Rademacher type yields essentially tight bounds for all regimes p,q>0.

Precision Sampling itself addresses the problem of estimating a sum of reals \sum a_i from weak estimates of each a_i\in[0,1]. More precisely, one chooses in advance "precisions" w_i>=1 for each i and obtains an estimate of a_i within additive 1/w_i. The core question is: what is the best trade-off between the approximation to \sum a_i and the total precision, \sum_i w_i ?

Joint work with Robert Krauthgamer and Krzysztof Onak.
DANW01 12th January 2011
11:30 to 12:30
A survey on random walks on groups
DANW01 12th January 2011
14:00 to 15:00
Coarse non-amenability and coarse embeddings
The concept of coarse embedding was introduced by Gromov in 1993. It plays an important role in the study of large-scale geometry of groups and the Novikov higher signature conjecture. Guoliang Yu's property A is a weak amenability-type condition that is satisfied by many known metric spaces. It implies the existence of a coarse embedding into a Hilbert space.

We construct the first example of a metric space with bounded geometry which coarsely embeds into a Hilbert space, but does not have property A. This is a joint work with Erik Guentner and Jan Spakula.
DANW01 13th January 2011
10:00 to 11:00
Cover times of graphs, majorizing measures, and the Gaussian free field
The cover time of a finite graph (the expected time for the simple random walk to visit all the vertices) has been extensively studied, yet a number of fundamental questions have remained open. We present a connection between the cover time, the discrete Gaussian free field on the underlying graph, and the Fernique-Talagrand theory of majorizing measures. At its most basic level, this involves embedding the graph into Euclidean space via the effective resistance, and then studying the associated Gaussian process (the image points under random projection) using the geometry of the resistance metric, in combination with Talagrand's ultrametric interpretation of majorizing measures.

This allows us resolve a number of open questions. Winkler and Zuckerman (1996) defined the blanket time (when the empirical distribution if within a factor of 2, say, of the stationary distribution) and conjectured that the blanket time is always within O(1) of the cover time. Aldous and Fill (1994) asked whether there is a deterministic polynomial-time algorithm that computes the cover time up to an O(1) factor. The best approximation factor found so far for both these problems was (log log n)^2 for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000). We use the aforementioned connection to deduce a positive answer to the question of Aldous and Fill and to establish the conjecture of Winkler and Zuckerman. These results extend to arbitrary reversible finite Markov chains

This is joint work with Jian Ding (U. C. Berkeley) and Yuval Peres (Microsoft Research).
DANW01 13th January 2011
11:30 to 12:30
Tight embedding of subspaces of $L_p$ in $\ell_p^n$ for even $p$
Given $1\le p\infty$ and $k$ what is the minimal $n$ such that $\ell_p^n$ almost isometrically contain all $k$-dimensional subspaces of $L_p$? I'll survey what is known about this problem and then concentrate on a recent result, basically solving the problem for even $p$. The proof uses a recent result of Batson, Spielman and Srivastava.
DANW01 13th January 2011
15:30 to 16:30
Embeddings and topological rigidity
I will discuss the relations between embedability and topological rigidity of manifolds.
DANW01 13th January 2011
16:30 to 17:30
Recent work of Nigel Kalton
Nigel Kalton passed away on August 2010. Shortly before his death, he sent me several remarkable preprints that contain major progress on embedding theory. In this talk I will present some of his new results, explain at least one of his beautiful proofs in detail, and describe the significance of these results and some problems that remain open.
DANW01 14th January 2011
10:00 to 11:00
ME embeddings for groups
Two countable discrete groups $G$ and $H$ are said to be measure equivalent, or ME in short, if there is a standard measure space which carries commuting measure-preserving actions of $G$ and $H$ such that each of actions has a fundamental domain of finite measure. For example lattices of a locally compact group are ME to each other. The notion of measure equivalence is introduced by Gromov as a younger brother of quasi-isometry for groups. I will give a survey on ME embeddings.
DANW01 14th January 2011
11:30 to 12:30
Topics in Sparse Recovery
DANW01 14th January 2011
14:00 to 15:00
On the Unique Games Conjecture
This talk will survey recently discovered connections between the Unique Games Conjecture and computational complexity, algorithms, discrete Fourier analysis, and geometry.

The power-point presentation and a written article are available at the address below, though the talk will focus a bit more on the open problems and research directions.
DANW01 14th January 2011
15:30 to 16:30
Equilateral sets in normed spaces
This talk will be a survey about what is known about equilateral sets in normed spaces, mostly finite dimensional.
DANW01 14th January 2011
16:30 to 17:30
Coarse Lipschitz embeddings of expander graphs and cotype
In this talk we will discuss recent results of M. Ostrovskii about embeddings of graphs into graphs of bounded degree and Lipschitz embeddings of expanders. Then we will show how we can adapt his construction to prove that there exists a family of expander graphs whose coarse Lipschitz embedding (a.k.a quasi-isometric embedding) into a Banach space forces the target space to have trivial cotype. One wants to mention that the proof does not require a metric cotype approach'' and uses only classical Banach space theory.
DAN 19th January 2011
14:00 to 15:00
Maximal inequality for high-dimensional cubes
The talk will deal with the behaviour of the best constant in the Hardy-Littlewood maximal inequality in R^n when the dimension goes to infinity. More precisely, I will sketch a simple probabilistic proof of the following result (due to Aldaz): when the maximal function is defined by averaging over all centred cubes, the Hardy-Littlewood inequality does not hold with a constant independent of the dimension.
DAN 26th January 2011
14:00 to 15:00
Jordan's theorem on finite linear groups and its approximate Analogues
DAN 26th January 2011
15:15 to 16:15
On geometric incidences
DAN 28th January 2011
14:00 to 15:00
T Tao On Gromov's theorem on groups of polynominal growth and related topics
DAN 31st January 2011
14:00 to 15:00
On a conjecture of Snevily
DAN 1st February 2011
14:00 to 15:00
DAN 2nd February 2011
14:00 to 15:00
Applications of Discrete Analysis in Inapproximability of NP-hard Problems
DAN 4th February 2011
11:00 to 12:00
Self-affine sets and measures
DAN 9th February 2011
14:00 to 15:00
Plunnecke-type product set estimates in groups
DAN 9th February 2011
15:15 to 16:15
Multiplicative translates of subgroups in residue classes
DAN 11th February 2011
14:00 to 15:00
Linear threshold predicates and approximation resistance
DAN 12th February 2011
14:00 to 15:00
3 terms arithmetic progressions in finite fields (IV)
DAN 16th February 2011
14:00 to 15:00
Some remarks on Mahler's conjecture for convex bodies
Let $P(K)$ be the product of the volume of an origin symmetric convex body $K$ and its dual/polar body $K^*$. Mahler conjectured that $P(K)$ is minimized by a cube and maximized by a ball. The second claim of this conjecture was proved by Santalo; despite many important partial results, the first problem is still open in dimensions 3 and higher. In this talk we will discuss some recent progress and ideas concerning this conjecture.
DAN 18th February 2011
14:00 to 15:00
The Khinchine inequalities with optimal constants via ultra log-concavity
We shall present a new approach to the comparison of moments for sums of independent symmetric random variables, based on Walkup's theorem which states that the binomial convolution transform preserves log-concavity. This is a joint work with Piotr Nayar.
DAN 21st February 2011
14:00 to 15:00
O Guedon Concentration inequalities for log-concave measures
DAN 23rd February 2011
14:00 to 15:00
Row products of random matrices
We define the row product of K matrices of size d by n as a matrix of size d^K by n, whose rows are entry-wise products of rows of these matrices. This construction arises in certain computer science problems. We study to what extent the spectral and geometric properties of the row product of independent random matrices resemble those properties for a d^K by n matrix with independent random entries.
DAN 23rd February 2011
15:15 to 16:15
A Plagne From coding theory to Davenport constant
DAN 2nd March 2011
14:00 to 15:00
Vertices of high degree in the preferential attachment tree
The preferential attachment tree is the most basic model of evolving web graphs. At each stage of the process, a new vertex is added and joined to one of the existing vertices, with each vertex chosen with probability proportional to its current degree. In probability theory, this is also known as a Yule process. Much is known about this model, including the fact that the numbers of vertices of each small degree follow a power law''. Here we study in detail the degree sequence of the preferential attachment tree, looking at the vertices of large degrees as well as the numbers of vertices of each fixed degree. Our method is based on bounding martingale deviations, using exponential supermartingales. This is joint work with Graham Brightwell.
DAN 2nd March 2011
15:15 to 16:15
Polarisation problems
Let $u_1, u_2, ..., u_n$ be unit vectors in a Hilbert space $H$. The polarisation problem states that there is another unit vector $v$ in $H$, which is sufficiently far from the orthogonal complements of the given vectors in the sense that $\prod |(u_i, v)| \geq n^{-n/2}$. The strong polarisation problem asserts that there is choice of $v$ for which $\sum 1/ (u_i, v)^2 \leq n^2$ holds. These follow from the complex plank problem if $H$ is a complex Hilbert space, but for real Hilbert spaces the general conjectures are still open. We prove special cases by transforming the statements to geometric forms and introducing inverse eigenvectors of positive semi-definite matrices.
DAN 9th March 2011
14:00 to 15:00
Finding primes deterministically
DAN 9th March 2011
15:15 to 16:15
A Sen A new definition of influences of Boolean functions
The notion of influences of variables on Boolean functions is one of the central concepts in the theory of discrete harmonic analysis. We present a new definition of influences in product spaces of continuous distributions. Our definition is geometric, and for monotone sets it is identical with the measure of the boundary with respect to uniform enlargement. We prove analogues of the Kahn-Kalai-Linial (KKL) and Talagrand's influence sum bounds for the new definition. This result is then used to obtain an isoperimetric inequality for the Gaussian measure on R^n and the class of sets invariant under transitive permutation group of the coordinates. I will also discuss some statistical connection to this problem. This is joint work with Nathan Keller and Elchanan Mossel
DAN 16th March 2011
14:00 to 15:00
Spectrum of large non-hermitian random matrices
In this talk, we will revisit recent works of T. Tao, V. Vu and others on large non-hermitian random matrices with independent and identically distributed entries. We will explain the general strategy behind this class of problems. As a byproduct, we will explain why the generalized eigenvalues distribution of two independent matrices converges almost surely to the uniform measure on the Riemann sphere.
DAN 16th March 2011
15:15 to 16:15
G Lancien Coarse Lipschitz embeddings and asymptotic structure of Banach Spaces
The linear properties of Banach spaces considered in this talk will be the ex- istence of an equivalent asymptotically uniformly smooth (or convex) equivalent norm. We shall study the stability of these properties under various non linear transformations, but we will concentrate on the coarse Lipschitz embeddings (i.e. maps that are bi-Lipschitz for very large distances). These questions in relation with uniform asymptotic smoothness are now quite well understood. We will try to present the progress made last year by N.J. Kalton on the stability of uniform asymptotic convexity under coarse embeddings. We will focus on the use of some fundamental metric graphs or trees in the subject, and present a few open questions that we find interesting.
DANW02 28th March 2011
10:00 to 11:00
Threshold behaviour
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.
DANW02 28th March 2011
11:30 to 12:30
R Latala Tail and moment estimates for Rademacher chaos
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).

DANW02 28th March 2011
14:00 to 15:00
R O'Donnell The Fourier Entropy-Influence conjecture for certain classes of Boolean functions
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.
DANW02 28th March 2011
15:30 to 16:30
P Tetali Transportation and related inequalities in discrete spaces
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.
DANW02 28th March 2011
17:00 to 18:00
The power and weakness of randomness, when you are short on time (Rothschild Lecture)
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.
DANW02 29th March 2011
10:00 to 11:00
O Regev 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.
DANW02 29th March 2011
11:30 to 12:30
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.
DANW02 29th March 2011
14:00 to 15:00
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.
DANW02 29th March 2011
15:30 to 16:30
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.
DANW02 29th March 2011
16:30 to 17:30
N Anantharaman 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.
DANW02 30th March 2011
10:00 to 11:00
Sharp threshold for percolation on expanders
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.
DANW02 30th March 2011
11:30 to 12:30
P Dai Pra Convex decay of entropy in interacting systems
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.
DANW02 30th March 2011
15:30 to 16:30
S Khot A two prover one round game with strong soundness
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
DANW02 30th March 2011
16:30 to 17:30
Somewhere between Freiman's theorem and the Polynomial Freiman-Ruzsa conjecture
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.
DANW02 31st March 2011
10:00 to 11:00
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.
DANW02 31st March 2011
11:30 to 12:30
J Bennett 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.
DANW02 31st March 2011
15:30 to 16:30
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.
DANW02 31st March 2011
16:30 to 17:30
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.
DANW02 1st April 2011
10:00 to 11:00
On reverse hypercontractive inequalities
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 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).
DANW02 1st April 2011
11:30 to 12:30
G Kindler A quantitative version of the Gibbard-Satterthwaite theorem
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.
DANW02 1st April 2011
14:00 to 15:00
Large Deviation Principle for the Erdös-Renyi random graph
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.
DAN 5th April 2011
14:00 to 15:00
A Wigderson Arithmetic complexity and the sum of squares problem (I)
In this lecture I will survey basic models, results and problems on the computation of computing polynomials, such as DFT, symmetric polynomials, determinant, permanent, matrix multiplication and more...
DAN 5th April 2011
15:15 to 16:15
D Ellis Triangle-intersecting families of graphs
A family of graphs F on a fixed set of n vertices is said to be triangle-intersecting if for any two graphs G,H 2 F, G \ H contains a triangle. Simonovits and S´os conjectured that such a family has size at most 18 2(n2),and that equality holds only if F consists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycleintersecting family of graphs, then |F| · 18 2(n2). Equality holds only if F consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results in the theory of Boolean functions. We will then discuss some related open questions. All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).
DAN 7th April 2011
14:00 to 15:00
Multilinear Kakeya type inequalities and factorization
DAN 7th April 2011
15:15 to 16:15
A Wigderson Arithmetic complexity and the sum of squares problem (II)
This lecture will be largely independent from the first. I will explain the completeness of the determinant and permanent in respective classes of polynomials, and its importance to the P vs. NP problem. I will discuss the non commutative versions of their complexity, and show how these relate to the famous sum-of-squares problem. Then I'll mention some recent small progress on that problem and some of its variants.
DAN 12th April 2011
13:45 to 14:45
A Wigderson Explicit Euclidean Sections, Codes over the Reals and Expanders
Here is a basic problem, which comes under various names including "compressed sensing matrices", Euclidean sections of L1", "restricted isometries" and more. Find a subspace X or R^N such that every vector x in X has the same L1 and L2 norms (with proper normalization) up to constant factors. It is known that such subspaces of dimension N/2 exist (indeed "most" of them are), and the problem is to describe one explicitly. I will describe some progress towards this problem, based on extending the notion of expander codes from finite fields to the reals.
DAN 13th April 2011
13:45 to 14:45
On the Log-Concave Ensemble of random matrices
DAN 14th April 2011
13:45 to 14:45
Long Arithmetic Progressions in Sumsets
DAN 21st April 2011
14:00 to 15:00
The ferromagnetic Potts model: phase transition, gadgets and computational complexity
An instance of the Potts model is defined by a graph of interactions and a number q of different "spins". A configuration is this model is an assignment of spins to vertices. Each configuration has a weight, which in the ferromagnetic case is greater when more pairs of adjacent spins are alike. The classical Ising model is the special case of q=2 spins. We consider the problem of computing an approximation to the partition function, i.e., weighted sum of configurations, of an instance of the Potts model. Through the random cluster formulation it is possible to make sense of the partition function also for non-integer q. Yet another equivalent formulation is as the Tutte polynomial in the positive quadrant. About twenty years ago, Jerrum and Sinclair gave an efficient (i.e., polynomial-time) algorithm for approximating the partition function of a ferromagnetic Ising system. Attempts to extend this result to q­2 have been unsuccessful. At the same time, no convincing evidence has been presented to indicate that such an extension is impossible. In this talk, I sketch a recent result to the effect that, for q>2, approximating the partition function of the ferromagnetic Potts model is hard for a certain complexity class, which contains a large number of other approximation problems for which no efficient approximation algorithm is known. The reduction used to establish this result exploits a first-order phase transition, already known to exist when q>2, to construct a bi-stable combinatorial "gadget". Along the way, a hypergraph version of the Tutte polynomial arises quite naturally. This is joint work with Leslie Ann Goldberg, University of Liverpool.
DAN 27th April 2011
14:00 to 15:00
On various sum-product inequalities
DAN 27th April 2011
15:15 to 16:15
Randomized algorithms for the approximation of matrices
DAN 3rd May 2011
14:00 to 15:00
3-terms arithmetic progressions in finite fields (I)
DAN 4th May 2011
13:45 to 14:45
Correlation testing for affine invariant properties on $F_p^n$
Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f: F_p^n \rightarrow F_p$ with polynomials of degree at most $d \le p$ is non-negligible, while making only a constant number of queries to the function. This is an instance of {\em correlation testing}. In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analog of {\em proximity oblivious testing}, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree $d$ polynomials for some fixed $d$. We stress that our result holds also for non-linear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is an extension of a graph theoretical theorem of Erd\"os, Lov\'asz and Spencer to the context of additive number theory. Joint work with Hamed Hatami.
DAN 6th May 2011
14:00 to 15:00
3 terns arithmetic progressions in finite fields (II)
DAN 9th May 2011
14:00 to 15:00
3-terms arithmetic progressions in finite fields (III)
DAN 10th May 2011
14:00 to 15:00
S Bobkov Rates of convergence in the entropic central limit theorem
Abstract. Under moment conditions, we will be discussing asymptotic formulas for the entropy of sums of i.i.d. random variables. (Joint work with G. P. Chistyakov and F. G\"otze).
DAN 12th May 2011
14:00 to 15:00
3-terms arithmetic progressions in finite fields (IV)
DAN 18th May 2011
14:00 to 15:00
Discrete Ricci curvature with applications
We define a notion of discrete Ricci curvature for a metric measure space by looking at whether "small balls are closer than their centers are". In a Riemannian manifolds this gives back usual Ricci curvature up to scaling. This definition is very easy to apply in a series of examples such as graphs (eg the discrete cube has positive curvature). We are able to generalize several Riemannian theorems in positive curvature, such as concentration of measure and the log-Sobolev inequality. This definition also allows to prove new theorems both in the Riemannian and discrete case: for example improved bounds on spectral gap of the Laplace-Beltrami operator, and fast convergence results for some Monte Carlo Markov Chain methods.
DAN 19th May 2011
14:00 to 15:00
A curved Brunn-Minkowski inequality in the discrete cube
(Joint work with C.Villani) We try (and fail) to implement the displacement convexity property of Lott-Sturm-Villani to the discrete hypercube. Yet along the way we get new, unexpected results of a combinatorial and probabilistic nature, including a curved Brunn--Minkowski inequality on the discrete hypercube.
DAN 24th May 2011
14:00 to 15:00
How to Play Unique Games Against a Semi-Random Adversary
We study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an epsilon-fraction of all edges, and finally replaces ("corrupts'') the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1-epsilon)-satisfiable instance, so then the problem is as hard as in the worst case. We show however that we can find a solution satisfying a (1-delta)-fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is at least log k). Our result holds only for epsilon less than some absolute constant. We prove that if epsilon 1/2, then the problem is hard, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1-epsilon) satisfiable semi-random instance and (ii) the instance is at most delta satisfiable (for every delta > 0); the result assumes the 2-to-2 Unique Games conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-epsilon) satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an arbitrary (1-delta)-satisfiable instance (if epsilon > c delta, for some absolute constant c). Joint work with Alexandra Kolla and Yury Makarychev
DAN 25th May 2011
14:00 to 15:00
Favourite distances in high dimensions
DAN 25th May 2011
15:15 to 16:15
Y Makarychev Vertex Sparsifiers and Lipschitz Extendability
DAN 31st May 2011
14:00 to 15:00
Singular integrals in bad neighborhoods I: Singular integrals for Geometric Measure Theory
Very bad sets on which singular integrals are tame cannot be bad. They have to have the structure. This is the first topic in which we explain the solution of some old problems of Vitushkin, Denjoy, Painlev\'e, David--Semmes. The second lecture is mostly about probabilistic methods in taming the singular integrals in bad environment.
DAN 1st June 2011
14:00 to 15:00
Ricci curvature of Finsler manifolds, towards applications in the geometry of Banach spaces
I will introduce the notion of Ricci curvature for general Finsler manifolds. Bounding this curvature from below is equivalent to Lott, Sturm and Villani's curvature-dimension condition, and there are further applications (e.g., a Bochner-type formula and gradient estimates). I also would like to discuss some possible applications of this differential geometric technique to the geometry of Banach spaces.
DAN 1st June 2011
15:15 to 16:15
Computability and Complexity of Julia Sets
Studying dynamical systems is key to understanding a wide range of phenomena ranging from planetary movement to climate patterns to market dynamics. Various computational and numerical tools have been developed to address specific questions about dynamical systems, such as predicting the weather or planning the trajectory of a satellite. However, the theory of computation behind these problems appears to be very difficult to develop. In fact, little is known about computability of even the most natural problems arising from dynamical systems. In this talk I will survey the recent study of the computational properties of dynamical systems that arise from iterating quadratic polynomials on the complex plane. These give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. The theory behind them is even more fascinating, and the dynamical systems generating them are in many ways archetypal. I will present both positive and negative results on the computability and computational complexity of Julia sets.
DAN 6th June 2011
14:00 to 15:00
Singular integrals in bad neighborhoods II: Stochastic Optimal Control and sharp estimates of Singular Integrals
Very bad sets sets on which singular integrals are tame cannot be bad. They have to have the structure. This is the first topic in which we explain the solution of some old problems of Vitushkin, Denjoy, Painlev\'e, David--Semmes. The second lecture is mostly about probabilistic methods in taming the singular integrals in bad environment.
DAN 7th June 2011
14:00 to 15:00
Isoperimetric and concentration inequalities - equivalence and applications
Given a metric space equipped with a measure, various ways exist for studying the interaction between measure and metric. A very strong form is given by isoperimetric inequalities, which for a set of given measure, provide a lower bound on its boundary measure. A much weaker form is given by concentration inequalities, which quantify large-deviation behavior of measures of separated sets. There are also other tiers, interpolating between these two extremes, such as the tier of Sobolev-type inequalities. It is classical (by results of Cheeger, Maz'ya, Gromov--Milman andothers) that isoperimetric inequalities imply corresponding functional versions, which in turn imply concentration counterparts. However, in general, these implications cannot be reversed. We show that under a suitable (possibly negative) lower bound on the generalized Ricci curvature of a Riemannian-manifold-with-density, completely general concentration inequalities imply back their isoperimetric counterparts, up to dimension \emph{independent} bounds. Consequently, in such spaces, all of the above tiers of the hierarchy are equivalent, clarifying the role which curvature plays in the interaction between measure and metric. Several applications of this equivalence will be presented, ranging from Statistical Mechanics to Spectral Geometry. Time permitting, we will also present new \emph{sharp} isoperimetric inequalities, generalizing classical results due to P. L\'evy, Sudakov--Tsirelson and Borell, Gromov and Bakry--Ledoux, into one single form. The talk will be self-contained and accessible to all.
DAN 10th June 2011
14:00 to 15:00
Stochastic completeness for random walks and jump processes
DAN 14th June 2011
14:00 to 15:00
Is asymptotic extremal graph theory of dense graphs trivial?
Recent developments in asymptotic extremal combinatorics have provided powerful automatic and semi-automatic methods for proving theorems in the dense setting. For example I will show how relying completely on a computer, one can solve an old conjecture of Erdos and answer a question of Sidorenko and of Jagger, Stovicek and Thomason. These new discoveries raise the following fundamental question: is it possible to prove every true algebraic inequalities between graph densities using a finite amount of manipulation with densities of finitely many graphs?'' Although this question itself is not well-defined, various precise refinements of it are formulated independently by Razborov and Lovasz. I will present a joint theorem with Sergey Norin which answers many of these questions.
DAN 15th June 2011
15:30 to 16:30
Towards an entropy-based sumset calculus for additive combinatorics and convex geometry
We use common entropy-based tools to study two kinds of problems: the first of proving general cardinality inequalities for sumsets in possibly nonabelian groups, and the second of proving volume inequalities of interest in convex geometry and geometric functional analysis. We will spend most of our time on the discrete setting (joint work with A. Marcus and P. Tetali), introducing the notion of partition-determined functions, and presenting some basic new inequalities for the entropy of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Corollaries of the results for partition-determined functions include entropic analogues of general Pl\"unnecke-Ruzsa type inequalities, sumset cardinality inequalities in abelian groups generalizing inequalities of Gyarmati-Matolcsi-Ruzsa and Balister-Bollob\'as, and partial progress towards a conjecture of Ruzsa for sumsets in nonabelian groups. Time permitting, we will also mention some results in the continuous setting (joint work with S. Bobkov) including some Pl\"unnecke-type inequalities for Minkowski sums of convex sets, and an entropic generalization of V. Milman's reverse Brunn-Minkowski inequality.
DAN 15th June 2011
17:00 to 17:50
Quantitative geometry and efficient classification procedures
This talk will illustrate to non-experts the use of geometric methods to design efficient partitioning algorithms for discrete objects or, in some cases, to prove that such algorithms must fail to perform well. These connections show that combinatorial optimization problems are intimately related to classical questions in continuous geometry, and we will describe some recent progress on old questions that translates to the best known results on algorithmic problems of central interest. This talk will provide an introduction to geometric aspects of computational complexity via an examination of specific examples. No specialized background will be required.
DAN 21st June 2011
14:00 to 15:00
Applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra in Fixed-Parameter Tractability and Kernelization
Let $P$ be a decision problem (answers are yes or no). A parameterized problem $\Pi$ is a set of pairs $(x,k)$ where $x$ is an instance of $P$ and $k$ (usually an integer) is the parameter. One example is the $k$-Vertex Cover problem, where for a given graph $G$ we are to decide whether there is a set of $k$ vertices covering all edges of $G.$ A kernelization of $\Pi$ is a polynomial time algorithm that maps an instance $(x,k)\in \Pi$ to an instance $(x',k')\in \Pi$ (kernel) such that (i) $(x,k)$ is a yes-instance iff $(x',k')$ is a yes-instance, (ii) $k'\leq h(k)$ and $|x'|\leq g(k)$ for some functions $h$ and $g$, where $|x'|$ is the size of $x'$. For example, there is a kernelization of $k$-Vertex Cover reducing each pair ($G,k$) into ($H,k$), where $H$ has at most $2k$ vertices and $k^2$ edges. A parameterized problem is fixed-parameter tractable if it can be solved in time $O(f(k)|x|^{O(1)})$ for some function $f$ in $k$. It is well-known that a parameterized problem is fixed-parameter tractable iff it is decidable and admits a kernelization. We'll discuss applications of Discrete Harmonic Analysis, Probabilistic Method and Linear Algebra to some parameterized problems. We'll mainly discuss MaxLin2-AA: given a system of linear equations over GF(2) in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least $W/2+k,$ where $W$ is the total weight of all equations of the system. Solving an open question of Mahajan, Raman and Sikdar (2006,2009), we'll show that MaxLin2-AA is fixed-parameter tractable and admits a kernel with at most $O(k^2\log k)$ variables. Here we use Linear Algebra. This is a very recent result, see http://arxiv.org/abs/1104.1135 It is still unknown whether MaxLin2-AA admits a kernel with a polynomial number of equations (rather than variables), but we can prove that such a kernel exists for a number of special cases of MaxLin2-AA. Here we apply Probabilistic Method and Discrete Harmonic Analysis. In particular, we use the well-known (4,2)-Hypercontractive Inequality as well as its new version.
DAN 22nd June 2011
14:00 to 15:00
Gradient flows of the entropy for finite Markov chains
At the end of the nineties, Jordan, Kinderlehrer, and Otto discovered a new interpretation of the heat equation in R^n, as the gradient flow of the entropy in the Wasserstein space of probability measures. In this talk, I will present a discrete counterpart to this result: given a reversible Markov kernel on a finite set, there exists a Riemannian metric on the space of probability densities, for which the law of the continuous time Markov chain evolves as the gradient flow of the entropy.
DAN 22nd June 2011
15:30 to 16:30
The logarithmic Laplace transform in convex geometry
My plan is to give a slow introduction to the use of the logarithmic Laplace transform in obtaining bounds on the isotropic constants of convex bodies. We will review the proofs of Bourgain's n^{1/4} bound, the bound by the width of the thinshell, and the bound in term of the sub-gaussian coefficient. This talk is based on joint works with Ronen Eldan and with Emanuel Milman.
DAN 5th July 2011
14:00 to 15:00
Positive projections
If A is a set of n positive integers, how small can the set { (a,b) : a,b in A } be? Here as usual (a,b) denotes the HCF of a and b. This elegant question was raised by Granville and Roesler, who also reformulated it in the following way: given a set A of n points in the integer grid Z^d, how small can (A-A)^+, the projection of the difference set of A onto the positive orthant, be? Freiman and Lev gave an example to show that (in any dimension) the size can be as small as n^{2/3} (up to a constant factor). Granville and Roesler proved that in two dimensions this bound is correct, i.e. that the size is always at least n^{2/3}, and they asked if this holds in any dimension. After some background material, the talk will focus on recent developments, including a negative answer to the n^{2/3} question. (joint work with Bela Bollobas)