Leslie Valiant

Leslie Gabriel Valiant (born 1949) is a British-American computer scientist and theorist of computation who has taught at Harvard University since 1982, where he holds the T. Jefferson Coolidge chair in computer science and applied mathematics. He took his doctorate at the University of Warwick in 1974 and earlier taught at Carnegie Mellon, Leeds and Edinburgh. His best known contributions are the notion of sharp-P completeness, which explains why counting and enumeration problems such as the matrix permanent are intractable, the probably approximately correct model of learning that founded computational learning theory, and the bulk synchronous parallel model of parallel computing. His honours include the Nevanlinna Prize in 1986, the Knuth Prize in 1997 and the Turing Award in 2010, and he is a Fellow of the Royal Society and a member of the United States National Academy of Sciences.