acm
The Association for Computing Machinery
Advancing Computing as a Science & Profession

 

Contact: Virginia Gold
212-626-0505
[email protected]

 Printable PDF

 

NEW YORK, March  9, 2011 – ACM, the Association for Computing Machinery, today named Leslie G. Valiant of Harvard University 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 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 Corporation 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.  His work has produced modeling that offers computationally inspired answers on fundamental questions like how the brain ‘computes,’ said ACM President Alain Chesnais. “His profound vision 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.”  

Shekhar Borkar, Director of the Microprocessor Technology Lab at Intel Corp., 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.”  

            “Google joins in recognizing Leslie Valiant for his profound impact on the computer science research landscape,” said Alfred Spector, Vice President of Research and Special Initiatives at Google Inc.  “His ingenious concepts and brilliant research have had incredible breadth, and he has both made and inspired innovations in the field of machine learning, an area of growing importance in many uses of computing.  We are pleased to be a sponsor of the ACM Turing Award, which motivates and recognizes the great advances in computing that together have had such a beneficial impact on the world." 

Computational Learning Theory
Valiant’s “Theory of the Learnable,” published in 1984 in Communications of the ACM, 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.  

Algebraic Computation Theory
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.”  This work led to the theory of algebraic computation, which established a framework for understanding which algebraic formulas can be evaluated efficiently.  Valiant 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.  

Development of Models for Parallel Computing
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.  

Recent Research Focus
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.  It focuses on the brain's ability to quickly access a massive store of accumulated information during reasoning processes despite the extreme constraints imposed by the brain's finite number of neurons, their limited speed of communication, and their restricted interconnectivity.  The book offers a new approach to brain science for students and researchers in computer science, neurobiology, neurosciences, artificial intelligence, and cognitive science.

 

 

Background
Valiant is the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University’s School of Engineering and Applied Sciences (SEAS).  Before joining Harvard in 1982, he taught at Carnegie Mellon University, Leeds University, and the University of Edinburgh.  He is a graduate of Kings College, University of Cambridge, with a BA in Mathematics, and Imperial College London, where he received a Diploma of the Imperial College (DIC) in Computer Science.  He earned a Ph.D. in Computer Science from the University of Warwick.  

 A recipient of the Nevanlinna Prize from the International Mathematical Union in 1986, Valiant was awarded the 1997 Knuth Prize from the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEE Technical Committee on the Mathematical Foundations of Computing.  In 2008, he received the European Association for Theoretical Computer Science Award.  He is a Fellow of the Royal Society (London), a Fellow of the American Association for Artificial Intelligence, and a member of the National Academy of Sciences (USA).           

 ACM will present the 2010 A.M. Turing Award at its annual Awards Banquet on June 4, in San Jose, CA. 

About the ACM A.M. Turing Award

The A.M. Turing Award was named for Alan M. Turing, the British mathematician who articulated the mathematical foundation and limits of computing, and who was a key contributor to the Allied cryptanalysis of the German Enigma cipher and the German “Tunny” encoding machine in World War II. Since its inception in 1966, the Turing Award has honored the computer scientists and engineers who created the systems and underlying theoretical foundations that have propelled the information technology industry.  Go to http://awards.acm.org/turing for information.

About ACM

ACM, the Association for Computing Machinery www.acm.org, is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence.  ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.    

More press coverage

• The Boston Globe
• SD Times
• Network World
• The New York Times
• CBS News
• The Wall Street Journal