A3 · Algebraic Algorithms and Applications

The project Algebraic Algorithms and Applications (A3) is an interdisciplinary and multidisciplinary project, with strong international synergy.It consists of four work packagesThe first (Algebraic Algorithms) focuses on fundamentalproblems of computational (real) algebraic geometry: effective zerobounds, that is estimations for the minimum distance of the roots of apolynomial system from zero, algorithms for solving polynomials andpolynomial systems, derivation of non-asymptotic bounds for basicalgorithms of real algebraic geometry and application of polynomialsystem solving techniques in optimization.We propose a novel approach thatexploits structure and symmetry, combinatorial properties of highdimensional polytopes and tools from mathematical physics.Despite the great potential of the modern tools from algebraicalgorithms, their use requires a combined effort to transfer thistechnology to specific problems. In the second package (Stochastic Games)we aim to derive optimal algorithms for computingthe values of stochastic games, using techniques from real algebraicgeometry, and to introduce a whole new arsenal of algebraic tools tocomputational game theory.The third work package (Non-linear Computational Geometry), wefocus on exact computations with implicitly defined plane andspace curves. These are challenging problems that commonly arise ingeometric modeling and computer aided design,but they also have applications in polynomial optimization.The final work package (Efficient Implementations) describes our plansfor complete, robust and efficient implementations of algebraicalgorithms.