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