Quantitative and Computational Aspects of Metric Geometry

January 12 - 16, 2009

Schedule


Monday, January 12, 2009

9:00 - 10:00
Assaf Naor (New York University)

Embeddings of Discrete Groups and the Speed of Random Walks

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

Integrality Gaps for Sherali-Adams Relaxations

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

Passing algorithms and better LP decoding

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

Combinatorics meets topology
PDF Presentation

3:15 - 4:15

Tuesday, January 13, 2009

9:00 - 10:00
Uriel Feige (Weizmann Institute of Science)

Interchanging distance and capacity in probabilistic mappings
Presentation (PowerPoint File)

10:15 - 11:15
11:30 - 12:30
Robert Krauthgamer (Weizmann Institute of Science)

Overcoming the L_1 Non-Embeddability Barrier
Presentation (PowerPoint File)

3:15 - 4:15
Alain Valette (Université de Neuchâtel)

Proper isometric actions of wreath products.
PDF Presentation


Wednesday, January 14, 2009

9:00 - 10:00
Anupam Gupta (Carnegie-Mellon University)

How to Complete a Doubling Metric
PDF Presentation

10:15 - 11:15
11:30 - 12:30
Moses Charikar (Princeton University)

 

3:15 - 4:15
Alexandr Andoni (Massachusetts Institute of Technology)

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


Thursday, January 15, 2009

9:00 - 10:00
Tatiana Toro (University of Washington)

Cones of measures
PDF Presentation

10:15 - 11:15
William Johnson (Texas A&M University - College Station)

Lipschitz p-summing mappings
PDF Presentation

11:30 - 12:30
Gideon Schechtman (Weizmann Institute of Science)

Diamonds and super-reflexivity
PDF Presentation

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

Efficient Dimension Reduction
PDF Presentation

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

9:00 - 10:00
Ofer Neiman (Hebrew University)

 

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

Local Global Tradeoffs in Metric Embeddings

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

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