معرفی
Leslie Valiant is the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics in the School of Engineering and Applied Sciences at Harvard University, where he has taught since 1982. He previously held positions at Carnegie Mellon University, Leeds University, and the University of Edinburgh.
His research spans theoretical computer science with significant contributions to complexity theory, computational learning, and parallel computation. He introduced the #P-completeness concept to explain why enumeration and reliability problems are intractable, developed holographic algorithms, and created the influential "probably approximately correct" (PAC) model that helped establish machine learning theory as a formal discipline. His work extends to computational neuroscience, evolution theory, and artificial intelligence, where he has formulated evolution as a form of computational learning.
- Nevanlinna Prize (1986)
- Knuth Award (1997)
- EATCS Award (2008)
- A.M. Turing Award (2010)
- Fellow of the Royal Society
- Member of the National Academy of Sciences (USA)
Valiant's interdisciplinary approach connects computer science with biological evolution, proposing that protein circuits in living organisms evolve through processes analogous to machine learning algorithms. His work on evolvability distinguishes function classes that can evolve with polynomially bounded resources from those that cannot, addressing fundamental questions about how complex biological systems can emerge through natural selection.
