Monday, December 7, 2009
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136, 10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Finding a sparse/low rank solution in linear/semidefinite programming has many important applications, e.g. combinatorial optimization, compressed sensing, geometric embedding, sensor network localization. In this talk we will consider one of the most basic problems involving semidefinite programs with rank constraints: the positive semidefinite Grothendieck problem with rank-n-constraint. It contains the MAX CUT problem as a special case when n = 1. We will perform a complete complexity analysis of the problem by designing an approximation algorithm and by proving that the algorithm is optimal if one assumes the unique games conjecture.
joint work with Jop Briët and Fernando de Oliveira Filho (http://arxiv.org/abs/0910.5765).
Colloquium - 16:00
Abstract:
A recent wonderful breakthrough in the ``Colored Tverberg problem''
(Pavle V. M. Blagojevic, Günter M. Ziegler, Optimal bounds for
the colored Tverberg problem, arXiv:0910.4987v1 [math.CO])
placed chessboard complexes $\Delta_{m,n}$ in the focus again.
Closely related ``cycle-free chessboard complexes'' $\Omega_{m,n}$
have recently emerged in completely different problem on the
borderline of combinatorics and topology (Shaun Ault, Zbigniew
Fiedorowicz, arXiv:0708.1575v4 [math.AT]). We review properties of
these complexes focusing on their homology, connectivity, and
(still open) problems about their shellability (vertex
decomposability). The lecture is based on the joint paper with
Sini\v sa Vrecica (European J.~Math.\ 2009, arXiv:0710.5252v3
[math.AT]).