Leslie Gabriel Valiant

Presentation address by Professor Tony Cohn


Leslie Valiant is one of the world’s most distinguished theoretical computer scientists, known for an extraordinary variety of important results, encompassing both natural and artificial phenomena.

He took a post as a lecturer at the University of Leeds in 1974, where he stayed for two years;  he is now at Harvard, where he has held an endowed chair since 1982. 

Leslie invented the notion of a model learnt by an algorithm as being ‘Probably Approximately Correct’ (PAC for short), which allows a quantitative characterisation of the circumstances in which learning can be said to have taken place successfully.  This notion gave rise to a whole new field of study now known as computational learning theory with profound theoretical and practical consequences.

His 1994 book, Circuits of the Mind, broadened this notion of ‘PAC learnability’ to investigate how the brain accesses and computes information, which not only set out fundamental constraints on neural computation, but also provided important questions for experimentalists to answer.

He also discovered a new class for algorithmic complexity;  previously the so called NP complexity class had been the cornerstone for the analysis of hard computational problems, but his new class, named #P, captured a harder class, which characterised certain kinds of counting problems.  An active international research community continues to pursue the problems opened up by this work, as they apply to a wide range of practical problems.

As a final example of his very broad range of fundamental contributions, I will mention his work on analysing communication between parallel computations, such as might be found in today’s cloud computers;  his Bulk Synchronous Parallel model has had a profound influence on the community. 

It is no surprise, then, that Leslie has been awarded every major prize in the field, including the 1986 Nevanlinna Prize for outstanding contributions in Mathematical Aspects of Information Sciences;  the 1996 Knuth Prize;  and the European Association for Theoretical Computer Science Distinguished Achievement Award in 2008.

Leslie is a Fellow of the Royal Society and a member of the US National Academy of Sciences.  He was the 2010 ACM Turing award recipient, which is widely acknowledged as the most prestigious award in Computer Science. 

Vice-Chancellor, in recognition of this very distinguished career, I am delighted and honoured to present to you for the degree of Doctor of Science (Engineering), honoris causa, Leslie Gabriel Valiant.