Quantitative and Computational Aspects of Metric Geometry

January 12 - 16, 2009

Schedule

All times in this Schedule are Pacific Time (PT)

Monday, January 12, 2009

Morning Session
8:00 - 9:00 Check-In/Breakfast (Hosted by IPAM)
9:00 - 10:00
Assaf Naor (New York University)

Embeddings of Discrete Groups and the Speed of Random Walks

10:00 - 10:15 Break
10:15 - 11:15
Yury Makarychev (Microsoft Research New England)

Integrality Gaps for Sherali-Adams Relaxations

11:15 - 11:30 Break
11:30 - 12:30
Sanjeev Arora (Princeton University)

Passing algorithms and better LP decoding

12:30 - 2:00 Lunch (on your own)

Afternoon Session
2:00 - 3:00
Nathan (Nati) Linial (Hebrew University)

Combinatorics meets topology
PDF Presentation
3:00 - 3:15 Break
3:15 - 4:15
4:30 - 6:00 Poster Session & Reception (Hosted by IPAM)

Tuesday, January 13, 2009

Morning Session
8:00 - 9:00 Continental Breakfast
9:00 - 10:00
Uriel Feige (Weizmann Institute of Science)

Interchanging distance and capacity in probabilistic mappings
Presentation (PowerPoint File)
10:00 - 10:15 Break
10:15 - 11:15
11:15 - 11:30 Break
11:30 - 12:30
Robert Krauthgamer (Weizmann Institute of Science)

Overcoming the L_1 Non-Embeddability Barrier
Presentation (PowerPoint File)
12:30 - 2:00 Lunch (on your own)

Afternoon Session
2:00 - 3:00 Gregory Margulis - "Homogeneous Dynamics and Number Theory" - Part of "Distinguished Lecture Series" at UCLA Math Department
3:00 - 3:15 Break
3:15 - 4:15
Alain Valette (Université de Neuchâtel)

Proper isometric actions of wreath products.
PDF Presentation

Wednesday, January 14, 2009

Morning Session
8:00 - 9:00 Continental Breakfast
9:00 - 10:00
Anupam Gupta (Carnegie-Mellon University)

How to Complete a Doubling Metric
PDF Presentation
10:00 - 10:15 Break
10:15 - 11:15
11:15 - 11:30 Break
11:30 - 12:30
Moses Charikar (Princeton University)

 

12:30 - 2:00 Lunch (on your own)

Afternoon Session
2:00 - 3:00 Gregory Margulis - "Homogeneous Dynamics and Number Theory" - Part 2 in MS6627 (Math building next door)
3:00 - 3:15 Break
3:15 - 4:15
Alexandr Andoni (Massachusetts Institute of Technology)

Approximating Edit Distance in Near-Linear Time
Presentation (PowerPoint File)

Thursday, January 15, 2009

Morning Session
8:00 - 9:00 Continental Breakfast
9:00 - 10:00
Tatiana Toro (University of Washington)

Cones of measures
PDF Presentation
10:00 - 10:15 Break
10:15 - 11:15
William Johnson (Texas A&M University - College Station)

Lipschitz p-summing mappings
PDF Presentation
11:15 - 11:30 Break
11:30 - 12:30
Gideon Schechtman (Weizmann Institute of Science)

Diamonds and super-reflexivity
PDF Presentation
12:30 - 2:00 Lunch (on your own)

Afternoon Session
2:00 - 3:00
Nir Ailon (Google Research)

Efficient Dimension Reduction
PDF Presentation
3:00 - 3:15 Break
3:15 - 4:15
Yuval Rabani (Technion - Israel Institute of Technology)

Explicit construction of a small epsilon-net for linear threshold functions


Friday, January 16, 2009

Morning Session
8:00 - 9:00 Continental Breakfast
9:00 - 10:00
Ofer Neiman (Hebrew University)

 

10:00 - 10:15 Break
10:15 - 11:15
Konstantin Makarychev (IBM Thomas J. Watson Research Center)

Local Global Tradeoffs in Metric Embeddings

11:15 - 11:30 Break
11:30 - 12:30
Leonard Schulman (California Institute of Technology)

Geometry-based sampling in learning and classification
Presentation (PowerPoint File)