GYSS 2020 Web Banner (low res)

Leslie Valiant

Turing Award


Ask a wildlife photographer to identify a common bird species and you’ll probably get the answer in seconds. But what if he or she has never seen that bird before? Chances are, a veteran photographer would still come up with an educated guess, based on the bird’s plumage, size and other features.

British computer scientist Professor Leslie Valiant theorised that machines can also “learn” by drawing upon experiences from the past. In 1984, he developed the “probably approximately correct” (PAC) model of machine learning, a learning algorithm that takes experiences from the past to derive a generalisation that is effective in correctly categorising examples not seen before. In recent years, Prof Valiant has also 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, Prof Valiant 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.

Born in 1949 in Budapest, Hungary, Prof Valiant received a bachelor’s degree in mathematics from the University of Cambridge in 1970 and a diploma in computer science from Imperial College, London, in 1973. He received a doctorate in computer science from the University of Warwick in 1974. Since 1982, he has been based at Harvard University, where he is now the T Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the Harvard School of Engineering and Applied Sciences.

Prof Valiant is a fellow of the Royal Society (London) and a member of the National Academy of Sciences (USA). Other honours include the Nevanlinna Prize in 1986, the Knuth Prize in 1997, and the European Association for Theoretical Computer Science Award in 2008. He received the Association for Computing Machinery's 2010 A. M. Turing Award, the highest honour in computer science.

His newer research focuses on the many computational processes in neuroscience and biological evolution. He is also interested in the computational building blocks that are necessary for cognition, or artificial intelligence. Prof Valiant has authored two books: Circuits of the Mind and Probably Approximately Correct. In the latter, he challenges how we think about behaviour, cognition, biological evolution, and the possibilities and limits of human and machine intelligence.