https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Leslie_ValiantLeslie Valiant - Versionsgeschichte2026-06-06T04:47:02ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Leslie_Valiant&diff=1809021&oldid=previmported>John Red: Ergänzungen2025-07-27T13:09:49Z<p>Ergänzungen</p>
<p><b>Neue Seite</b></p><div>[[Datei:Leslie Valiant.jpg|miniatur|Leslie Valiant 2005 am [[Mathematisches Forschungsinstitut Oberwolfach|Mathematischen Forschungsinstitut Oberwolfach]]]]<br />
<br />
'''Leslie Gabriel Valiant''' (* [[28. März]] [[1949]] in [[Budapest]], [[Ungarn]]) ist ein britischer [[Informatik]]er und [[Turingpreis]]träger.<br />
<br />
== Studium und Forschung ==<br />
Valiant studierte an der [[University of Cambridge]] ([[King’s College (Cambridge)|King’s College]]), am [[Imperial College London]] und an der [[University of Warwick]], wo er 1974 in Informatik bei [[Michael Paterson]] promovierte (''Decision Procedures for Families of Deterministic Pushdown Automata'').<ref>{{MathGenealogyProject|id=18757|name=Leslie Gabriel Valiant|Kommentar=abgerufen am 27. Juli 2025.}}</ref> Danach war er an der [[Carnegie Mellon University]], der [[University of Leeds]] und der [[University of Edinburgh]]. Ab 1982 lehrte er an der [[Harvard University]], wo er zurzeit T. Jefferson Coolidge Professor für Informatik und Angewandte Mathematik ist.<br />
<br />
Valiant beschäftigte sich besonders mit [[Komplexitätstheorie]] (Einführung von [[Sharp-P]] 1979<ref>Valiant: The Complexity of Computing the Permanent, Theoretical Computer Science, Band 8, 1979, S. 189–201</ref>), [[Computational learning theory]] (Einführung des PAC-Modells des Maschinenlernens: [[Probably Approximately Correct Learning]]), parallelem Rechnen, neuronalem Rechnen, Evolutions-Modellen und [[Künstliche Intelligenz|Künstlicher Intelligenz]]. Von ihm stammt das Konzept holographischer Algorithmen (auch ''accidental algorithms'' genannt).<ref>Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13</ref><ref>Valiant, Holographic algorithms, Electronic Colloquium on Computational Complexity, Report No. 99.l, 2005</ref><ref>Valiant, Accidental algorithms, Proceedings of the 47th IEEE Symposium on<br />
Foundations of Computer Science, FOCS ’06, 2006, S. 509–517.</ref><br />
<br />
Bei seiner Einführung von #P zeigte er, dass die Berechnung der [[Permanente]] #P-vollständig ist.<br />
<br />
1985 bewies er mit [[Vijay Vazirani]] ein wichtiges Resultat der Komplexitätstheorie (Valiant-Vazirani-Theorem), dass wenn UNIQUE-[[Erfüllbarkeitsproblem der Aussagenlogik|SAT]] in [[P (Komplexitätsklasse)|P]] ist, die [[Komplexitätsklasse]]n [[NP (Komplexitätsklasse)|NP]] und [[RP (Komplexitätsklasse)|RP]] (random polynomial) identisch sind.<ref>Valiant, Vazirani ''NP is as easy as detecting unique solutions'', Proceedings of the seventeenth annual ACM symposium on Theory of computing, 1985, S.&nbsp;458–463.</ref><br />
<br />
Zu seinen Doktoranden zählt [[Mark Jerrum]].<br />
<br />
== Auszeichnungen ==<br />
1986 erhielt er den [[Nevanlinna-Preis]], 1997 den [[Knuth-Preis]] für Informatik, 2008 den [[EATCS-Award]] und 2010 den [[Turing Award]]. 2024 wurde er mit dem Basic Science Lifetime Award for Theoretical Computer Sciences ausgezeichnet.<ref>[https://www.icbs.cn/site/pages/index/index?pageId=930f0000-54af-a6e2-31c3-08dc45561427 Basic Science Lifetime Award 2024]</ref><br />
<br />
Er ist Fellow der [[Royal Society]], Mitglied der [[National Academy of Sciences]] und seit 2019 Auswärtiges Mitglied der [[Academia Europaea]],<ref>[https://www.ae-info.org/ae/Member/Valiant_Leslie Eintrag] auf der Internetseite der Academia Europaea</ref> seit 2022 Mitglied der [[American Academy of Arts and Sciences]]. 1983 war er Invited Speaker auf dem [[Internationaler Mathematikerkongress|Internationalen Mathematikerkongress]] in [[Warschau]] (''An algebraic approach to computational complexity'').<br />
<br />
== Schriften ==<br />
* ''Circuits of the mind''. Oxford University Press, 1994, 2000<br />
<br />
== Weblinks ==<br />
{{commonscat}}<br />
* {{MacTutor|id=Valiant|title=Leslie Gabriel Valiant}}<br />
* [http://people.seas.harvard.edu/~valiant/ Homepage in Harvard] (englisch)<br />
* {{TIBAV-Suche |suche= |link= | gnd=155042718 }}<br />
* [https://zbmath.org/authors/valiant.leslie-g Leslie Gabriel Valiant] in der Datenbank [[zbMATH]]<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
{{Navigationsleiste Träger des Turing-Awards}}<br />
<br />
{{Normdaten|TYP=p|GND=1036657280|LCCN=n/91/63548|VIAF=56713854|NDL=00662635}}<br />
<br />
{{SORTIERUNG:Valiant, Leslie}}<br />
[[Kategorie:Informatiker]]<br />
[[Kategorie:Hochschullehrer (Harvard University)]]<br />
[[Kategorie:Mitglied der National Academy of Sciences]]<br />
[[Kategorie:Mitglied der Royal Society]]<br />
[[Kategorie:Mitglied der Academia Europaea]]<br />
[[Kategorie:Mitglied der American Academy of Arts and Sciences]]<br />
[[Kategorie:Träger des Turing Award]]<br />
[[Kategorie:Brite]]<br />
[[Kategorie:Geboren 1949]]<br />
[[Kategorie:Mann]]<br />
<br />
{{Personendaten<br />
|NAME=Valiant, Leslie<br />
|ALTERNATIVNAMEN=Valiant, Leslie G.; Valiant, Leslie Gabriel (vollständiger Name)<br />
|KURZBESCHREIBUNG=britischer Informatiker<br />
|GEBURTSDATUM=28. März 1949<br />
|GEBURTSORT=[[Budapest]], [[Ungarn]]<br />
|STERBEDATUM=<br />
|STERBEORT=<br />
}}</div>imported>John Red