| Citation | Valiant has contributed in a decisive way to the growth of almost every branch of theoretical computer science. His work is concerned mainly with quantifying mathematically the resource costs of solving problems on a computer. In early work (1975) he found the asymptotically fastest algorithm known for recognising context-free languages. At the same time, he pioneered the use of communication properties of graphs for analysing computations. In 1977 he defined the notion of #P-completeness ("sharp-P") and established its utility in classifying counting or enumeration problems according to computational tractability. The first application was to counting matchings (the matrix permanent function). In 1984 Valiant introduced a definition of inductive learning that for the first time reconciles computational feasibility with the applicability to non-trivial classes of logical rules to be learned.* More recently he has devised a scheme for efficient routing of communications in a multiprocessor system. He showed that the overheads involved even in a sparse network need not grow with the size of the system. This establishes, from a theoretical viewpoint, the possibility of efficient general purpose parallel computers.*
* Both these results were reported to Discussion Meetings of the Royal Society. |