Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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)

Letzte Aktualisierung: 20.06.2007