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 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. 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 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. 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 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). 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 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. INI 1 12:30 to 13:30 Lunch at Wolfson Court 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. INI 1 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. 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 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...). 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 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). 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 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. 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 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. 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 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. INI 1 18:45 to 19:30 Dinner at Wolfson Court (residents only)