Avi Wigderson

Avi Wigderson, London 2012

Avi Wigderson (født 9. september 1956 ) er en israelsk matematiker og informatiker . I 2021 ble han tildelt Abelprisen med László Lovász . Begge mottok det for sine grunnleggende bidrag til teoretisk informatikk og diskret matematikk og for sin ledende rolle i deres utvikling til sentrale områder av moderne matematikk.

Liv

Wigderson vokste opp i Haifa som en av tre sønner av Holocaust-overlevende. Faren hans var elektroingeniør og fikk ham til å elske gåter. Med sine egne ord tilbrakte han ungdommen delvis på stranden, delvis som en typisk nerd. Fra 1977 til 1980 studerte han datavitenskap ved Technion i Haifa , Israel , hvor han fikk sin Bachelor of Science (summa cum laude) . I ettertid hyllet han den teoretiske orienteringen til datavitenskapstudier i Israel, som understreket og verdsatte matematikkens rolle, i motsetning til en mer praktisk orientering i USA. Deretter gikk han på Princeton University i USA fra 1980 til 1983 , hvor han fikk sin mastergrad i informatikk og doktorgrad med Richard J. Lipton ( studier i beregningskompleksitet ). Som post-doktorgradsstudent var han ved University of California, Berkeley , ved IBM Almaden Research Center i San José og ved MSRI (1985/86). Fra 1986 underviste han ved det hebraiske universitetet i Jerusalem, sist med full professorat. Siden 1999 har han også vært professor ved Institute for Advanced Study , hvor han har vært heltid siden 2003 ( fast opphold , også Herbert H. Maass professor ). Han ga opp stillingen ved det hebraiske universitetet for det.

Fra 1990 til 1992 var han gjesteforsker ved Princeton University og i 1995/96 ved Institute for Advanced Study.

anlegg

I kompleksitetsteorien undersøker Avi Wigderson problemer på grensene eller utenfor kapasiteten til selv de kraftigste datamaskinene og slike vanskelige problemer som det ikke er kjent noen effektive algoritmer for, og samspillet mellom forutsigbarhet og tilfeldige metoder med applikasjoner, for eksempel i kryptografi og sikkerhet for datanettverk og elektronisk kommunikasjon.

Blant annet undersøkte han ekspandergrafer , interaktive proof-systemer og zero-knowledge proof-systemer .

I 1992 beviste han og Ran Raz at det perfekte matchingsproblemet for beregninger med monotone kretser (dvs. de med bare AND- og ELLER-porter, uten NOT) er lineært i antall noder i grafen. Så det er i utgangspunktet ingen god metode for å løse dette problemet på slike kretser. Dette viste en signifikant forskjell mellom monotone og ikke-monotone kretser. Også tidlig på 1990-tallet begynte han å undersøke innflytelsen av tilfeldige avgjørelser på forutsigbarhet. Dataforskere hadde allerede oppdaget fordelen med å bruke tilfeldige prosesser i beregninger i praksis på 1970-tallet, og på begynnelsen av 1990-tallet virket det som om du kunne gjøre raskere fremgang med nesten alle problemer. Da viste Wigderson og Russell Impagliazzo at, under visse forhold, raske tilfeldige algoritmer alltid kan konverteres til deterministiske algoritmer: kompleksitetsklassen BPP er lik kompleksitetsklassen P under en tilstand som ofte antas å være riktig . Forutsetningen er at kompleksitetsklasse E har eksponentiell kretskompleksitet. Resultatet deres er basert på muligheten for å konstruere egnede pseudo-tilfeldige generatorer, klassifiserte tilfeldige algoritmer i hierarkiet av kompleksitetsklasser og grunnleggende endret måten dataloger tenker på tilfeldige algoritmer. I følge Wigdersons egen vurdering førte dette til erkjennelsen at tilfeldige algoritmer er ganske svake i stedet for sterke algoritmer, siden tilfeldighet kan elimineres under ovennevnte forutsetning.

Sikk-sakk-produktet er en av hans prestasjoner innen kompleksitetsteori. Den har funnet flere bruksområder og brukes for eksempel til å finne en vei ut av en labyrint basert på bare et begrenset antall kryss.

Han skrev over 200 akademiske artikler og veiledet over 100 post-doktorgradsstudenter ved IAS og det hebraiske universitetet (fra 2021). Hans doktorgradsstudenter inkluderer Ran Raz , Prabhakar Ragde (University of Waterloo) og Dorit Aharonov .

Priser og medlemskap

I 1994 ble han tildelt Nevanlinna-prisen for sitt arbeid innen kompleksitetsteori , den høyeste prisen for bidrag innen informatikk fra International Mathematical Union, som deles ut på International Congress of Mathematicians. I 2006 holdt han en plenarforelesning på den internasjonale kongressen for matematikere i Madrid (P, NP og matematikk: et beregningskompleksitetsperspektiv) og i 1990 ble han invitert som foredragsholder ved ICM i Kyōto (Informasjonsteoretiske grunner til beregningsvanskeligheter) . I 2008 mottok han Levi L. Conant-prisen og i 2009 fulgte Gödel-prisen (med Omer Reingold , Salil Vadhan for deres arbeid med sikksakkproduktet av grafer), i 2008 holdt han Gibbs-foredrag, og i 2019 Knuth -Pris . I 2011 ble han valgt til American Academy of Arts and Sciences , i 2013 til National Academy of Sciences , og siden 2018 har han vært stipendiat i Association for Computing Machinery . I 2018 holdt han Colloquium Lectures of the American Mathematical Society (Tittel: 1) Alternative Minimization and Scaling algoritmer: teori, applikasjoner og forbindelser på tvers av matematikk og informatikk; 2) Å bevise algebraiske identiteter; 3) Bevise analytiske ulikheter ). I 2021 mottok han Abel-prisen, en av de høyeste matematiske utmerkelsene.

Privat

Wigderson er gift og har tre barn.

Skrifter (utvalg)

  • Matematikk og beregning. En teori som revolusjonerer teknologi og vitenskap . Princeton University Press, 2019. (Tilgjengelig online via IAS.edu )

weblenker

Individuelle bevis

  1. ↑ a b c Kevin Hartnett, Pioneers Linking Math and Computer Science Win the Abel Prize , Quanta Magazine, 17. mars 2021
  2. ↑ a b c Avi Wigderson and the Second Golden Era of Theoretical Computing , IAS, portrett for Abelprisen 2021.
  3. ↑ Avi Wigderson i Mathematics Genealogy Project (engelsk)Mal: MathGenealogyProject / Maintenance / id used
  4. ↑ a b CV fra Wigderson fra 2010, [1] (pdf) i waybackmachine.
  5. ^ Shlomo Hoory, Nathan Linial, Avi Wigderson: Expander Graphs and their Applications, Bulletin of the AMS, Volum 43, 2006, s. 439-561.
  6. ↑ Oded Goldreich , Silvio Micali , Avi Wigderson: Bevis som ikke gir noe annet enn deres gyldighet, Journal of the ACM, Volum 38, 1991, s. 690-728. De demonstrerte eksistensen av en sikker protokoll for ethvert Secure Multiparty Computation-problem ved å bruke null kunnskapsbevis i 1987.
  7. ^ Raz, Wigderson, monotone kretser for samsvar krever lineær dybde, Journal of the ACM, Volum 39, 1992, s. 736-744, abstrakt
  8. ^ R. Impagliazzo, A. Wigderson: P = BPP hvis E krever eksponensielle kretser: Derandomisering av XOR-lemmaet. I: 29. STOC, 1997, s. 220-229
personlig informasjon
ETTERNAVN Wigderson, Avi
KORT BESKRIVELSE Israelsk matematiker og informatiker
FØDSELSDATO 9. september 1956