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…