Leslie Valiant
![]() Leslie Valiant el 2005 (foto de l'MFO) ![]() | |
Biografia | |
---|---|
Naixement | 28 març 1949 ![]() Budapest (Hongria) ![]() |
Nacionalitat | Britànica |
Formació |
|
Tesi acadèmica | Decision Procedures for Families of Deterministic Pushdown Automata (1974) |
Director de tesi | Mike Paterson[2] |
Es coneix per | Teorema de Valiant–Vazirani[1] |
Activitat | |
Camp de treball | Ciències de la computació ![]() |
Ocupació | Matemàtiques Informàtica |
Organització |
|
Membre de | Academia Europaea (2019–) Association for Computing Machinery (membre de l'Association for Computing Machinery) (2012–) Acadèmia Nacional de Ciències dels Estats Units (2001–) American Association for Artificial Intelligence Acadèmia Americana de les Arts i les Ciències Royal Society ![]() |
Obra | |
Estudiant doctoral |
|
Premis
| |
Lloc web | people.deas.harvard.edu… ![]() |
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
- ↑ Valiant, Leslie; Vazirani, V.V.. NP is as easy as detecting unique solutions. DOI 10.1016/0304-3975(86)90135-0.
- ↑ 2,0 2,1 2,2 Leslie Valiant al Mathematics Genealogy Project.
- ↑ David Peleg The EATCS Award 2008 - Laudatio for Professor Leslie Valiant European Association of Theoretical Computer Science.
- ↑ Josh Fishman "‘Probably Approximately Correct’ Inventor, From Harvard U., Wins Turing Award" Chronicle of Higher Education March 9, 2011.
- ↑ ACM Turing Award Goes to Innovator in Machine Learning ACM Computing News
Enllaços externs
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- DBLP:Leslie G. Valiant.
- Pàgina oficial (Inclou fotografies).
- Premi EATCS 2008 Arxivat 2008-07-04 a Wayback Machine..
- Premi Turing 2010