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
Abstract:
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
Abstract:
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.