• go to Maurice V. Wilkes's profile page
  • go to Butler W Lampson's profile page
  • go to Judea Pearl's profile page
  • go to Frances Allen's profile page
  • go to Edsger W. Dijkstra's profile page
  • go to Ronald L Rivest's profile page
  • go to Whitfield Diffie 's profile page
  • go to Leslie G Valiant's profile page
  • go to Robert E Kahn's profile page
  • go to John E Hopcroft's profile page
  • go to Shafi Goldwasser 's profile page
  • go to Edmund Clarke's profile page
  • go to Dana S Scott's profile page
  • go to Richard Karp's profile page
  • go to Manuel Blum's profile page
  • go to John Cocke 's profile page
  • go to Fernando Corbato's profile page
  • go to Martin Hellman 's profile page
  • go to Michael O. Rabin 's profile page
  • go to Richard E Stearns's profile page
  • go to Leonard M. Adleman's profile page
  • go to Leslie Lamport's profile page
  • go to Robert E Tarjan's profile page
  • go to Raj Reddy's profile page
A.M. TURING AWARD WINNERS BY...

Leslie Gabriel Valiant DL Author Profile link

United States – 2010
Short Annotated Bibliography
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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."