On the uniqueness of the Simultaneous Rational Function Reconstruction

English

Séminaire AMAC: CASC

4/06/2020 - 14:00 Ilaria Zappatore (LIRMM, Université de Montpellier)

The Vector Rational Function Reconstruction is the problem of reconstructing a vector of rational functions given some evaluations, or more generally given their remainders modulo different polynomials. This is the vector generalization of the classic Rational Function Reconstruction. In this talk I will focus on the special case of rational functions sharing the same denominator, a.k.a. Simultaneous Rational Function Reconstruction (SRFR). This problem has many applications from polynomial linear system solving to coding theory, provided that SRFR has a unique solution. The number of unknowns of SRFR is smaller than for a general vector of rational functions. This allows one to reduce the number of evaluation points needed to guarantee the existence of a solution, possibly losing its uniqueness. Nevertheless, we will see that uniqueness is guaranteed for a generic instance.