Leslie Valiant wins Turing Award

The Association for Computing Machinery (ACM) today (March 9) named Leslie G. Valiant the winner of the 2010 ACM A.M. Turing Award for his fundamental contributions to the development of computational learning theory and to the broader theory of computer science.

Valiant, the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at the Harvard School of Engineering and Applied Sciences (SEAS), brought together machine learning and computational complexity, leading to advances in artificial intelligence as well as computing practices such as natural language processing, handwriting recognition, and computer vision. He also launched several subfields of theoretical computer science, and developed models for parallel computing.

The Turing Award, widely considered the “Nobel Prize in Computing,” is named for the British mathematician Alan M. Turing. The award carries a $250,000 prize, with financial support provided by Intel Corp. and Google Inc.

“Leslie Valiant’s accomplishments over the last 30 years have provided the theoretical basis for progress in artificial intelligence and led to extraordinary achievements in machine learning,” said ACM President Alain Chesnais. “His work has produced modeling that offers computationally inspired answers on fundamental questions like how the brain ‘computes.’

“His profound insights in computer science, mathematics, and cognitive theory have been combined with other techniques to build modern forms of machine learning and communication, like IBM’s ‘Watson’ computing system, that have enabled computing systems to rival a human’s ability to answer questions,” Chesnais said.

Valiant’s “Theory of the Learnable,” published in 1984 in Communications of the Association for Computing Machinery, is considered one of the seminal contributions to machine learning. It put machine learning on a sound mathematical footing and laid the foundations for a new research area known as computational learning theory.

“Google joins in recognizing Leslie Valiant for his profound impact on the computer science research landscape,” said Alfred Spector ’76, vice president of Research and Special Initiatives at Google Inc. “His ingenious concepts and original research have significantly influenced the way computers learn, with applications in medicine, transportation, finance, telecommunications, image processing, game theory, and strategic planning, to name a few.”

One of Valiant’s key contributions to computational complexity was his work on enumeration problems. Its impact was to show the inherent difficulty in counting the number of solutions not just to computationally hard problems, but also to those whose decision complexity is relatively “easy.”

“Les Valiant is known by researchers the world over for his revolutionary contributions to theoretical computer science,” said Michael D. Smith, dean of Harvard’s Faculty of Arts and Sciences and the John H. Finley Jr. Professor of Engineering and Applied Sciences. “His work has reoriented this entire field in recent decades, single-handedly creating or transforming any number of key research areas. Les is clearly deserving of the Turing Award.”

“From the first inklings of artificial intelligence to the early days of the ARPANET to the personal computer revolution and social networking, Harvard students, faculty, and alumni have been a driving force behind innovations in computer science,” added Cherry A. Murray, dean of SEAS and John A. and Elizabeth S. Armstrong Professor of Engineering and Applied Sciences. “Les Valiant is yet another pioneer in this remarkable tradition.”

More recently, Valiant has contributed to computational neuroscience, offering a concrete mathematical model of the brain and relating its architecture to complex cognitive functions.  In his 1994 book “Circuits of the Mind,” he details a promising new computational approach to studying the intricate workings of the human brain.  The book focuses on the brain’s ability to quickly access a massive store of accumulated information during reasoning processes despite the extreme constraints imposed by its finite number of neurons, their limited speed of communication, and their restricted interconnectivity.  The book offered a new approach to brain science for students and researchers in computer science, neurobiology, neurosciences, artificial intelligence, and cognitive science.

“Les Valiant stands out for having essentially initiated multiple research areas within computer science,” says Michael Mitzenmacher, Gordon McKay Professor of Computer Science at Harvard. “Learning theory, the complexity of counting solutions, the bulk-synchronous parallel model of computation, and holographic algorithms are just some of his outstanding contributions.  He is a truly profound thinker who has never feared bringing the power of theoretical computer science to entirely new areas, and he and his work have taught and inspired a generation of scholars.”

Michael Rabin, Thomas J. Watson Sr. Professor of Computer Science at SEAS, won the Turing Award in 1976, and three SEAS-affiliated alumni have also been bestowed with the honor: E. Allen Emerson ’81; Richard M. Karp ’55, ’59; and Frederick P. Brooks Jr. ’56.

To read the full release.