Leslie G. Valiant has been appointed the ACM Turing Award Recipient 2010 for his work on computational learning theory and his contribution to the broader theory of computer science. Valiant teaches computer science and applied mathematics at Harvard's School of Engineering and Applied Sciences. His work over the last 30 years has been fundamental to creation of systems like IBM’s Watson and various other computers that are capable of learning.
One of Valiant’s main contributions is the PAC model (“probably approximately correct”) which enables classification of information such as deciding whether an e-mail message should be considered SPAM or not. For this purpose the learning algorithm takes experiences from the past to devise a probability-based hypothesis as a decision fundament. However, such generalizations from the past might not work properly in the future, for example due to over-generalization. The PAC model allows minimizing such generalization errors which is why it is considered “approximately correct”. The learning model had also significant influence on machine learning, artificial intelligence, and many areas of computing practice such as natural language processing, handwriting recognition, and computer vision.
According to the Commentary of the ACM Committee,
another key contribution to computational complexity was Valiant’s theory of algebraic computation, in which he established a framework for understanding which algebraic formulas can be evaluated efficiently.
In addition, Valiant provided significant contributions to complexity theory as well as to parallel and distributed computing.
In the last years, Valiant has also contributed to research on computational neuroscience where he developed a mathematical model of the brain and associated its architecture with complex cognitive functions. His findings are published in the book Circuits of the Mind.
As the committee pointed out in their conclusions,
Rarely does one see such a striking combination of depth and breadth as in Valiant’s work. He is truly a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science.