Leslie Valiant

Leslie Valiant 2005 am Mathematischen Forschungsinstitut Oberwolfach

Leslie Gabriel Valiant (* 28. März 1949 in Budapest, Ungarn) ist ein britischer Informatiker und Turingpreisträger.

Studium und Forschung

Valiant studierte an der University of 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>Leslie Gabriel Valiant im Mathematics Genealogy Project (englisch){{#if: abgerufen am 27. Juli 2025.| abgerufen am 27. Juli 2025. }} {{#if: 18757 | {{#ifeq: {{#property:P549}} | 18757 | | {{#if: {{#property:P549}} | {{#if: | | }} | {{#if: | | }} }} }} }}</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.

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ü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 Foundations of Computer Science, FOCS ’06, 2006, S. 509–517.</ref>

Bei seiner Einführung von #P zeigte er, dass die Berechnung der Permanente #P-vollständig ist.

1985 bewies er mit Vijay Vazirani ein wichtiges Resultat der Komplexitätstheorie (Valiant-Vazirani-Theorem), dass wenn UNIQUE-SAT in P ist, die Komplexitätsklassen NP und 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. 458–463.</ref>

Zu seinen Doktoranden zählt Mark Jerrum.

Auszeichnungen

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>Basic Science Lifetime Award 2024</ref>

Er ist Fellow der Royal Society, Mitglied der National Academy of Sciences und seit 2019 Auswärtiges Mitglied der Academia Europaea,<ref>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 Internationalen Mathematikerkongress in Warschau (An algebraic approach to computational complexity).

Schriften

Circuits of the mind. Oxford University Press, 1994, 2000

Weblinks

[{{canonicalurl:Commons:Category:{{#if:|{{{1}}}|Leslie Valiant}}|uselang=de}} Commons: {{#if:|{{{2}}}|{{#if:|{{{1}}}|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if:

   | {{#ifeq: {{#invoke:Str|left||9}} 
       | category:

| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

{{#if: |{{{author}}}: |John J. O’Connor, Edmund F. Robertson: }}[https://mathshistory.st-andrews.ac.uk/{{#switch:

| bio = Biographies | cur = Curves | ex = Extras | ht = HistTopics | misc = Miscellaneous | soc = Societies | #default = Biographies }}/Valiant/ Leslie Gabriel Valiant.] In: {{#invoke:Vorlage:lang|flat}}{{#if: |, {{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}}} (englisch).

Homepage in Harvard (englisch)
Vorlage:TIBAV-Suche
Leslie Gabriel Valiant in der Datenbank zbMATH

Einzelnachweise

Vorlage:Navigationsleiste Träger des Turing-Awards

{{#ifeq: p | p | | {{#if: 1036657280n/91/635480066263556713854 | |

}} }}Vorlage:Hinweisbaustein{{#ifeq: p | p | | {{#if: 1036657280n/91/635480066263556713854 | |

}} }}{{#ifeq:||{{#if: | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|{{{GNDCheck}}}|7}}]] }}{{#if: | {{#if: | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: p | p | {{#if: 1036657280 | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: p | p | {{#if: 1036657280 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: p | p | {{#if: n/91/63548 | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: p | p | {{#if: n/91/63548 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: p | p | {{#if: 56713854 | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: p | p | {{#if: 56713854 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung

{{#if: Valiant, Leslie | {{#if: Valiant, Leslie G.; Valiant, Leslie Gabriel (vollständiger Name) | {{#if: britischer Informatiker | {{#if: 28. März 1949 | {{#if: Budapest, Ungarn | {{#if: | {{#if: |

Personendaten
NAME	Valiant, Leslie }}
ALTERNATIVNAMEN	Valiant, Leslie G.; Valiant, Leslie Gabriel (vollständiger Name) }}
KURZBESCHREIBUNG	britischer Informatiker }}
GEBURTSDATUM	28. März 1949 }}
GEBURTSORT	Budapest, Ungarn }}
STERBEDATUM	}}
STERBEORT	}}

Vorlage:Wikidata-Registrierung