Entrance hall of the ICMS

Geometry and Algorithms

Apr 16, 2007 - Apr 21, 2007

Heriot-Watt University, Edinburgh


Name Institution
Ball, Keith ICMS
Jerrum, Mark Queen Mary, University of London
Naor, Assaf New York University

Additional Scientific Advisors

Sanjeev Arora Professor, Princeton

Moses Charikar Professor, Princeton

Jiri Matousek Professor Charles University, Prague

Yuri Rabinovich Professor, Haifa


Short Report

During the last 15 years or so, it has become clear that many problems in theoretical computer science are actually geometric problems in disguise. In other cases, the problems are so complex that the best available approximation algorithms were devised by embedding the underlying structure into a familiar geometry so that it becomes “geometrically obvious” what to do. This general philosophy led to the best currently available algorithms for tackling a long list of computationally hard problems and in consequence the embedding method is one of the hottest topics in theoretical computer science. This meeting brought together mathematicians and computer scientists working in this fertile area to enable them to see both sides of the picture. Its second aim was to advertise the field to British researchers (especially young ones). The expository talks, which were intended to enable both groups to understand each other’s language, were extremely well prepared and clear.

Participants list and links to available presentations are further down this page.

Download the pdf file of the full report


The workshop will begin on Monday 16 April and finish midday on Saturday 21 April 2007. Participation is by invitation only.

The workshop will include a mini-course of 3 1-hour lectures, intended to provide a grounding in geometric embeddings and their relationship to algorithms. This will take place on Monday 16 April so that graduate students who wish to attend the workshop will be better equipped to follow the research talks that occupy the rest of the week. There will also be an organised problem session.

The Workshop will be held at Heriot-Watt University. The campus is on the western edge of the city, near the airport, with excellent public transport to and from Edinburgh city centre. The easiest way to get there from the airport is by taxi at a cost of about £10.00. There is no direct bus from the airport to HW. If you arrive by train or coach in central Edinburgh, there are a number of buses that will take you directly to the campus.

The university's website has a map showing the location of the university and instructions on how to reach it by various forms of transport, http://www.hw.ac.uk/home/dir/40/edinburgh-campus then choose ‘Edinburgh Campus Maps and Directions’.

Audio/Visual Facilities

The Cedar Room will have a data projector, an overhead projector, a laptop, a whiteboard, a blackboard and flipcharts.

Accommodation and Facilities
Single study-bedrooms have been reserved at Heriot-Watt University. All rooms have a private shower and toilet and a telephone. The telephone will access incoming calls. You need to buy a telephone card from Reception in order to make outgoing calls. Each room also has an internet point should you wish to bring your laptop, although there is a charge for this service. We have arranged email access in some of the central computer labs and the Library.

On arrival go to the main University and Conference Centre Reception in the James Watt Centre which is manned 24 hours. You may check into your room from 14.00 on the day of arrival. Your room must be vacated by 10.00 on the day of departure. There is a £20.00 charge for any bedroom key not returned to Reception by 11.00 on the morning of departure. Please note that if you do not check out by noon, you will be charged for a full night of accommodation. If you are not leaving immediately, luggage may be left temporarily in the baggage room at James Watt Centre Reception.

Meals and Refreshments
Breakfast will be provided for Heriot-Watt University residents for the period of their stay in the Middle Floor Dining Room. Lunch will be provided on weekdays only (Monday 16 April to Friday 20 April) outside the Cedar Room where the lectures are being held.

Evening meals will be provided on campus in the Middle Floor Dining Room on Monday, Tuesday, Wednesday and Friday from 17.15 to 19.00.

There will be a buffet supper (free of charge to delegates) in the College Lounge on the evening of Sunday 15 April between 19.00 and 20.30. Participants may register for the workshop during this buffet. There will also be an opportunity to register on Monday morning prior to the first talk.

A Workshop Dinner will be held on Thursday 19 April in Scholars Restaurant at Heriot-Watt. Participants will be asked to pay for this workshop dinner.

Financial Matters

The workshop grant will cover the cost of single en-suite bed and breakfast accommodation at Heriot-Watt. Lunches and evening meals Mon-Fri inclusive on campus and the Sunday evening buffet supper will also be provided. Please note that we cannot reimburse any meals taken off campus.

Participants are expected to cover their own travel expenses. It is also anticipated that the cost of the workshop dinner on the Thursday evening will be covered by participants.

Under the terms of our EPSRC funding we are required to charge a 30.00 GBP registration fee to cover costs not admissible under the grant. Please contact ICMS if this fee will be difficult for you to pay, as we may be able to waive this cost for some graduate students. Otherwise, you will be advised about payment methods at a later date.


Monday 16 April
08.30 - 09.00 Registration
09.00 - 10.00 Gideon Schechtman(Weizmann Institute)
Tight linear embeddings of normed spaces
10.00 - 11.00 Guy Kindler (Weizmann Institute)
How to get hardness results from integrality gaps Presentation
11.00 - 11.30 Coffee/tea
11.30 - 12.30 Piotr Indyk (Massachusetts Institute of Technology)
Uncertainty principles, extractors, and explicit embeddings of L2 into L1
12.30 - 14.00 Lunch
14.00 - 15.00 Charles Fefferman (Princeton University)
Extension and interpolation of functions
15.00 - 16.00 Moses Charikar (Princeton University)
Tighter local versus global properties for metric spaces
16.00 - 16.30 Coffee/tea
16.30 - 17.30 Michael Elkin (Ben Gurion University)
Low stretch spanning trees
Presentation | Open questions

Tuesday 17 April
09.00 - 10.00 Avner Magen (University of Toronto)
Integrality gap of 2-o(1) for Vertex Cover in the SDP Lovasz Schrijver lift and project system Presentation
10.00 - 11.00 Sanjeev Arora (Princeton University)
Geometry and approximation algorithms for NP-hard problems: a survey
11.00 - 11.30 Coffee/tea
11.30 - 12.30 Nathan Linial (Hebrew University)
The geometry of graphs - some open questions See recent talks section of this website
12.30 - 14.00 Lunch
14.00 - 16.00 Open problem solving
16.00 - 16.30 Coffee/tea

Wednesday 18 April
09.00 - 10.00 Ryan O’Donnell (Carnegie Mellon University)
Understanding parallel repetition requires understanding foams Presentation
10.00 - 11.00 Bruce Kleiner (Yale University)
Differentiation and bilipschitz embedding problems Presentation
11.00 - 11.30 Coffee/tea
11.30 - 12.30 Jeff Cheeger (Courant Institute, New York University)
Generalized differentiation and nonembedding in L^1
12.30 - 14.00 Lunch
14.00 onwards Free afternoon

Thursday 19 April
09.00 - 10.00 Shmuel Weinberger (University of Chicago)
Coarse embeddings of discrete groups and their applications
10.00 - 11.00 Vincent Lafforgue (Université de Paris 7)
Expanders with no uniform embedding in a uniformly convex Banach space
11.00 - 11.30 Coffee/tea
11.30 - 12.30 Assaf Naor (Courant Institute)
Isomorphic uniform convexity in metric spaces
12.30 - 14.00 Lunch
14.00 - 15.00 Manor Mendel (Open University of Israel)
Metric dichotomies Presentation
15.00 - 16.00 Satish Rao (University of California, Berkeley)
Learning mixtures of geometric distributions
16.00 - 16.30 Coffee/tea
16.30 - 17.30 Lior Silberman (Harvard University)
Property (T) is recursively enumerable

Friday 20 April
09.00 - 10.00 Yair Bartal (Hebrew University of Jerusalem and Caltech)
Advances in metric embedding theory
10.00 - 11.00 Ofer Neiman (Hebrew University)
Embedding metric spaces in their intrinsic dimension Presentation
11.00 - 11.30 Coffee/tea
11.30 - 12.30 Robert Krauthgamer (IBM Almaden Research Centre)
Lower bounds for edit distance estimation Presentation
12.30 - 14.00 Lunch
14.00 - 15.00 Yuval Rabani (Technion, Israel Institute of Technology)
Low distortion embeddings for edit distance Presentation
15.00 - 16.00 Ittai Abraham (Hebrew University of Jerusalem)
Local embeddings of metric spaces
16.00 - 16.30 Coffee/tea
16.30 - 17.30 Romain Tessera (Vanderbilt University)Quantitative property A and embeddings of metric spaces into Banach spaces

Saturday 21 April

09.00 - 10.00 James Lee (University of Washington, Seattle)
Meditations on planar graphs
10.00 - 11.00 Santosh Vempala (Georgia Institute of Technology and MIT)
Dispersion of mass and the complexity of randomized algorithms I
11.00 - 11.30 Coffee/tea
11.30 - 12.30 Luis Rademacher (Massachusetts Institute of Technology)
Dispersion of mass and the complexity of randomized algorithms II Presentation
12.30 Workshop closes


Name Institution
Abraham, Ittai Hebrew University of Jerusalem
Ambrus, Gergely University College London
Arora, Sanjeev Princeton University
Austin, Tim University of California at Los Angeles
Ball, Keith ICMS
Bartal, Yair Hebrew University of Jerusalem & Caltech
Charikar, Moses Princeton University
Chawla, Shuchi University of Wisconsin, Madison
Cheeger, Jeff New York University
Christofides, Demetres University of Cambridge
Creed, Patrick University of Edinburgh
Cryan, Mary University of Edinburgh
Csornyei, Marianna University College London
Elkin, Michael Ben-Gurion University
Fefferman, Charles Princeton University
Gupta, Anupam Carnegie Mellon University
Hatami, Hamed University of Toronto
Indyk, Piotr Massachusetts Institute of Technology (MIT)
Jerrum, Mark Queen Mary, University of London
Johnson, William Texas A&M University
Khot, Subhash Georgia Tech
Kindler, Guy Hebrew University
Kleiner, Bruce Courant Institute
Krauthgamer, Robi IBM Almaden Research Center
Lafforgue, Vincent Université de Paris 7
Lee, James University of Washington, Seattle
Lehec, Joseph University College London
Lindenstrauss, Joram Hebrew University of Jerusalem
Lindenstrauss, Naomi Hebrew University of Jerusalem
Linial, Nati Hebrew University of Jerusalem
Magen, Avner Univeristy of Toronto
Matthews, James University of Edinburgh
Mendel, Manor The Open University of Israel
Naor, Assaf New York University
Neiman, Ofer Hebrew University of Jerusalem
O'Donnell, Ryan Carnegie Mellon University
Pansu, Pierre Université Paris-Sud
Preiss, David University of Warwick
Prodromou, Maria University College London
Rabani, Yuval Technion, Israel Institute of Technology
Rabinovich, Yuri University of Haifa
Rademacher, Luis Massachusetts Institute of Technology (MIT)
Randrianantoanina, Beata Miami University
Rao, Satish University of California, Berkeley
Schechtman, Gideon Weizmann Institute of Science
Silberman, Lior Harvard University
Tessera, Romain Vanderbilt University
Vempala, Santosh Georgia Tech & MIT
Weinberger, Shmuel University of Chicago