Dr. Leslie Valiant

SHARE
Portrait of Dr. Leslie Valiant

October 11th, 12pm EST

Dr. Leslie Valiant, honored with the 2010 Turing Award, is a visionary computer scientist whose work has redefined the landscape of computational learning theory and artificial intelligence. His pioneering development of the 'probably approximately correct' (PAC) learning model has become a cornerstone in machine learning theory and practice. Dr. Valiant's groundbreaking contributions continue to drive innovation in AI algorithms and applications, influencing countless advancements in the field.

Turing Award Recipient

Biography

Leslie Gabriel Valiant

Early Life and Education

Leslie Gabriel Valiant was born on March 28, 1949, in Budapest, the Hungarian Republic. He was born to a chemical engineer father and a translator mother. Valiant's educational journey began at King's College, University of Cambridge, where he obtained his Bachelor of Arts (BA) degree. He then pursued a Master of Science (MS) degree at Imperial College London. Valiant completed his academic qualifications with a Ph.D. in computer science from the University of Warwick in 1974. His doctoral thesis was titled "Decision Procedures for Families of Deterministic Pushdown Automata" under the supervision of Mike Paterson source.

Academic and Professional Career

Valiant's illustrious career in theoretical computer science has seen him contribute significantly to multiple fields, including mathematics, theoretical computer science, computational learning theory, and theoretical neuroscience. He began his teaching career at Carnegie Mellon University, followed by positions at the University of Leeds and the University of Edinburgh. In 1982, he joined Harvard University, where he is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics source.

Key Contributions

Complexity Theory

Valiant introduced the notion of #P-completeness (Sharp-P completeness), significantly impacting the understanding of computational intractability in enumeration and reliability problems. His work in this area is seminal and has laid the foundation for further research in complexity theory source.

Probably Approximately Correct (PAC) Learning

One of Valiant's most influential contributions is the Probably Approximately Correct (PAC) learning model. This model formed the theoretical basis for the field of computational learning theory and has been a cornerstone for the development of machine learning source.

Holographic Algorithms

Valiant also pioneered the concept of holographic algorithms, which was inspired by quantum computation models. This innovative approach has furthered the understanding and development of algorithms in computer science.

Bulk Synchronous Parallel (BSP) Model

In computer systems, Valiant is renowned for introducing the Bulk Synchronous Parallel (BSP) processing model. This model has been instrumental in shaping parallel and distributed computing architectures. It has influenced large-scale computation frameworks like Google's MapReduce and Facebook's graph analytics systems.

Automata Theory

Valiant's work in automata theory includes an algorithm for context-free parsing, which remains the asymptotically fastest known algorithm in this area.

Computational Neuroscience

In recent years, Valiant has focused on computational neuroscience, particularly in understanding memory and learning processes. His 2013 book, "Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World," delves into the intersection of evolutionary biology and computational learning.

Awards and Honors

Valiant's groundbreaking work has earned him numerous prestigious awards and honors:

  • Nevanlinna Prize (1986): Awarded for outstanding contributions to mathematical aspects of information science.
  • Knuth Prize (1997): Recognizes outstanding contributions to the foundations of computer science.
  • EATCS Award (2008): Honoring extensive and widely recognized contributions to theoretical computer science.
  • Turing Award (2010): Often regarded as the "Nobel Prize of Computing," this award recognized Valiant for his transformative contributions to the theory of computation. The citation highlighted his work on PAC learning, complexity of enumeration, algebraic computation, and parallel and distributed computing source.

He was elected a Fellow of the Royal Society (FRS) in 1991 source, a Fellow of the Association for the Advancement of Artificial Intelligence (AAAI) in 1992, and a member of the United States National Academy of Sciences in 2001.

Personal Life

Valiant has two sons, Gregory Valiant and Paul Valiant, both of whom are also theoretical computer scientists.

Career Timeline

Career Timeline

  • 1974: Received Ph.D. in Computer Science from the University of Warwick source
  • 1982: Joined Harvard University as a professor source
  • 1985: Introduced the PAC learning model
  • 1986: Awarded the Nevanlinna Prize
  • 1991: Elected Fellow of the Royal Society (FRS) source
  • 1992: Elected Fellow of the Association for the Advancement of Artificial Intelligence (AAAI)
  • 1997: Awarded the Knuth Prize
  • 2001: Elected member of the United States National Academy of Sciences
  • 2008: Received the EATCS Award
  • 2010: Awarded the ACM Turing Award source
  • 2013: Published "Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World"