Monday, July 2, 2007
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
Recent advances in designing approximation algorithms for NP-hard problems often use semidefinite programs. The analysis of such algorithms relies (necessarily, as I will point out) on new theorems about high-dimensional geometry. This talk is a survey of such developments. One of the main examples will be recent algorithms for sparsest cut and other graph partitioning-type problems, whose analysis requires a new understanding of the expansion of certain geometric graphs. This new understanding has led to a better understanding of embeddings of metric spaces, especially l_1 and l_2.
The talk will be a self-contained survey.
Colloquium - 16:00
How many different 3-spheres can be glued from N tetrahedra?
Is there a singly exponential upper bound? We give an improved upper bound on
the number of spheres that are "locally constructible". However, it is still
not clear whether all 3-spheres are "locally constructible". We show that
this class contains at least the family of all shellable (or constructible)