A.M. TURING AWARD WINNERS BY...

United States – 2010

Short Annotated Bibliography

- Valiant, Leslie G., “Three Problems in Computer Science,”
*Journal of the ACM*, Vol. 50, Num. 1, January 2003, pp. 96-99.*In this work Valiant discusses three major computer science problems that have formed the basis for much of his work.* - Valiant, L., "The complexity of computing the permanent,"
*Theoretical Computer Science*, Vol. 8, Num. 2, 1979, pp. 189-201.*This is the paper that contains the results that showed counting problems are much more subtle than previous experience had suggested.* - Valiant, Leslie G., “A bridging model for parallel computation,”
*Communications of the ACM*, Vol. 33, Num. 8, August 1990, pp. 103-111. Available here.*The ordinary sequential execution of most programs is based on the usual von Neumann model of a sequential computer. This model allows a programmer to specify the process in a high level language which can be efficiently implemented on standard hardware. In this paper Valiant proposes an analogous bulk-synchronous parallel (BSP) model for parallel computation. The model is not the only such arrangement possible but it does provide a promising candidate and Valiant presents evidence of how such a model can be efficiently implemented.* - Valiant, L., “A theory of the learnable,”
*Communications of the ACM*, Vol. 27, Num. 11, pp. 1134-1142, 1984.*In this paper Valiant presents his “probably approximately correct” (PAC) model of learning. In it he presents a methodology of studying learning from a computational point of view.* *Valiant, L.,**Circuits of the Mind*, Oxford University Press, 1994.*As Valiant notes in his preface to this work:**"The main task for the present, therefore, may be viewed as a prescientific one. What is the most promising way to proceed in order to find the intellectual structure within which at least some central questions can be formulated and reduced to problem solving? This volume suggests one avenue. It places at the center of the investigation some simple tasks of memory and learning, and advocates that these tasks be investigated by means of detailed computational models."*