MacTutor

Biografie

Leslie Valiants Eltern waren Leslie Valiant und Eva Julia Ujlaki. Er wuchs in England auf und besuchte die Tynemouth High School in North Shields. Diese Schule wurde 1969 umbenannt, einige Jahre nachdem Valiant gegangen war, als sie als Norham High School bekannt wurde. Valiant absolvierte seine Schulausbildung an der Latymer Upper School in der King Street, Hammersmith, London. Dies war (und ist immer noch) eine berühmte selektive unabhängige Schule mit einem guten Ruf, der auf die Gründung durch Edward Latymer im Jahr 1624 zurückgeht. Nach seinem Abschluss an der Latymer Upper School, Er studierte am King’s College, Cambridge dann, nach der Verleihung seines ersten Abschlusses, ein BA in Mathematik, Er trat in das Imperial College ein, London, um theoretische Informatik zu studieren. Nach der Verleihung des Diploms des Imperial College in Computer Science ging Valiant an die University of Warwick, wo er mit Michael Stewart Paterson als Berater für eine Promotion in Informatik forschte.
Vor der Verleihung seines Ph.D. Valiant verbrachte das Jahr 1973-74 in den Vereinigten Staaten als Visiting Assistant Professor an der Carnegie Mellon University in Pittsburgh, Pennsylvania. Er promovierte 1974 an der University of Warwick für seine Arbeit Decision Procedures for Families of Deterministic Pushdown Automata. In Zusammenarbeit mit seinem Doktorvater MS Paterson hatte Valiant 1973 auf der Ersten Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen Ⓣ in Bonn die Arbeit Deterministic one-counter automata vorgestellt. Wilfried Brauer rezensierte das Papier und schrieb:-

Ein deterministischer Ein-Zähler-Automat (doca) ist ein deterministischer Pushdown-Automat mit einem Stapelalphabet aus einem Element. Es ist leicht zu erkennen, dass die Probleme mit der Einbeziehung und der Nichtigkeit von Überschneidungen für Docas unentscheidbar sind. Im Gegensatz dazu geben die Autoren ein Entscheidungsverfahren für die Äquivalenz von Doca’s an und zeigen, dass ihre zeitliche Komplexität oben durch eine Funktion begrenzt ist, die exponentiell in etwa der Quadratwurzel der Anzahl der Zustände der getesteten Doca’s liegt. Sie vermuten, dass die Äquivalenz für die Klasse aller deterministischen Pushdown-Automaten entscheidbar ist.

Valiant veröffentlichte 1974 das Papier The equivalence problem for deterministic finite-turn pushdown automata. S A Greibach weist auf die Bedeutung dieses Papiers hin: –

Ein Pushdown-Speicherautomat (pda) ist endlich – und wenn es eine einheitliche Grenze für die Anzahl der Male gibt, kann er während einer Berechnung für eine Eingabe von Push (Erhöhen der Länge des Pushdown-Speichers) zu Popping (Verringern der Pushdown-Speicherlänge) wechseln. Der Autor stellt die Entscheidbarkeit des Äquivalenzproblems fest (akzeptieren zwei Maschinen dieselbe Sprache?) für deterministische Finite-Turn-PDAs. Die Bedeutung des Ergebnisses liegt in den Beweistechniken, die bei seiner Etablierung verwendet werden, und in der Tatsache, dass es einen der wichtigsten Durchbrüche zur Beilegung der lange ausstehenden Vermutung darstellt, dass das Äquivalenzproblem für deterministische PDAs (dpdas) entscheidbar ist (das entsprechende Problem ist bekannt) unentscheidbar für nichtdeterministische PDAs sogar in sehr eingeschränkten Fällen).

Nach seiner Rückkehr aus den Vereinigten Staaten im Jahr 1974 nahm Valiant einen Lehrauftrag an der Leeds University, wo er für die zwei Jahre 1974-76. Lassen Sie uns ein weiteres Beispiel für seine frühen Arbeiten geben, dieser wiederum in Zusammenarbeit mit MS Paterson geschrieben,. Diese 1975 erschienene Arbeit Deterministic One-Counter automata beginnt mit der Einführung der folgenden Autoren: –

Wir präsentieren eine Analyse deterministischer Ein-Zähler-Automaten, um zu zeigen, dass das Äquivalenzproblem für sie entscheidbar ist. Alle unsere Argumente und Ergebnisse können direkt in schematheoretische Begriffe übersetzt werden. Daraus folgt, dass die Äquivalenz für Janov-Schemata auch dann entscheidbar ist, wenn diesen ein Hilfszähler erlaubt ist.

Valiant zog 1975 nach Schottland, um einen Lehrauftrag an der University of Edinburgh zu übernehmen. 1977 heiratete er Gayle Lynne Dyckhoff; Sie hatten zwei Söhne Gregory John Valiant und Paul A Valiant. In Edinburgh wurde er 1981 zum Reader befördert, ging aber 1982 als Gastprofessor in Harvard in die USA. Später in diesem Jahr wurde er Gordon McKay Professor für Informatik und Angewandte Mathematik an der Harvard. Er blieb in Harvard, obwohl er das Jahr 1987-88 als Visiting Fellow an der University of Oxford in England verbrachte. 2001 wurde er zum Jefferson Coolidge Professor für Informatik und Angewandte Mathematik an der Harvard School of Engineering and Applied Sciences ernannt.
Die Beiträge, die Valiant geleistet hat, sind bemerkenswert und er hat die höchsten Auszeichnungen für seine Leistungen erhalten. 1985-86 war er Guggenheim Fellow und erhielt 1986 den Nevanlinna Prize. 1991 wurde er Fellow der Royal Society of London und im Jahr darauf Fellow der American Association for Artificial Intelligence. 1997 wurde er mit dem Knuth-Preis der Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory und des Institute of Electrical and Electronics Engineers Technical Committee on the Mathematical Foundations of Computing ausgezeichnet. Er wurde 2001 in die National Academy of Sciences der Vereinigten Staaten gewählt, erhielt den European Association for Theoretical Computer Science Award und den A M Turing Award 2010 der Association for Computing Machinery, der Valiant am 4. Juni 2011 beim jährlichen Preisverleihungsbankett der Association in San Jose, Kalifornien, verliehen wird. Der Preis beinhaltet auch einen Geldpreis von 250.000 US-Dollar.
Wir haben die Beiträge von Valiant, die dazu geführt haben, dass er die höchstmöglichen Auszeichnungen erhalten hat, nicht erklärt. Dazu zitieren wir aus dem Kommentar, der der Bekanntgabe des Turing-Preises beiliegt (die unten zitierten Artikel von 2011 zitieren aus diesem Kommentar). Der Kommentar beginnt: –

In den letzten 30 Jahren hat Leslie Valiant grundlegende Beiträge zu vielen Aspekten der theoretischen Informatik geleistet. Seine Arbeit hat neue Grenzen eröffnet, geniale neue Konzepte eingeführt und Ergebnisse von großer Originalität, Tiefe und Schönheit präsentiert. Valiants Arbeit hat die Forschungslandschaft der Informatik immer wieder buchstäblich definiert oder verändert.

Es geht dann weiter, um Details zu mehreren Bereichen zu geben, zu denen Valiant erstaunliche Beiträge geleistet hat. Wir geben einige kurze Auszüge aus jedem der vier Bereiche:

  1. Computational Learning theory. Valiants größter Einzelbeitrag könnte sein Papier ‚A theory of the learnable‘ (1984) sein, das die Grundlagen der computergestützten Lerntheorie legte. … Valiants „wahrscheinlich ungefähr korrektes“ (PAC) Modell lieferte schöne Grundlagen für das Konzept des Lernens.
  2. Komplexität der Enumeration. In den frühen 1970er Jahren befasste sich die Rechenkomplexität im Allgemeinen mit der Schwierigkeit von Entscheidungsproblemen, z. B. ob ein Diagramm eine perfekte Übereinstimmung aufweist oder ob ein reisender Verkäufer eine Route von höchstens einer bestimmten Länge finden kann. … Eine der bemerkenswertesten Entdeckungen von Valiant ist, dass Zählprobleme viel subtiler sind, als frühere Erfahrungen nahelegen. Ein Zählproblem fragt nach der Anzahl einiger kombinatorischer Objekte: Wie viele perfekte Übereinstimmungen gibt es beispielsweise in einem Diagramm? Wir stellen nicht nur das Entscheidungsproblem, ob diese Zahl positiv ist, sondern auch, wie groß sie ist. Wenn das Entscheidungsproblem schwierig ist, dann muss das Zählproblem auch sein, aber Valiants überraschende Erkenntnis war, dass das Gegenteil fehlschlägt. In seiner Arbeit „The complexity of computing the graph“ (1979) zeigte er, dass es zwar einen effizienten Algorithmus gibt, um festzustellen, ob ein Graph eine perfekte Übereinstimmung aufweist, aber keinen effizienten Algorithmus, um perfekte Übereinstimmungen zu zählen (es sei denn, P = NP), und tatsächlich ist das Zählen perfekter Übereinstimmungen so schwierig wie jedes Zählproblem. Dies war ein Schock für die Computational Complexity Community, die sich an die Idee gewöhnt hatte, dass Entscheidungsprobleme die Hauptmerkmale eines Problems leicht erfassen würden.
  3. Algebraische Berechnung. Ein weiterer wichtiger Beitrag zur Rechenkomplexität war Valiants Theorie der algebraischen Berechnung, in der er einen Rahmen für das Verständnis schuf, welche algebraischen Formeln effizient ausgewertet werden können. … In seiner Arbeit „Completency classes in algebra“ (1979) charakterisierte Valiant die Schwierigkeit der algebraischen Berechnung in Bezug auf zwei grundlegende und eng verwandte Funktionen aus der linearen Algebra, nämlich die Determinante und die Permanente.
  4. Paralleles und verteiltes Rechnen. Neben der Theorie des computergestützten Lernens und der Computerkomplexität ist ein dritter breiter Bereich, in dem Valiant wichtige Beiträge geleistet hat, die Theorie des parallelen und verteilten Rechnens. Seine Ergebnisse reichen hier von einfachen, aber kraftvollen und eleganten Einsichten bis hin zur Überprüfung der Grundlagen. Ein Beispiel für eine einfache Einsicht ist sein paralleles Routing-Schema, das in der Arbeit „A scheme for fast parallel communication“ (1982) beschrieben ist.

Wir beenden diese Biographie, indem wir die Schlussfolgerung des Turing Award Citation vollständig zitieren: –

Selten sieht man eine so auffällige Kombination von Tiefe und Breite wie in Valiants Werk. Er ist wirklich eine Heldenfigur in der theoretischen Informatik und ein Vorbild für seinen Mut und seine Kreativität, einige der tiefsten ungelösten Probleme in der Wissenschaft anzugehen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.