12 citations · 34 across the 9 of their papers we have counts for
7 papers · 1 filter
Sparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding
Erich L. Kaltofen, Zhi-Hong Yang
We present sparse interpolation algorithms for recovering a polynomial with terms from evaluations at distinct values for the variable when of the evaluations c…
Elimination-based certificates for triangular equivalence and rank profiles
Jean-Guillaume Dumas, Erich Kaltofen, David Lucas +1
In this paper, we give novel certificates for triangular equivalence and rank profiles. These certificates enable somebody to verify the row or column rank profiles or the whole ra…
Computing Approximate Greatest Common Right Divisors of Differential Polynomials
Mark Giesbrecht, Joseph Haraldson, Erich Kaltofen
Differential (Ore) type polynomials with "approximate" polynomial coefficients are introduced. These provide an effective notion of approximate differential operators, with a stron…
Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix
Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé +1
Computational problem certificates are additional data structures for each output, which can be used by a-possibly randomized-verification algorithm that proves the correctness of…
Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices
Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé
Certificates to a linear algebra computation are additional data structures for each output, which can be used by a-possibly randomized- verification algorithm that proves the corr…
Sparse Polynomial Interpolation Codes and their decoding beyond half the minimal distance
Erich L. Kaltofen, Clément Pernet
We present algorithms performing sparse univariate polynomial interpolation with errors in the evaluations of the polynomial. Based on the initial work by Comer, Kaltofen and Perne…
Essentially optimal interactive certificates in linear algebra
Jean-Guillaume Dumas, Erich Kaltofen
Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the c…