Leslie Valiant: Trailblazer in Computational Learning Theory and Complexity Theory

Leslie Gabriel Valiant (born March 28, 1949) is a British-American computer scientist and computational theorist, currently serving as the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. He is renowned for his contributions to computational learning theory and complexity theory, particularly for introducing the PAC (Probably Approximately Correct) learning model, which has significantly influenced modern machine learning algorithms.

Early Life and Education

Valiant was born in Hungary and moved to the United Kingdom during his childhood. He studied mathematics at King's College, Cambridge, and earned a diploma in computer science from Imperial College London in 1973. In 1974, he completed his Ph.D. in computer science at the University of Warwick, under the supervision of Mike Paterson, with a thesis titled "Decision Procedures for Families of Deterministic Pushdown Automata" .

He received his early education in England, attending Tynemouth High School and later Latymer Upper School in London, a prestigious institution founded in 1624 (MacTutor History).

Career and Research

Valiant's academic career includes several notable positions: Assistant Professor at Carnegie Mellon University (1973-1974), Lecturer at the University of Leeds (1974-1976), Lecturer and Senior Lecturer at the University of Edinburgh (1976-1982), and Professor at Harvard University (since 1982). His research spans theoretical computer science, with key contributions such as the introduction of the concept of #P-completeness in 1979, which classifies the complexity of counting problems; the proposal of the PAC learning model in 1984; and the development of holographic algorithms and the Bulk Synchronous Parallel (BSP) model, which has influenced the design of parallel computing systems.

Awards and Honors

Valiant's accomplishments include:

• 1986 Nevanlinna Award
• 1997 Knuth Award
• 2008 EATCS Award
• 2010 Turing Award (for his transformative contributions to the theory of computing)

He is also a Fellow of the Royal Society (1991) and a Fellow of the National Academy of Sciences (2001).