Geometry and Algorithms
Apr 16, 2007 - Apr 21, 2007
Heriot-Watt University, Edinburgh
Organisers
| Name | Institution |
|---|---|
| Ball, Keith | University College London |
| 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
Arrangements
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.
Venue
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.
Programme
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 |
Participants
| 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 | University College London |
| 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 | Weizmann Institute of Science |
| Kleiner, Bruce | Yale University |
| 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 |