GYSS 10th ANNIVERSARY WEB BANNER 1500 x 312px-02_R3

Leslie Valiant

Turing Award


How does the human brain carry out operations such as memorising information and making associations? Professor Leslie Valiant, who won the Turing Award in 2010 for his pioneering work in computer science, is aiming to unlock these and other mysteries of the brain. His findings could shape the future of artificial intelligence, just as his past work revolutionised computer science.

In 1984, believing that machines can “learn” like humans by drawing on experiences from the past, Prof Valiant developed the “probably approximately correct” (PAC) model of machine learning, which is an algorithm that takes past experiences to derive a generalisation that is effective in categorising examples not seen before. This is like a veteran wildlife photographer guessing the species of a bird unknown to him or her based on its plumage and other features.

More recently, he adapted the PAC model to provide a mathematical theory of the scope and limits of biological evolution, framing Darwinian evolution in nature as a form of PAC learning.

In artificial computation, he devised a scheme for the efficient routing of communications in very large parallel computing systems, and showed that the overheads involved even in a sparse network need not grow with the size of the system.

With these and other groundbreaking work, Prof Valiant built an “extraordinarily productive career in theoretical computer science, producing results of great beauty and originality”, said the committee that conferred him the Turing Award. It added: “His research opened new frontiers and has resulted in the transformation of many areas.”

Prof Valiant’s other awards include the 1986 Rolf Nevanlinna Prize, 1997 Donald E. Knuth Prize, and 2008 European Association for Theoretical Computer Science Award. He has also authored two books, titled “Circuits of the Mind” and “Probably Approximately Correct”.

He is continuing his research on the computational processes in neuroscience and biological evolution, and the computational building blocks that are necessary for cognition and artificial intelligence. Since 1982, he has been based at Harvard University, where he is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the School of Engineering and Applied Sciences. He also co-leads its Centre for Brain Science.