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, February 14, 2011
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041

Lecture - 14:15

Günter M. Ziegler - Berlin

On low-dimensional faces that high-dimensional polytopes must have
(joint work with Karim Adiprasito, MDS)

In 1990, Kalai proved theorems on low-dimensional faces that high-dimensional polytopes must have, via a remarkable application of Linear Programming to flag-vector combinatorics. I will explain his approach, as well as a new, quite different approach, which yields results that are stronger than Kalai's: Every convex polytope of dimension at least 3 contains a triangle or its dual contains a triangle, for example; every 4-dimensional polytope has a facet with a vertex of degree at most 4. In particular, we complete the solution of a problem by Perles & Shephard (1967) on regular polytopes that occur as the facets of polytopes one dimension higher. Our new approach is based on the theory of CAT(0) polyhedral spaces, as pioneered by Alexandrov (1951) and Gromov (1987): Polytope boundaries cannot carry a metric of non-negative curvature, since this is not compatible with the topology of a sphere.

Colloquium - 16:00

Oliver Friedmann - München

Exponential lower bounds for determined game policy iteration and linear program simplex methods

Policy iteration is one of the most important algorithmic schemes for solving problems in the domain of determined game theory such as parity games, stochastic games and Markov decision processes, and many more. It is parameterized by an improvement rule that determines how to proceed in the iteration from one policy to the next. It is a major open problem whether there is an improvement rule that results in a polynomial time algorithm for solving one of the considered (two-player) game classes.

Simplex algorithms for solving linear programs are closely related to policy iteration algorithms. Like policy iteration, the simplex algorithm is parameterized by a so-called pivoting rule that describes how to proceed from one basic feasible solution in the linear program to the next. Also, it is a major open problem whether there is a pivoting rule that results in a (strongly) polynomial time algorithm for solving linear programs.

We describe our recent construction for parity games that give rise to an exponential lower bounds for the Random Facet improvement rule, and how to extend the lower bound to more expressive game classes like stochastic games. We show that our construction for parity games can be translated to Markov decision processes, transferring our lower bound to their domain, and finally show how the lower bounds for the MDPs can be transferred to the linear programming domain, solving problems that have been open for several decades.

We briefly address lower bound constructions for other pivoting rules if we still have time.

Letzte Aktualisierung: 31.01.2011