Completeness classes in algebraic complexity theory
arXiv:2406.06217
Abstract
The purpose of this overview is to explain the enormous impact of Les Valiant's eponymous short conference contribution from 1979 on the development of algebraic complexity.
49 pages, 4 figures. To appear in "Foundations of Computation and Machine Learning: The Work of Leslie Valiant'', Ed. Rocco Servedio, Turing Award series, ACM