#
Monday Lecture and Colloquium

**Monday, July 2, 2007 **

Freie Universität Berlin

Institut für Informatik

Takustr. 9

14195 Berlin

room 005

** Lecture - 14:15**

###
Sanjeev Arora - Princeton University

### Geometry, Semidefinite Programs, and Approximation Algorithms

*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**

###
Bruno Benedetti - TU Berlin

###
On the number of simplicial 3-spheres with N facets

*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.

Letzte Aktualisierung:
20.06.2007