From parity games to linear optimization and back

Speaker(s)

Henryk Michalewski

Affiliation

Uniwersytet Warszawski

Date

March 4, 2015, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Linear programs (LPs) can be solved efficiently, hence the
desire to reduce the parity games (PGs) to LPs. This seminar will be
devoted to a summary of attempted reductions published over the last 20 years.
A polynomial solution to PGs is still unknown. However, the recent progress made
by M. Akian, X. Allamigeon, P. Benchimol, M. Joswig, S.
Gaubert, S. Schewe  and others, summarized in P. Benchimol's PhD thesis defended
in December 2014

http://www.cmap.polytechnique.fr/~benchimol/thesis.pdf

shows that there is a potential in this approach and perhaps even more
interestingly, the questions regarding PGs naturally integrate into a
broader landscape of open problems regarding LPs. One such problem is
the strong polynomial
conjecture for LPs. Namely, if one can solve LPs in PTIME disregarding
the size of coefficients, then indeed this would lead to a PTIME
algorithm for PGs. This approach
means confronting a rather heavy-weight geometric conjecture regarding
polytopes in R^n (the polynomial Hirsch conjecture - the linear Hirsch
conjecture
was recently refuted by F. Santos, Annals of Math. vol. 176, 2012) and
probably can
be safely relegated to the algorithmic dreamland at least for the
next few years. One of the topics of this seminar will be a summary of
the research program proposed in the PhD thesis of P. Benchimol. This
program seems to be more realistic then solving the strong polynomial
conjecture for LPs. Namely, in a natural way one can identify the
class of LPs over the tropical reals with the mean-payoff games. This
line of research led to adaptations (tropicalizations) of the
classical simplex algorithm and some of its variants to the context of
the tropical reals. This is done via an observation that one can interpret
tropical linear programs as ordinary linear programs with coefficients
in the field
of infinite Puiseux series series and these linear programs in turn
can be solved using the simplex method, because
the Puiseaux series form a real closed field. However, the PTIME
algorithms such as the
Khachiyan's ellipsoid method, the randomized simplex algorithm of
Kolner and Spielman or Karmarkar's interior point algorithm relay on
mathematical methods which are not yet completely understood in the
context of the tropical geometry.
Tropicalizations of these "better" algorithms is an open problem which
may be a tempting target of research requiring skills in probability,
geometry and combinatorics.

---