Leslie G. Valiant

For contributing in a decisive way to the growth of many branches of computer science: solving the recognition problem of context-free grammars in cubic time; proving that superconcentrators of linear size exist; discovering complete counting problems that correspond to easy search problems, thereby considerably enlarging the scope of the theory of NP-completeness.

For transformative contributions to the theory of computation, including the theory of probably approximately correct (PAC) learning, the complexity of enumeration and of algebraic computation, and the theory of parallel and distributed computing.