We present a new algorithm for reducing a multivariate polynomial with respect to an autoreduced tuple of other polynomials. In a suitable sparse complexity model, it is shown that the execution time is essentially the same (up to a logarithmic factor) as the time needed to verify that the result is correct.

Occasion: ACA 2015, Kalamata, July 23, 2015

Documents: slideshow, TeXmacs source