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

Workshop 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