Erich Kaltofen

Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix

2016 · arXiv (Cornell University)

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 each output. In this paper, we give an algorithm that computes a …