MacTutor

Biografia

I genitori di Leslie Valiant erano Leslie Valiant e Eva Julia Ujlaki. È cresciuto in Inghilterra, frequentando la Tynemouth High School, North Shields. Questa scuola fu rinominata nel 1969, diversi anni dopo la partenza di Valiant, quando divenne nota come Norham High School. Valiant ha completato la sua formazione scolastica alla Latymer Upper School, a King Street, Hammersmith, Londra. Questa era (ed è ancora) una famosa scuola indipendente selettiva con una grande reputazione risalente alla sua fondazione da Edward Latymer nel 1624. Dopo essersi diplomato alla Latymer Upper School, ha studiato al King’s College di Cambridge poi, dopo aver conseguito la sua prima laurea, una laurea in matematica, è entrato all’Imperial College di Londra per studiare informatica teorica. Dopo il diploma dell’Imperial College in Informatica, Valiant si recò all’Università di Warwick dove intraprese la ricerca per un dottorato in informatica con Michael Stewart Paterson come suo consulente.
Prima dell’assegnazione del suo dottorato di ricerca., Valiant ha trascorso l’anno 1973-74 negli Stati Uniti come Visiting Assistant professor presso la Carnegie Mellon University di Pittsburgh, Pennsylvania. Ha conseguito il dottorato presso l’Università di Warwick nel 1974 per la sua tesi Decision Procedures for Families of Deterministic Pushdown Automata. In collaborazione con il suo consulente di tesi M S Paterson, Valiant aveva presentato il documento Deterministic one-counter automata alla Fte Fachtagung der Gesellschaft für Informatik über Automatentheorie und Formale Sprachen Ⓣ a Bonn nel 1973. Wilfried Brauer ha esaminato il documento, scrivendo:-

Un automa deterministico one-counter (doca) è un automa deterministico pushdown avente un alfabeto stack di un elemento. È facile vedere che i problemi di inclusione e nullità di intersezione per doca sono indecidibili. In contrasto con questo, gli autori danno una procedura di decisione per l’equivalenza dei doca e mostrano che la sua complessità temporale è limitata sopra da una funzione esponenziale in circa la radice quadrata del numero di stati dei doca testati. Congetturano che l’equivalenza è decidibile per la classe di tutti gli automi deterministici di pushdown.

Valiant pubblicò il documento The equivalence problem for deterministic finite-turn pushdown automata nel 1974. S A Greibach sottolinea l’importanza di questo documento:-

Un pushdown store automa (pda) è finito-turn se c’è un limite uniforme sul numero di volte in cui può passare da push (aumentando la lunghezza del pushdown store) a popping (diminuendo la lunghezza del pushdown store) durante qualsiasi calcolo su qualsiasi input. L’autore stabilisce la decidibilità del problema di equivalenza (due macchine accettano la stessa lingua?) per i pda a turno finito deterministici. Il significato del risultato risiede nelle tecniche di dimostrazione utilizzate per stabilirlo e nel fatto che rappresenta una delle principali scoperte verso la risoluzione della lunga congettura in sospeso che il problema di equivalenza per i pda deterministici (dpda) è decidibile (il problema corrispondente è noto per essere indecidibile per i pda non deterministici anche in casi molto limitati).

Dopo il ritorno dagli Stati Uniti nel 1974, Valiant ha preso una lectureship presso l’Università di Leeds, dove ha lavorato per il biennio 1974-76. Diamo un altro esempio dei suoi primi documenti, questo ancora una volta scritto in collaborazione con M S Paterson,. Questo articolo del 1975 Deterministic one-counter automata inizia con l’introduzione dei seguenti autori: –

Presentiamo un’analisi degli automi deterministici one-counter per mostrare che il problema di equivalenza per loro è decidibile. Tutti i nostri argomenti e risultati possono essere tradotti direttamente in termini teorici dello schema. Il corollario che segue è che l’equivalenza è decidibile per gli schemi di Janov anche quando a questi è consentito un contatore ausiliario.

Valiant si trasferì in Scozia nel 1975 per prendere una lectureship presso l’Università di Edimburgo. Nel 1977 ha sposato Gayle Lynne Dyckhoff; hanno avuto due figli Gregory John Valiant e Paul A Valiant. A Edimburgo è stato promosso a lettore nel 1981, ma è andato negli Stati Uniti nel 1982, quando era un visiting professor ad Harvard. Nello stesso anno è stato nominato Gordon McKay Professore di Informatica e Matematica applicata ad Harvard. È rimasto ad Harvard, anche se ha trascorso l’anno 1987-88 come visiting fellow presso l’Università di Oxford in Inghilterra. Nel 2001 è stato nominato T Jefferson Coolidge Professore di Informatica e Matematica applicata alla Harvard School of Engineering and Applied Sciences.
I contributi che Valiant ha fatto sono abbastanza notevoli e ha ricevuto le più alte onorificenze per i suoi successi. È stato Guggenheim Fellow nel 1985-86 e ha ricevuto il Premio Nevanlinna nel 1986. È stato eletto fellow della Royal Society di Londra nel 1991 e, l’anno successivo, fellow dell’American Association for Artificial Intelligence. Nel 1997 ha ricevuto il premio Knuth dall’Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory e dall’Institute of Electrical and Electronics Engineers Technical Committee on the Mathematical Foundations of Computing. È stato eletto all’Accademia Nazionale delle Scienze degli Stati Uniti nel 2001, ha ricevuto l’European Association for Theoretical Computer Science Award e l’Association for Computing Machinery 2010 A M Turing Award che sarà presentato a Valiant al banchetto annuale dei premi dell’Associazione a San Jose, in California, il 4 giugno 2011. Il premio include anche un premio in denaro di $250.000.
Non abbiamo spiegato i contributi di Valiant che lo hanno portato a ricevere i più alti riconoscimenti possibili. Per fare questo citiamo dal commento che accompagna l’annuncio del Premio Turing (gli articoli 2011 citati di seguito citano da quel commento). Il commento inizia: –

Negli ultimi 30 anni, Leslie Valiant ha dato contributi fondamentali a molti aspetti dell’informatica teorica. Il suo lavoro ha aperto nuove frontiere, introdotto nuovi concetti ingegnosi e presentato risultati di grande originalità, profondità e bellezza. Più e più volte, il lavoro di Valiant ha letteralmente definito o trasformato il panorama della ricerca informatica.

Si continua poi a dare dettagli di diverse aree a cui Valiant ha dato contributi sbalorditivi. Diamo alcuni brevi estratti da ciascuna delle quattro aree:

  1. Teoria dell’apprendimento computazionale. Il più grande contributo di Valiant può essere il suo articolo “A theory of the learnable” (1984), che ha posto le basi della teoria dell’apprendimento computazionale. … Il modello “probabilmente approssimativamente corretto” (PAC) di Valiant ha fornito bellissime basi per il concetto stesso di apprendimento.
  2. Complessità di enumerazione. Nei primi anni 1970, la complessità computazionale generalmente affrontava la difficoltà dei problemi decisionali, ad esempio se un grafico ha una corrispondenza perfetta o se un venditore ambulante può trovare un percorso di una certa lunghezza al massimo. … Una delle scoperte più degne di nota di Valiant è che i problemi di conteggio sono molto più sottili di quanto suggerito dall’esperienza precedente. Un problema di conteggio richiede il numero di alcuni oggetti combinatori: ad esempio, quanti abbinamenti perfetti ci sono in un grafico? Non stiamo solo chiedendo il problema della decisione se quel numero è positivo, ma anche quanto è grande. Se il problema della decisione è difficile, allora anche il problema del conteggio deve essere così, ma la sorprendente realizzazione di Valiant è che il contrario fallisce. Nel suo articolo “The complexity of computing the permanent” (1979), ha dimostrato che sebbene esista un algoritmo efficiente per dire se un grafico ha una corrispondenza perfetta, non esiste un algoritmo efficiente per contare gli abbinamenti perfetti (a meno che P = NP), e in effetti contare gli abbinamenti perfetti è difficile come qualsiasi problema di conteggio. Ciò è stato uno shock per la comunità della complessità computazionale, che si era abituata all’idea che i problemi decisionali avrebbero facilmente catturato le caratteristiche chiave di un problema.
  3. Calcolo algebrico. Un altro contributo chiave alla complessità computazionale è stata la teoria di Valiant del calcolo algebrico, in cui ha stabilito un quadro per capire quali formule algebriche possono essere valutate in modo efficiente. … Nel suo articolo “Classi completezza in algebra” (1979), Valiant caratterizzato la difficoltà di calcolo algebrico in termini di due funzioni fondamentali e strettamente correlati da algebra lineare, vale a dire il determinante e il permanente.
  4. Calcolo parallelo e distribuito. Oltre alla teoria dell’apprendimento computazionale e alla complessità computazionale, una terza ampia area in cui Valiant ha dato importanti contributi è la teoria del calcolo parallelo e distribuito. I suoi risultati qui vanno da intuizioni semplici, ma potenti ed eleganti, a riesaminare le fondamenta stesse. Un esempio di una semplice intuizione è il suo schema di routing parallelo, descritto nel documento “A scheme for fast parallel communication” (1982).

Concludiamo questa biografia citando per intero la conclusione della citazione del Premio Turing:-

Raramente si vede una combinazione così sorprendente di profondità e ampiezza come nel lavoro di Valiant. È veramente una figura eroica nell’informatica teorica e un modello per il suo coraggio e la sua creatività nell’affrontare alcuni dei problemi irrisolti più profondi della scienza.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.