Exploiting Structure in Polynomial Equation and System Solving for geOmetric and game mOdeling.
Excellence Programme, EU and Ministry of Development. October 2012 — September 2015.
ESPRESSO members:
I. Emiris
(PI)
Y. Avrithis
(Postdoc)
R. Vidunas
(Postdoc)
A. Karasoulou
(PhD student)
ESPRESSO collaborators:
E. Koutsoupias (U. Athens, U. Oxford)
B. Mourrain (INRIA)
P. Bro Miltersen (U. Aarhus)
D. Hristopoulos (Technical U. Crete)
The complexity of polynomial equation and system solving is often too high, hence the need for algorithms that exploit the structure of the problem, leading to complexity bounds in terms of its intrinsic rather than nominal hardness. Structure is multifarious: We consider the sparseness of the input, and reducing the problem to methods that operate on sparse objects.
ESPRESSO focuses on two specific applications. The first is geometric modeling, where we have extensive experience and expect to obtain tangible and practical results, based on effective, publicly available implementations. Our second application uses algebraic tools to better model stochastic games with the goal of effectively computing finite or infinite game equilibria.
