Embedding workshop
Monday 10th January 2011 to Friday 14th 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.

INI 1  
11:00 to 11:30  Morning coffee  
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 flowsparsifier 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 TalgamCohen and Kunal Talwar.

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

INI 1  
15:00 to 15:30  Afternoon tea  
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.

INI 1  
16:30 to 17:30 
Duality for Lipschitz psumming 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 psumming operator. These operators were introduced by J. Farmer and W. B. Johnson, and generalize the concept of a linear psumming operator between Banach spaces . In this talk we identify the dual of the space of Lipschitz psumming 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 nonlinear concept of Lipschitz psumming operator between metric spaces in terms of linear operators between certain Banach spaces.

INI 1  
17:30 to 18:30  Welcome wine reception  
18:45 to 19:30  Dinner at Wolfson Court (residents only) 
10:00 to 11:00 
Discrete differentiation and local rigidity of smooth sets in the plane
We exhibit an infinite doubling metric space whose npoint subsets
require distortion sqrt(log n/log log n) to embed into L_1. This
nearly matches the upper bound of sqrt(log n) (GuptaKrauthgamerLee 2003)
and improves over the best previous bound of (log n)^c for some c > 0
(CheegerKleinerNaor 2009). Furthermore, this offers a nearly tight
integrality gap for a weak version of the GoemansLinial SDP for Sparsest Cut, matching the upper bound of AroraLeeNaor (2005). We discuss how our results might lead to a resolution of the full GoemansLinial 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 2dimensional complex which takes inspiration from both the Heisenberg group and the diamond graphs.
This is joint work with James R. Lee (University of Washington).

INI 1  
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 upto 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.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
14:00 to 15:00 
Rademacher Chaos, Random Eulerian Graphs and The Sparse JohnsonLindenstrauss 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 JohnsonLindenstrauss 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 nonzero 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 nodedisjoint 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.

INI 1  
15:00 to 15:30  Afternoon tea  
15:30 to 16:30 
N Alon ([Tel Aviv University and IAS, Princeton]) A nonlinear lower bound for planar epsilonnets
After a brief description of the notion of epsilonnets for range spaces and of the main known results about them, I will show that the minimum possible size of an epsilonnet 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.

INI 1  
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 quasiisometry 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 NaorPeres, Li, Dreesen) on the behaviour of Hilbert compression under various group constructions (wreath products, free and amalgamated products, HNNextensions, etc...).

INI 1  
18:45 to 19:30  Dinner at Wolfson Court (residents only) 
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 lowdimensional "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 tradeoff between the approximation to \sum a_i and the total precision, \sum_i w_i ?
Joint work with Robert Krauthgamer and Krzysztof Onak.

INI 1  
11:00 to 11:30  Morning coffee  
11:30 to 12:30  A survey on random walks on groups  INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
14:00 to 15:00 
Coarse nonamenability and coarse embeddings
The concept of coarse embedding was introduced by Gromov in 1993. It plays an important role in the study of largescale geometry of groups and the Novikov higher signature conjecture. Guoliang Yu's property A is a weak amenabilitytype 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.

INI 1  
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) 
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 FerniqueTalagrand 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 polynomialtime 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 nvertex 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).

INI 1  
11:00 to 11:30  Morning coffee  
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.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
13:30 to 15:00  Free time  
15:00 to 15:30  Afternoon tea  
15:30 to 16:30 
Embeddings and topological rigidity
I will discuss the relations between embedability and topological rigidity of manifolds.

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

INI 1  
19:30 to 22:00  Conference Dinner at Emmanuel College 
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 measurepreserving 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 quasiisometry for groups. I will give a survey on ME embeddings.

INI 1  
11:00 to 11:30  Morning coffee  
11:30 to 12:30  Topics in Sparse Recovery  INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
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 powerpoint 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.

INI 1  
15:00 to 15:30  Afternoon tea  
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.

INI 1  
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 quasiisometric 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.

INI 1  
18:45 to 19:30  Dinner at Wolfson Court (residents only) 