EATCS Award 2008 - Leslie G. Valiant

Leslie Valiant is world-renowned for his revolutionary, extensive and widely recognized contributions to theoretical computer science over a life long scientific career. He made seminal contributions to computational learning theory, computational complexity, parallel and distributed computation, cognitive theory and holographic algorithms. Let us briefly highlight some of these contributions.

Valiant's "Theory of the Learnable" has literally created the area of computational learning theory, and his viewpoint was adopted by many in the artificial intelligence community as the path to understanding and designing intelligent systems. Valiant not only created this area, but also made continuous significant contributions to its development. He provided a general framework as well as concrete computational models for studying the learning process, such as the "probably approximately correct" (or PAC) model of machine learning. This, in turn, lead to well-defined research directions and to the development of a fundamental scientific theory. Furthermore, this theory turned out to have numerous applications in wide areas of computer science (such as computer vision and natural language recognition) as well as other scientific disciplines (such as the study of proteins and the cognitive functions of the brain).

Valiant also made numerous seminal contributions to the field of computational complexity. To explain the apparent intractability of enumeration problems, he introduced the class of counting problems #P, and gave a brilliant proof that the permanent is complete for this class. Beyond their fundamental importance, these innovations have served computational complexity in unforeseen ways, for example, in unveiling the power of interactive proofs, PCPs, program checking and more. Valiant has contributed greatly also to the study of Boolean circuit complexity, in particular with his introduction of an algebraic analog of Boolean complexity and the fundamental concept of superconcentrators. The latter were also the inspiration for developments in other fields, such as communication, sorting and searching networks and error correcting codes.

In the area of parallel and distributed computation, Valiant's ingenious randomized distributed routing algorithm (with its equally ingenious analysis) provides a way of avoiding congestion in sparse networks. As congestion is unavoidable using any deterministic algorithm, the importance of this randomized algorithm in parallel and distributed architectures cannot be overestimated. Valiant's novel ideas and the challenges he posed for parallel computing (such as parallelizing seemingly "inherently sequential" problems like maximal independent set and maximum matching), shaped the direction of the field, and addressing those challenges yielded the development of some of the most basic parallel algorithmic techniques currently available.

Valiant has also been fascinated with the human brain, and his work in computational neuroscience offered a concrete mathematical model of the brain and tried to explain how the brain's architecture can support complex cognitive functions like memory, complex pattern recognition and natural language recognition.

Recently, Valiant suggested a novel algorithmic technique, capable of solving counting problems and constraint satisfaction problems that appear to be intractable by previous methods, by providing a "holographic" (many-to-many) reduction to a problem in P, namely, counting the number of perfect matchings in planar graphs. His model may be viewed as a submodel

of the standard quantum Turing machine, which has a classical simulation in polynomial time. One may speculate that, again, this work will create a field of beauty and importance. Leslie Valiant's research career has spanned computer science, mathematics, artificial intelligence and cognitive theory, and is unique in terms of the number of important research areas which he, single-handedly, created or completely transformed. His influence on the European research community of theoretical computer science is evident to anyone observing the focus shifts within this community and its progress in the last two decades.