MacTutor

biografi

Leslie Valiants föräldrar var Leslie Valiant och Eva Julia Ujlaki. Han växte upp i England, deltar Tynemouth High School, North Shields. Denna skola döptes om 1969, flera år efter att Valiant lämnade, när den blev känd som Norham High School. Valiant avslutade sin skolutbildning på Latymer Upper School, I King Street, Hammersmith, London. Detta var (och är fortfarande) en berömd selektiv oberoende skola med ett gott rykte som går tillbaka till grundandet av Edward Latymer 1624. Efter examen från Latymer Upper School studerade han vid King ’ s College, Cambridge sedan, efter tilldelningen av sin första examen, en BA i matematik, gick han in i Imperial College, London för att studera teoretisk datavetenskap. Efter tilldelningen av diplom från Imperial College i datavetenskap gick Valiant till University of Warwick där han genomförde forskning för doktorsexamen i datavetenskap med Michael Stewart Paterson som sin rådgivare.
innan tilldelningen av hans Ph. D., Valiant tillbringade året 1973-74 i USA som besökande biträdande professor vid Carnegie Mellon University i Pittsburgh, Pennsylvania. Han tilldelades sin doktorsexamen vid University of Warwick 1974 för sin avhandling beslutsförfaranden för familjer av deterministiska Pushdown automater. I samarbete med sin avhandlingsrådgivare M S Paterson hade Valiant presenterat den deterministiska en-räknarautomaten för Erste Fachtagung der Gesellschaft ftubylr Informatik automatentheorie und Formale Sprachen Kazaki i Bonn 1973. Wilfried Brauer granskade papperet och skrev:-

en deterministisk en-räknare automat (doca) är en deterministisk pushdown automat som har en en-element stack alfabet. Det är lätt att se att inkluderingen och korsningsproblemen för doca är obestridliga. I motsats till detta ger författarna ett beslutsförfarande för ekvivalensen av doca och visar att dess tidskomplexitet begränsas ovan av en funktion exponentiell i ungefär kvadratroten av antalet tillstånd hos de testade doca. de antar att ekvivalensen är avgörande för klassen av alla deterministiska pushdown-automater.

Valiant publicerade papperet ekvivalensproblemet för deterministisk ändlig svängning pushdown automata 1974. S a Greibach påpekar vikten av detta dokument:-

en pushdown store automat (pda) är ändlig-sväng om det finns en enhetlig bunden på hur många gånger det kan växla från att trycka (öka längden på pushdown store) till popping (minska pushdown store längd) under någon beräkning på någon ingång. Författaren fastställer bestämningen av ekvivalensproblemet (accepterar två maskiner samma språk?) för deterministiska ändliga handdatorer. Betydelsen av resultatet ligger i de bevistekniker som används för att fastställa det och i det faktum att det representerar ett av de stora genombrotten mot att lösa det långa utestående antagandet att ekvivalensproblemet för deterministiska pda: er (dpda: er) är avgörande (motsvarande problem är känt för att vara obeslutbart för icke-deterministiska pda: er även i mycket begränsade fall).

efter att ha återvänt från USA 1974 tog Valiant upp en föreläsning vid Leeds University där han arbetade under de två åren 1974-76. Låt oss ge ett annat exempel på hans tidiga papper, den här igen skriven i samarbete med M S Paterson,. Detta papper från 1975 deterministisk en-räknare automat börjar med följande författares introduktion:-

vi presenterar en analys av deterministisk en-räknare automat för att visa att ekvivalensproblemet för dem är avgörande. Alla våra argument och resultat kan översättas direkt till schemasteoretiska termer. Följden som sedan följer är att ekvivalens är avgörande för Janov-scheman även när dessa tillåts en hjälpräknare.

Valiant flyttade till Skottland 1975 för att ta upp en föreläsning vid University of Edinburgh. 1977 gifte han sig med Gayle Lynne Dyckhoff; de hade två söner Gregory John Valiant och Paul a Valiant. I Edinburgh befordrades han till läsare 1981 men åkte till USA 1982 när han var gästprofessor vid Harvard. Senare samma år utsågs han till Gordon McKay Professor i datavetenskap och tillämpad matematik vid Harvard. Han stannade kvar vid Harvard, även om han tillbringade året 1987-88 som gästkamrat vid University of Oxford i England. År 2001 utsågs han till T Jefferson Coolidge Professor i datavetenskap och tillämpad matematik vid Harvard School of Engineering and Applied Sciences.
de bidrag som Valiant har gjort är ganska anmärkningsvärda och han har fått högsta utmärkelser för sina prestationer. Han var Guggenheim Fellow 1985-86 och fick Nevanlinnapriset 1986. Han valdes till ledamot av Royal Society of London 1991 och året därpå till ledamot av American Association for Artificial Intelligence. Han tilldelades Knuth-priset från Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory och Institute of Electrical and Electronics Engineers Technical Committee on the Mathematical Foundations of Computing 1997. Han valdes till United States National Academy of Sciences 2001, fick European Association for Theoretical Computer Science Award och Association for Computing Machinery 2010 A M Turing Award som kommer att delas ut till Valiant vid föreningens årliga utmärkelsebankett i San Jose, Kalifornien den 4 juni 2011. Priset inkluderar också ett kontantpris på $250,000.
vi har inte förklarat de bidrag från Valiant som har lett till att han fått högsta möjliga utmärkelser. För att göra detta citerar vi från kommentaren som åtföljer tillkännagivandet av Turing Award (2011-artiklarna som hänvisas till nedan citat från den kommentaren). Kommentaren börjar: –

under de senaste 30 åren har Leslie Valiant gjort grundläggande bidrag till många aspekter av teoretisk datavetenskap. Hans arbete har öppnat nya gränser, introducerat geniala nya koncept och presenterat resultat av stor originalitet, djup och skönhet. Gång på gång har Valiants arbete bokstavligen definierat eller förvandlat datavetenskapsforskningslandskapet.

det fortsätter sedan att ge detaljer om flera områden som Valiant har gjort fantastiska bidrag till. Vi ger några korta utdrag från vart och ett av fyra områden:

  1. Beräkningsinlärningsteori. Valiants största enskilda bidrag kan vara hans uppsats ’ a theory of the learnable ’(1984), som lade grunden för beräkningsinlärningsteori. … Valiants” förmodligen ungefär korrekta ” (PAC) modell levererade vackra fundament för själva begreppet lärande.
  2. komplexitet av uppräkning. I början av 1970-talet behandlade beräkningskomplexitet i allmänhet svårigheten med beslutsproblem, till exempel om en graf har en perfekt matchning eller om en resande säljare kan hitta en rutt med högst en viss längd. … En av Valiants mest anmärkningsvärda upptäckter är att räkneproblem är mycket mer subtila än tidigare erfarenheter föreslog. Ett räkningsproblem ber om antalet kombinatoriska objekt: till exempel, hur många perfekta matchningar finns det i en graf? Vi frågar inte bara beslutsproblemet om det numret är positivt, utan också hur stort det är. Om beslutsproblemet är svårt, måste räkningsproblemet vara lika bra, men Valiants överraskande insikt var att det omvända misslyckas. I sitt papper ”komplexiteten i att beräkna det permanenta” (1979) visade han att även om det finns en effektiv algoritm för att berätta om en graf har en perfekt matchning, finns det ingen effektiv algoritm för att räkna perfekta matchningar (såvida inte P = NP), och faktiskt att räkna perfekta matchningar är lika svårt som alla räkningsproblem. Detta kom som en chock för beräkningskomplexitetssamhället, som hade vant sig vid tanken att beslutsproblem lätt skulle fånga de viktigaste funktionerna i ett problem.
  3. algebraisk beräkning. Ett annat viktigt bidrag till beräkningskomplexitet var Valiants teori om algebraisk beräkning, där han etablerade en ram för att förstå vilka algebraiska formler som kan utvärderas effektivt. … I sin uppsats ”Fullständighetsklasser i algebra” (1979) karakteriserade Valiant svårigheten med algebraisk beräkning i termer av två grundläggande och närbesläktade funktioner från linjär algebra, nämligen determinanten och den permanenta.
  4. parallell och distribuerad databehandling. Förutom beräkningsinlärningsteori och beräkningskomplexitet är ett tredje brett område där Valiant har gjort viktiga bidrag teorin om parallell och distribuerad databehandling. Hans resultat här sträcker sig från enkla, men kraftfulla och eleganta insikter till att ompröva själva grunden. Ett exempel på en enkel insikt är hans parallella routingschema, som beskrivs i papperet ”ett schema för snabb parallell kommunikation” (1982).

vi avslutar denna biografi genom att citera i sin helhet slutsatsen av Turing Award citation:-

sällan ser man en så slående kombination av djup och bredd som i Valiants arbete. Han är verkligen en heroisk figur i teoretisk datavetenskap och en förebild för sitt mod och kreativitet för att ta itu med några av de djupaste olösta problemen inom vetenskapen.

Lämna ett svar

Din e-postadress kommer inte publiceras.