Sign In

Communications of the ACM


Beauty and Elegance

ACM's 2010 A.M. Turing Award recipient Leslie Valiant

David Gelernter, a computer scientist at Yale University, calls beauty in computing "the happy marriage of simplicity and power." It would be difficult to find a greater master of those principles than Leslie Valiant, the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University, and the recipient of the 2010 ACM A.M. Turing Award.

The Turing Award citation notes Valiant's "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." (An interview with Valiant, "A Lifelong Learner," appears on p. 128; to view his award citation see

"He looks at what many people would see as very complex problems, and he breaks them down into something beautiful and elegant, really getting at the heart of the problem," says Jennifer Chayes, managing director of Microsoft Research New England. "He thinks with such amazing clarity. Part of it is his solution, but a lot of it is his definition and articulation of these problems."

Chayes and others point in particular to Valiant's pioneering 1984 paper, "Theory of the Learnable," which established the mathematical framework for machine learning with the simple yet profound concept of PAC learning.

"In the 1980s, the field of machine learning was in its infancy and largely empirical and ad hoc," says Michael Kearns, a professor of computer and information science at the University of Pennsylvania. "With a series of models and results that combined technical depth with broad applicability, Les' work created a common language and way of thinking about different machine learning problems, an achievement that is hard to overestimate."

"The most critical choice for a scientist is what problems to work on."

"The scientific question I isolated," says Valiant, "was whether one could specify what it means for a mechanistic process to learn effectively. If we claim that a machine can do this, what exactly is it reasonable to ask of it? My definition of 'probably approximately correct' learning is such a specification. It is quantitative, and hence gives a way of comparing different learning algorithms with respect to how much computation they do, how many experiences they need, and how well they generalize. In that way it has encouraged the development of useful learning algorithms."

In distributed computing, Valiant developed the Bulk Synchronous Parallel model. It is based on "supersteps" consisting of computation, communication, and synchronization, the various parameters of which can define the varieties of parallel computers and specify their throughput. "He articulated the questions of what does it mean to do parallel computation, and what is the interaction between hardware and software," says Chayes. In so doing, Valiant created an analytic framework for the design of parallel systems.

With conventional computers, we have the von Neumann model, says Valiant, but for parallel processors there is no comparable unifying view. "Different machines have very different characteristics as far as how many processors they have and how efficiently the internal inter-processor communication is realized," he says. "This is a very big problem since it means that programs that run efficiently on one machine may be close to useless on another. I have tried to delineate the issues involved here and have worked toward finding an appropriate 'bridging model' that might give the sought-after single view and account for the variety of machines that one will inevitably find."

Kearns observed Valiant up close as a Ph.D. candidate under him at Harvard in the late 1980s. "One strongly feels that his taste in problems is inherently personal," Kearns says. "He picks very big and fundamental questions and pursues them quietly and rigorously until he has something important to say, and only then will you find him writing a usually landmark paper. In this sense he is immune to fashion, more so than any researcher I have ever encountered."

About his knack of extracting the simple from the complex, Valiant says, "A basic question about science is whether everything important is really simple when looked at from the right perspective. I would generally answer yes. Of course the path to discovering the right perspective may be tortuous and highly technical. The simplicity and elegance of the solution is apparent only after it has been discovered.

"The most critical choice for a scientist is what problems to work on," says Valiant, when asked about advice for future Turing Award winners. "The successful ones find problems of significance on which progress is possible using their particular skills."

Back to Top


Gary Anthes is a technology writer and editor based in Arlington, VA.

Back to Top



©2011 ACM  0001-0782/11/0600  $10.00

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.


Justin Kellner

Congrats to Mr. Valiant. It's pretty rare that a person's name actually describes them, and is positive (as opposed to the unflattering connotation of the recently embattled Congressman from NY! Cheers.

Displaying 1 comment