Leslie Valiant

Infotaula de personaLeslie Valiant

Leslie Valiant el 2005 (foto de l'MFO) Modifica el valor a Wikidata
Biografia
NaixementLeslie Gabriel Valiant
28 març 1949 Modifica el valor a Wikidata (75 anys)
Budapest (Hongria) Modifica el valor a Wikidata
Dades personals
NacionalitatBritànica
Formació
  • University of Cambridge
  • Imperial College London
  • Universitat de Warwick
Tesi acadèmicaDecision Procedures for Families of Deterministic Pushdown Automata (1974)
Director de tesiMike Paterson[2]
Es coneix perTeorema de Valiant–Vazirani[1]
Activitat
Camp de treballCiències de la computació Modifica el valor a Wikidata
OcupacióMatemàtiques
Informàtica
Organització
  • Harvard University
  • University of Edinburgh
Membre de
Obra
Estudiant doctoral
  • Mark Jerrum
  • Michael Kearns
  • Dan Roth
  • Rocco Servedio[2]
Premis
  • Premi ACM Turing Award (2010)
  • Premi EATCS (2008)
  • Premi Knuth (1997)
  • Premi Nevanlinna (1986)
  • FRS (1991)
Lloc webpeople.deas.harvard.edu… Modifica el valor a Wikidata

Leslie Gabriel Valiant, nascut el 28 de març de 1949, és un informàtic teòric britànic.

Educació

Valiant Va ser educat en el King's College, Cambridge, Imperial College de Londres i la Universitat de Warwick, on va rebre un Ph.D. en ciències de la computació el 1974.[2] Educat al King's College, Cambridge, Imperial College London i la Universitat de Warwick on va rebre el seu Ph.D. en ciències de computació el 1974.

Carrera

Va començar dictant classes a la Universitat Harvard el 1982 i actualment és un T. Jefferson Coolidge Professor de Ciències de Computació i Matemàtiques Aplicades al Harvard School of Engineering and Applied Sciences. Abans de 1982 va ensenyar a més en la Universitat Carnegie Mellon, a la Universitat de Leeds, i a la Universitat d'Edimburg. El 2010 Valiant rep el Premi Turing.

Investigació

Valiant és reconegut mundialment pel seu treball en ciències de la computació. Entre les seves principals contribucions a la complexitat computacional, es troba la seva introducció de la notació de Numeral-P-complet per explicar per què els problemes d'enumeració són intractables. També va introduir el model d'aprenentatge automàtic PAC, que va contribuir al desenvolupament d'aquesta teoria, i el concepte d'algoritmes hologràfics. Leslie Valiant també treballa en neurociència computacional, especialment en la comprensió de la memòria i l'aprenentatge.

Premis i honors

Va rebre el Premi Nevanlinna el 1986, el Premi Knuth el 1997, i el premi atorgat per la EATCS el 2008.[3] És membre de la Royal Society de Londres, de l'American Association for Artificial Intelligence, i de l'Acadèmia Nacional de Ciències dels Estats Units.

Un dels seus articles més significatius, escrit juntament amb Vijay Vazirani, demostra que si UNIQUE-SAT ∈ P, aleshores es compleix que NP = RP.

Valiant va rebre el Premi Turing de l'ACM, el 2010"[4][5] per les seves transformadores contribucions a la teoria de la computació, inclosa la teoria de l'aprenentatge probable, aproximadament correcta, la complexitat de l'enumeració i de la computació algebraica, i teories de la computació paral·lela i distribuïda."

Referències

  1. ↑ Valiant, Leslie; Vazirani, V.V.. NP is as easy as detecting unique solutions. DOI 10.1016/0304-3975(86)90135-0. 
  2. ↑ 2,0 2,1 2,2 Leslie Valiant al Mathematics Genealogy Project.
  3. ↑ David Peleg The EATCS Award 2008 - Laudatio for Professor Leslie Valiant European Association of Theoretical Computer Science.
  4. ↑ Josh Fishman "‘Probably Approximately Correct’ Inventor, From Harvard U., Wins Turing Award" Chronicle of Higher Education March 9, 2011.
  5. ↑ ACM Turing Award Goes to Innovator in Machine Learning ACM Computing News

Enllaços externs

  • DBLP:Leslie G. Valiant.
  • Pàgina oficial (Inclou fotografies).
  • Premi EATCS 2008 Arxivat 2008-07-04 a Wayback Machine..
  • Premi Turing 2010
  • Vegeu aquesta plantilla
Guardonats amb el Premi Turing

Perlis (1966) • Wilkes (1967) • Hamming (1968) • Minsky (1969) • Wilkinson (1970) • McCarthy (1971) • Dijkstra (1972) • Bachman (1973) • Knuth (1974) • Newell / Simon (1975) • Rabin / Scott (1976) • Backus (1977) • Floyd (1978) • Iverson (1979) • Hoare (1980) • Codd (1981) • Cook (1982) • Thompson / Ritchie (1983) • Wirth (1984) • Karp (1985) • Hopcroft / Tarjan (1986) • Cocke (1987) • Sutherland (1988) • Kahan (1989) • Corbató (1990) • Milner (1991) • Lampson (1992) • Hartmanis / Stearns (1993) • Feigenbaum / Reddy (1994) • Blum (1995) • Pnueli (1996) • Engelbart (1997) • Gray (1998) • Brooks (1999) • Yao (2000) • Dahl / Nygaard (2001) • Rivest / Shamir / Adleman (2002) • Kay (2003) • Cerf / Kahn (2004) • Naur (2005) • Allen (2006) • Clarke / Emerson / Sifakis (2007) • Liskov (2008) • Thacker (2009) • Valiant (2010) • Pearl (2011) • Micali / Goldwasser (2012) • Lamport (2013) • Stonebraker (2014) • Hellman / Diffie (2015) • Berners-Lee (2016) • Hennessy / Patterson (2017) • Bengio / Hinton / LeCun (2018) • Hanrahan / Catmull (2019) • Aho / Ullman (2020) • Dongarra (2021) • Metcalfe (2022)

Registres d'autoritat
Bases d'informació