### Workshop on Geometry and Algorithms

#### October 29 - 31, 2008

Friend Center 006

Princeton University, Princeton NJ

**Organizers:**
**Sanjeev Arora**, Princeton University, arora at cs.princeton.edu
**Moses Charikar**, Princeton University, moses at cs.princeton.edu
**Bill Johnson**, Texas A&M, johnson at math.tamu.edu
**Assaf Naor**, NYU, naor at cims.nyu.edu

Presented under the auspices of the Special Focus on Hardness of Approximation.

#### Workshop Program:

This is a preliminary program.

**Wednesday, October 29, 2008**
9:00 - 10:10 Survey on Compressed Sensing
Piotr Indyk
10:10 - 10:50 break
10:50 - 11:25 Understanding Patterns in Data
Stephen Smale
11:25 - 12:00 Isotropic Principal Components
Santosh Vempala
12:00 - 2:00 lunch
2:00 - 2:35 On the geometry of graphs and L_1 embeddings
James Lee
2:35 - 3:10 Column subset selection, matrix factorization, and
eigenvalue optimization
Joel Tropp
3:10 - 3:45 TBA
Assaf Naor
3:45 - 4:25 break
4:25 - 5:00 Lower bounds for Sherali Adams via local-global metrics
Yury Makarychev
5:00 - 5:35 Metric Embeddings As Computational Primitives
Robi Krauthgamer
**Thursday, October 30, 2008**
9:00 - 9:35 Can cubic tiles be sphere-like?
Guy Kindler
9:35 - 10:10 Contraction and Expansion of Convex Sets
Leonard Schulman
10:10 - 10:50 break
10:50 - 11:25 Explicit Euclidean sections from expander codes
Venkat Guruswami
11:25 - 12:00 Exact Low-rank Matrix Completion via Convex Optimization
Ben Recht
12:00 - 2:00 lunch
2:00 - 2:35 Manifold Learning: A geometric perspective on learning
theory and algorithms
Partha Niyogi
2:35 - 3:10 Open problems in learning low dimensional representations
Sanjoy Dasgupta
3:10 - 3:45 Applications of Compressed Sensing to Biology
Anna Gilbert
3:45 - 4:25 break
4:25 - 5:35 Rump session: open problems, brief announcements, etc
6:15 Banquet at Palmer House
**Friday, October 31, 2008**
9:00 - 9:35 Explicit construction of a small epsilon-net for linear
threshold functions
Yuval Rabani
9:35 - 10:10 Graph norms and Sidorenko's conjecture
Hamed Hatami
10:10 - 10:40 break
10:40 - 11:00 Learning Convex Bodies is Hard (short talk)
Navin Goyal
11:00 - 11:35 TBA
Gideon Schechtman
11:35 - 12:10 Online embedding of metrics
Ilan Newman
12:10 - 1:10 lunch
1:10 - 1:45 TBA
Prasad Raghavendra
1:45 - 2:20 Expanders via Random Spanning Trees
Luis Rademacher
2:20 - 2:55 Rounding Parallel Repetitions of Unique Games
Moritz Hardt
2:55 - 3:30 Hardness of Nearest Neighbor under L_infinity
Alexandr Andoni

Previous: Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on October 29, 2008.