Sparse polynomial interpolation in practice

Sparse polynomial interpolation consists in recovering of a sparse representation of a polynomial P given by a blackbox program which computes values of P at as many points as necessary. In practice P is typically represented by DAGs (Directed Acyclic Graphs) or SPLs (Straight Line Programs). For polynomials with at most t terms over a field K, this task typically involves O(t) evaluations of P, operations on integers fo