skip to content

Timetable (DANW01)

Embedding workshop

Monday 10th January 2011 to Friday 14th January 2011

Monday 10th January 2011
09:00 to 09:55 Registration
09:55 to 10:00 Welcome from Sir David Wallace (INI Director)
10:00 to 11:00 B Bukh ([Cambridge])
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.
11:00 to 11:30 Morning coffee
11:30 to 12:30 R Krauthgamer (Weizmann Institute of Science)
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.
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 N Linial (Hebrew University of Jerusalem)
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.
15:00 to 15:30 Afternoon tea
15:30 to 16:30 M Sapir ([Vanderbilt])
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.
16:30 to 17:30 JA Chavez-Dominguez ([Texas A&M])
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.
17:30 to 18:30 Welcome wine reception
18:45 to 19:30 Dinner at Wolfson Court (residents only)
Tuesday 11th January 2011
10:00 to 11:00 A Sidiropoulos (Toyota Technological Institute)
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).
11:00 to 11:30 Morning coffee
11:30 to 12:30 M Mendel ([Open University of Israel])
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.
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 Y Rabani (Hebrew University of Jerusalem)
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.
15:00 to 15:30 Afternoon tea
15:30 to 16:30 N Alon ([Tel Aviv University and IAS, Princeton])
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.
16:30 to 17:30 A Valette ([Neuchâtel])
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...).
18:45 to 19:30 Dinner at Wolfson Court (residents only)
Wednesday 12th January 2011
10:00 to 11:00 A Andoni (Microsoft Research)
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.
11:00 to 11:30 Morning coffee
11:30 to 12:30 L Saloff-Coste ([Cornell])
A survey on random walks on groups
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 G Arzhantseva ([Vienna])
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.
15:00 to 15:30 Afternoon Tea
15:30 to 17:30 Open problem session INI 1
18:45 to 19:30 Dinner at Wolfson Court (residents only)
Thursday 13th January 2011
10:00 to 11:00 J Lee ([Washington])
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).
11:00 to 11:30 Morning coffee
11:30 to 12:30 G Schechtman (Weizmann Institute of Science)
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.
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 G Yu ([Vanderbilt])
Embeddings and topological rigidity
I will discuss the relations between embedability and topological rigidity of manifolds.
16:30 to 17:30 A Naor ([New York])
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.
19:30 to 22:00 Conference Dinner at Emmanuel College
Friday 14th January 2011
10:00 to 11:00 N Ozawa ([Tokyo])
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.
11:00 to 11:30 Morning coffee
11:30 to 12:30 P Indyk ([MIT])
Topics in Sparse Recovery
12:30 to 13:30 Lunch at Wolfson Court
14:00 to 15:00 S Khot ([New York])
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.
15:00 to 15:30 Afternoon tea
15:30 to 16:30 KJ Swanepoel (London School of Economics)
Equilateral sets in normed spaces
This talk will be a survey about what is known about equilateral sets in normed spaces, mostly finite dimensional.
16:30 to 17:30 F Baudier ([Texas A&M])
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.
18:45 to 19:30 Dinner at Wolfson Court (residents only)
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons