“Nobel Prize” in Computing Presented to Leslie Valiant

Computer scientist and expert in computational learning theory Leslie Valiant, winner of the 2010 Turing Award, believes that the "science of learning remains only partially explored and certainly unexploited." Courtesy of Eliza Grinnell, Harvard School of Engineering and Applied Sciences |

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.

“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.

Shekhar Borkar, Director of the Microprocessor Technology Lab at Intel, and an Intel Fellow said, "Professor Valiant’s research in the theory of computation has revolutionized machine learning and artificial intelligence, making machines almost think.” He added, "His approach invites comparison with Turing himself — a novel formulation starting from a deep fundamental insight, and Intel is pleased to support this award."

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. He provided a general framework, as well as concrete computational models, and his approach of “Probably Approximately Correct” (PAC) learning has become a standard model for studying the learning process. His work has led to the development of algorithms that adapt their behavior in response to feedback from the environment. Mainstream research in AI has embraced his viewpoint as a critical tool for designing intelligent systems.

“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. “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. We are pleased to be a sponsor of the ACM Turing Award, which offers opportunities that advance computing and enable innovation worldwide.”

One of Valiant’s key contributions to computational complexity was his work on the complexity of 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; as a colleague and friend, I am delighted by this recognition his myriad contributions to our field."

Valiant's work led to the theory of algebraic computation, which established a framework for understanding which algebraic formulas can be evaluated efficiently. He also introduced the class #P and proved the permanent to be complete for this class. His paper “Completeness Classes in Algebra,” published in 1979, brought algebraic techniques into the toolbox of theoretical computer science, and his work on #P set the stage for the development of interactive proofs for problems beyond NP.

Valiant’s insight into the theory of parallel and distributed computing offers another broad area of important contributions. His 1982 paper “A Scheme for Fast Parallel Communication” described a simple parallel routing scheme that offered a solution to congestion problems, which occur when multiple computers try to communicate over networks with limited capacity. He also introduced the “bulk synchronous parallel” (BSP) computing model, which describes different types of multiprocessor computers based on how efficiently they synchronize and communicate internally. The BSP model explains why the performance of an algorithm may vary between different parallel computers.

"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 the Harvard School of Engineering and Applied Sciences and John A. and Elizabeth S. Armstrong Professor of Engineering and Applied Sciences. "Les Valiant is yet another pioneer in this remarkable tradition. On behalf of everyone in the School of Engineering and Applied Sciences, I wish to extend Les our congratulations on this fantastic achievement."

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,” said 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.”