6-7 septembre 2018, Lyon
Par ordre alphabétique :
Pascal Koiran : Orbits of monomials and factorization into products of linear forms.
Abstract: the talk will be based on a joint paper with Nicolas Ressayre.
Arpita Korwar : Survey of polynomial factorization.
Abstract: Polynomial factorization is the problem of finding factors of polynomials which are given to us as special arithmetic circuits. One would not even expect arithmetic circuit classes to be closed under factorization. But many classes like VP, VNP, small-depth circuits, sparse polynomials, VBP (arithmetic branching programs), VF (formulas) have been shown to have efficient factoring algorithms. In this talk, we will look at the factorization algorithm given by Dvir, Shpilka and Yehudayoff in 2009 for special polynomials. The depth of the factor circuit is d+5, where d is the depth of the original circuit. They use a method similar to Newton iteration.
We will also look at a recent paper by Bhargava, Saraf and Volkovich which factorizes sparse polynomials. They use the Newton polygon to bound the sparsity of the factor polynomial.
Pierre Ohlmann: Characterization of non-associative circuits using automata, and applications.
Abstract: Arithmetic circuit are the algebraic analogue of boolean circuits. As a natural model for computing multivariate polynomials, they have been extensively studied. The most important open question in the field of algebraic complexity theory is that of separating the classes VP and VNP, the analogues of P and NP. More precisely, can one obtain super-polynomial lower bounds for circuits computing a given explicit polynomial ?
Despite decades of efforts, this question yet seems out of reach, the best general lower bound being only slightly super-linear. The most common approach is to prove lower bounds for restricted classes of circuits, such as monotone or constant-depth circuits. Another approach would be removing relations arising from the mathematical structure underlying the computations, making it harder for circuits to compute polynomials and thus conceivably easier to obtain lower bounds. In this line of thought, Nisan (1991) was able to obtain breakthrough results in the context of non-commutative computations, separating circuits and formulas and characterizing the minimal size of Algebraic Branching Programs (ABP).
Likewise, circuits for which the multiplication is assumed to be non-associative, meaning that (xy)x and x(yx) are different monomials, have been considered. General exponential lower bounds can be proved in this setting. We highlight a syntactical equivalence between non-associative circuits and acyclic Multiplicity Tree Automata (MTA), which leads to a general algebraic characterization of the size of the smallest non-associative circuit computing a given non-associative polynomial.
As a direct consequence of this characterization, we unify several recent circuit lower bounds in the non-commutative setting. Going deeper in the comprehension of this new algebraic tool, we are able to considerably extend a known lower bound to a class which is very close to general.
Timothée Pecatte: Reconstruction algorithms for sums of affine powers
Abstract: A sum of affine powers is an expression of the form
\[
f(x) = \sum_{i=1}^s \alpha_i (x - a_i)^{e_i}.
\]
Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and Sparsest Shift.
We propose algorithms that find the smallest decomposition of $f$ in the first model (sums of affine powers) for an input polynomial $f$ given in dense representation.
Our algorithms only work in situations where the smallest decomposition is unique, and we provide conditions that guarantee the uniqueness of the smallest decomposition.
We also consider the natural multivariate extension and propose polynomial time black-box algorithms that find the decomposition with the smallest value of $s$ for an input polynomial $f$.
Our multivariate algorithms work in situations where $s$ is small enough compared to the number of variables or to the exponents $e_i$.
This talk is based on two joint works with Pascal Koiran and Ignacio Garcia-Marco, accepted at ISSAC '17 & '18.
Mateusz Skomra : Une relation entre la programmation semi-définie non-archimédienne et les jeux stochastiques.
Résumé : La programmation semi-définie est un outil fondamental d'optimisation convexe et polynomiale. Elle revient à optimiser une fonction linéaire sur un spectraèdre (un ensemble défini par des inégalités matricielles linéaires). En particulier, la programmation semi-définie est une généralisation de la programmation linéaire.
Nous étudions l'analogue non-archimédien de la programmation semi-définie, en remplaçant le corps des nombres réels par le corps des séries de Puiseux. Nous définissons les spectraèdres tropicaux comme les images par la valuation non-archimédienne des spectraèdres sur le corps des séries de Puiseux. Nous montrons que les spectraèdres tropicaux génériques sont décrits par des systèmes d'inégalités polynomiales sur le semi-anneau tropical. Ces systèmes expriment des contraintes de positivité sur des mineurs tropicaux d'ordre au plus 2. Nous en déduisons une relation entre les spectraèdres tropicaux génériques et les jeux à paiement moyen stochastiques. Cela donne une méthode pour résoudre des problèmes de réalisabilité en programmation semi-définie non-archimédienne en utilisant les algorithmes combinatoires conçus pour les jeux stochastiques.
Sébastien Tavenas: Homogeneous non-commutative formulas.
Abstract: Let us start by considering two irritating open problems about the arithmetic complexity of the iterated matrix multiplication. First, unlike multilinear models, there is no known separation between non-commutative formulas and non-commutative arithmetic branching programs. By the completeness of IMM, this question comes down to whether or not there exists a polynomial size non-commutative formula for IMM. Second, for multilinear models, Dvir-Malod-Perifel-Yehudayoff showed that there exists a polynomial computed by a polynomial size multilinear ABP which can not be computed by a polynomial size multilinear formula. However, as the completeness of IMM uses non-multilinear reductions, DMPY’s proof does not seem to imply anything about the question whether IMM has a polynomial size multilinear formula.
At the intersection of these two questions, we could wonder if IMM can be computed by a polynomial size homogeneous non-commutative formula. That is why, we will see in this talk, some properties and reductions of homogeneous non-commutative formulas.