The Work of Leslie Valiant

Avi Wigderson
On Saturday, May 30, one day before the start of the regular STOC 2009 program, a workshop was held in celebration of Leslie Valiant's 60th birthday. Talks were given by Jin-Yi Cai, Stephen Cook, Vitaly Feldman, Mark Jerrum, Michael Kearns, Mike Paterson, Michael Rabin, Rocco Servedio, Paul Valiant, Vijay Vazirani, and Avi Wigderson. The workshop was organized by Michael Kearns, Rocco Servedio, and Salil Vadhan, with support from the STOC local arrangements team and program committee. To accompany the workshop, here we briefly survey Valiant's many fundamental contributions to the theory of computing.

1. INTRODUCTION
Les Valiant singlehandedly created, or completely transformed, several fundamental research areas of computer science. Here we list some of those areas, and some of Valiant's seminal contributions to each.
2. COMPUTATIONAL LEARNING THEORY
Valiant's \Theory of the Learnable" created the area of Computational Learning Theory. Mainstream research in Machine Learning today has embraced Valiant's viewpoint as a path to understand and design intelligent systems. Philosophically, Valiant's work presents a computational theory that mirrors or at least serves as a metaphor for one of the most basic human activities: learning. Pragmatically, this work suggests a framework for the development of algorithms that adapt their behavior in response to feedback from the environment. Needless to say, attempts to model the learning process were made before Valiant. His contribution was in providing a general framework, as well as very concrete computational models for studying questions relating to the learning process, namely the PAC Learning Model and its variants. This led to well-dened research directions and created a language that enabled this study to mature into a real scientic theory, with techniques, results and connections to the rest of computer science. The resulting theory turned out to have numerous applications in a very wide area of computer practice (e.g., in Computer Vision and Natural Language Processing) as well as inform other scientic disciplines (e.g., the study of proteins and the cognitive functions of the brain). It is impossible to give details here of Valiant's numerous concrete contributions to computational learning theory. We only mention a recent work of his that attempts to present a computational theory of evolution, which builds on his learning framework.
Read full text