Deliverables

10:00 Welcome

10:15 Raimundas Vidunas (University of Athens)

Title: Counting Nash equilibria with MacMahon’s Master theorem.
Abstract: Estimation of the number of Nash equilibria in games of several players is still an open problem. The maximal number of totally mixed Nash equilibria (TMNE) was combinatorially characterized by McKelvey and McLennan, using the BKK bound of the algebraic system for them. MacMahon’s master theorem can be applied to the m-Bezout bound to derive the generating function for the maximal number of TMNE (when the number of players is fixed, and the number of their options varies). We will show the relation between the BKK and m-Bezout bounds explicitly, derive recurrence relations and some hypergeometric formulas for the maximal number of TMNE, and discuss computational complexity.

11:00 Anna Karasoulou (University of Athens)

Title: Discriminants (Intermediate PhD Thesis presentation)
Abstract: Discriminant is a key tool when examining well-constrained systems, including the case of one univariate polynomial. We present some useful properties and applications in order to motivate their study. We discuss a multiplicativity formula of the discriminant in the case of two polynomials with fixed supports when one of them factors. We are also interested in symmetric homogeneous polynomials and their discriminant. Taking advantage of the polynomial symmetries, we present a factorization formula for them.

13:00 LUNCH

15:00 Bernard Mourrain (INRIA, Sophia-Antipolis)

Title: Sparse reconstruction from moments
Abstract: Many problems of reconstruction of structured models from measurements can by reformulated in terms of reconstruction of sparse exponential polynomials, which naturally lead to truncated moment problems. Gaspard-Clair-François-Marie Riche de Prony proposed in 1795 a method to reconstruct the decomposition of functions in one variable, which reduces to the solution of a univariate polynomial. We describe a generalization of this approach to several variables, which involves algebraic ingredients such as duality, border basis and eigenvector solving. We illustrate the method in some applications to signal recovering, sparse interpolation, tensor decomposition and polynomial optimization. Numerical issues are discussed including Newton-type improvement of exponential polynomial representations.

16:00 Marta Abril Bucero (INRIA , Sophia Antipolis)

Title: Border basis relaxation for polynomial optimization
Abstract: A relaxation method based on border basis reduction which improves the efficiency of Lasserre’s approach is proposed to compute the optimum of a polynomial function on a basic closed semi algebraic set. A new stopping criteria is given to detect when the relaxation sequence reaches the minimum, using a sparse flat extension criteria. We also provide a new algorithm to reconstruct a finite sum of weighted Dirac measures from a truncated sequence of moments, which can be applied to other sparse reconstruction problems. As an application, we obtain a new algorithm to compute zero-dimensional minimizer ideals and the minimizer points or zero-dimensional G-radical ideals. Experimentations show the impact of this new method on significant benchmarks.

17:00 DISCUSSION / COFFEE

17:30 Laurent Busé (INRIA, Sophia Antipolis)

Title: Implicit Matrix Representations of Rational Bézier Curves and Surfaces
Abstract: We introduce and study a new implicit representation of rational Bézier curves and surfaces in the 3-dimensional space. This representation consists of a matrix whose entries depend on the space variables and whose rank drops exactly on this curve or surface. Then, we show that these implicit matrix-based representations adapt geometric problems, such as intersection problems, to the powerful tools of numerical linear algebra, as the Singular value decomposition, with a good numerical stability.

10:30 Elias Tsigaridas (INRIA, Paris-Rocquencourt)
Title: Real root isolation and refinement
Abstract: We present an overview of algorithmic, complexity and implementation results for isolating and refining up to arbitrary precision the real roots of a univariate polynomial the coefficients of which are integers, polynomial functions of real algebraic numbers, or logarithms of real algebraic numbers.

11:30 Vissarion Fisikopoulos (University of Athens)
Title: Practical polytope volume approximation in high dimensions

Abstract: We study the fundamental problem of computing the volume of a convex polytope given as an intersection of linear inequalities. We design, implement and experimentally evaluate practical randomized algorithms for accurately approximating the polytope’s volume in high dimensions (one or two hundred). Our code is significantly faster than exact computation and more accurate, as well as faster, than existing approximation methods.