Monday, July 2, 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005
Lecture - 14:15
Abstract:
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
Abstract:
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)
3-spheres.