Efficient computation of squarefree separator polynomials and applications to algebraic statistics

Il giorno 6 giugno 2019 alle ore 14 in aula 2107 la Dott.sa Michela Ceria terra' un seminario.
La Dott.sa Ceria e' assegnista di ricerca presso il Dipartimento di Informatica dell'Università di Milano (laboratorio di Crittografia) Si e' laureata a laureata a Torino con il prof. Valabrega e ha lavorato principalmente nel campo dell'Algebra Computazionale (basi di Groebner).

 

==============
Efficient computation of squarefree separator polynomials and applications to algebraic statistics.

Given a finite set of points X, we call separator family a set of polynomials, each one corresponding to a point of X, such that each of them takes value one at the corresponding point, whereas it vanishes at any other point of X. Separator polynomials are fundamental building blocks for polynomial interpolation and they can be employed in many practical applications, such that, for example, algebraic statistics or reverse engineering.
A new algorithm by Ceria and Mora computes squarefree  separator polynomials.
The algorithm, to avoid redundancy,  employs as a tool the point trie structure, first defined by Felszeghy-Ráth-Rónyai in their Lex game algorithm, which gives a compact representation of the relation among the points' coordinates.

In this talk, we first discuss Ceria-Mora algorithm, proposing a fast implementation in C, based on an efficient storing and visiting of the point trie.

Then, we give an overview on the current progresses on this project.
Basing on Ceria-Mora iterative lex game, we can improve the separators' construction by giving their
normal forms without passing through Groebner bases (whose computation is rather inefficient).

This is exactly the outcome needed for applications in the field of study of algebraic statistics.
We will see that a simple arithmetic model is all one needs to specialize our algorithm to produce the indicator functions (as described by Pistone-Rogantin) which represents a fraction of factorial designs

 

 

Argomento