Foundations of Computing and Machine Learning

This volume is a celebration of Leslie Valiant's scientific and intellectual achievements. It contains eight of Valiant's most impactful research works, along with accompanying contributions providing modern perspectives on these landmark papers in the context of contemporary research in complexity theory, parallel computing, computational learning theory, and machine learning. It also contains a biography of Leslie Valiant, an interview with him, and his Turing Award lecture. In 2010, Valiant received the ACM's Turing Award for "transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing." His research contributions have also been recognized with the International Mathematical Union's Nevanlinna Prize in 1986, the Knuth Prize in 1997, and many other awards. Leslie Valiant has made deep contributions to an unusually broad range of areas within theoretical computer science. Perhaps his most celebrated contribution has been his paper "A Theory of the Learnable," which gave birth to the field of computational learning theory and provided much of the intellectual foundation for the highly successful development of modern machine learning. His pioneering research in computational complexity inaugurated the study of the complexity of counting problems, defining the fundamental "counting complexity" class #P and showing that a wide range of natural counting problems are complete for this class. Valiant defined algebraic analogues of the complexity classes P and NP and established the first completeness results for these classes; this groundbreaking work opened new vistas for the field of algebraic complexity theory that continue to be explored to this day. Valiant also made seminal contributions to the field of parallel computing through his development of the highly impactful Bulk Synchronous Parallel (BSP) model as a "bridging" model between parallel software and parallel hardware, and he gave an unexpected randomized message-routing algorithm for parallel computers, which has been highly influential.