Corrigimus, verificamus, vincimus: Ensuring algorithmic accuracy in an age of uncertainty

For nearly as long as it has been developing fast heuristic, approximate, and randomized algorithms, the computer algebra community has also been keen to produce methods by which we can verify accuracy and even correct a small number of errors. These routines are much more efficient than trivially recomputing the result, but are often themselves randomized and can be wrong with controllably small probability. Nonetheless, provable probabilistic correctness is useful when running code on unreliable or cloud-based hardware, or when the original computation relies on unproven heuristics. The latter case may be increasingly relevant in the coming years as the code produced by generative AI models continues to improve in quality and inevitably makes its way into production. We will examine a few recent methods for interactive verification and error correction for some basic problems in linear algebra, pointing out connections and differences to related work from the coding theory and applied cryptography communities.