Mathematiker, geb. 28.3.1949 Budapest.

Valiant schloß seine Studien am King’s College in Cambridge mit dem Grad des Bachelor ab, studierte 1970/71 am Imperial College in London, und promovierte 1973 an der Universität von Warwick in Coventry. Es folgten 1973/74 eine Gastprofessur an der Carnegie-Mellon-Universität in Pittsburgh sowie Lehrpositionen an den Universitäten in Leeds (1974–1976) und Edinburgh (1977–1982), jeweils auf dem Gebiet der Informatik (Computer Science). Seit 1982 hat Valiant die Gordon McKay-Professur für Informatik und Angewandte Mathematik an der Harvard Universität in Cambridge (Mass.) inne.

Valiant lieferte grundlegende Beiträge zu verschiedenen Bereichen der theoretischen Informatik. 1975 gelang ihm für die kontextfreien Sprachen ein überraschendes Resultat über die Algorithmen für das Erkennungsproblem. Er konnte zeigen, daß für das Erkennen von Sätzen der Länge n, die in kontextfreien Grammatiken formuliert sind, ein Algorithmus existiert, dessen Rechenzeit schwächer wächst als n³. Im gleichen Jahr erzielte er wichtige Einsichten über gerichtete Graphen. Die dabei vorgenommenen Größenabschätzungen für bestimmte Typen von Graphen führten zu den Nachweis, daß es für die schnelle Fourier-Transformation im gewissen Sinne keinen Optimalitätsbeweis gibt. Weitere bedeutende Ergebnisse betrafen die Klassen von Entscheidungsproblemen, die mit einem bestimmten Typ von Turing-Maschinen gelöst werden können. In der Komplexitätstheorie erweiterte er 1979 den Bereich der NP-Vollständigkeit, indem er eine Relation zwischen verschiedenen Abzählbarkeitsproblemen und einfachen Suchproblemen herstellte. Außerdem wandte sich Valiant der algebraischen Komplexitätstheorie zu, zeigte für eine wichtige Klasse von Quantenberechnungen in der Physik, daß sie in Polynom-Zeit auf klassischen Turing-Maschinen ausgeführt werden können, und behandelte Fragen der künstlichen Intelligenz. Er entwickelte effektive stochastisch bewertete Algorithmen und hat mit seinen Beweistechniken und neuen Konzepten wesentlich zu Fortschritten in der theoretischen Informatik beigetragen.

1986 wurde Valiant für seine Leistungen mit dem Nevanlinna-Preis ausgezeichnet.