Parallel Computing Pioneer -- Leslie G. Valiant

Parallel Computing Pioneer - Leslie G. Valiant

Gordon McKay Professor of Computer Science and Applied Mathematics, Harvard University

Leslie G. Valiant has conducted groundbreaking research in parallel computation from the time he first became involved in the field. He took an early interest in the central role that communication plays in parallel computation. He developed an efficient randomized routing methodology for general patterns of communication. This provided some positive evidence for the possibility of general purpose parallel computing. This work in turn led to his development, almost a decade later in 1989, of the bulk synchronous parallel (BSP) model, intended to take the role of a unifying "bridging" model for parallel computers and programs.

"When I started my research in the early 1970s, parallel computing was very confusing as a field," says Valiant. "It contrasted starkly with some other areas of computer science ‹ for instance, complexity theory had just developed into a coherent and powerful science. However, despite its frustrations, the field of parallelism did offer one attraction. It seemed that there was one central question around which everything revolved: 'What is the right model?' "

He has also contributed to several other areas of computer science. Some of his early work was in complexity theory. He introduced the class #P and showed how it could be used to classify many basic algebraic and combinatorial counting problems according to their computational difficulty. He has also a longstanding interest in the theoretical basis of artificial intelligence.

In 1983 he introduced the PAC or "probably approximately correct" model of learning, which was instrumental in giving rise to the field of computational learning theory. More recently, he proposed this as a foundation for a broader computational study of intelligence. His 1994 book, Circuits of the Mind, formulates such a study in a framework suggested by cortical neurons.

Valiant was educated at King's College, Cambridge; Imperial College, London; and Warwick University, where he received his Ph.D. in computer science in 1974. He has been the Gordon McKay Professor of Computer Science and Applied Mathematics at Harvard University's Division of Engineering and Applied Sciences since 1982. Before coming to Harvard, he taught at Carnegie-Mellon University, Leeds University, and the University of Edinburgh.

Valiant is an active member of the high-performance computing community. He is a regularly invited lecturer at conferences an symposia, distinguished lecture series, and other events. He serve or has served on numerous editorial boards and program committees including the SIAM Journal on Computing, Machine Learning Computational Complexity, Neural Computation, Neural Networks, the International Journal of Foundations of Computer Science, the Symposium on Theory of Computing (STOC), the Conference on Computational Learning Theory (COLT), EuroColt, the Symposium on Parallel Algorithms & Architectures (SPAA), and others.

In addition to writing his 1994 book, Valiant is the author or co-author of more than 80 articles and papers. He received the Nevanlinna Prize at the International Congress of Mathematicians in 1986 and the Knuth Award in 1997. He is a Fellow of the Royal Society and the American Association for Artificial Intelligence.