Avi Wigderson

Hovedtemaet for Wigdersons forskning har vært datakompleksitet. Dette dreier seg om hvor raske og effektive algoritmer og utregningsmetoder er, spesielt når mengden data som skal behandles øker. Et sentralt spørsmål i dette feltet er det såkalte P versus NP-problemet: Er det teoretisk mulig å løse visse klasser av problemer i polynomtid, altså slik at beregningstiden ikke vokser raskere enn et polynom i størrelsen på inndata? Dette og andre problemer fra datavitenskapen har Wigderson arbeidet matematisk med, og fått frem som et viktig felt også i matematikk. Han har også mange interessante resultater i mer klassisk matematikk, bevist med metoder og innsikt fra datavitenskap og kompleksitetsteori.

De senere årene har kravene til sikkerhet rundt dataoverføringer vokst kraftig. De fleste banktjenester utføres nå over nett, og sikker håndtering av for eksempel passord og bankID er viktig. Kompleksitetsteori er viktig i denne forbindelse, fordi man må sikre at tiden det vil ta å regne ut andres skjulte krypteringsnøkler (det som trengs for å kunne lese en hemmelig melding sendt på nett) er så lang at det i praksis ikke er mulig. Et lignende problem er «zero-knowledge»-bevis, eller kunnskapsløse bevis. Her er temaet hvordan man kan finne felles kjent informasjon basert på informasjon man ikke vil dele. Wigderson har funnet resultater som sikrer at slike kunnskapsløse bevis finnes i mange viktige tilfeller. Dette har anvendelser blant annet i blokkjedeteknologi og kryptovaluta.

Wigderson har også studert sannsynlighetsteoretiske aspekter ved databeregninger. Det er flere eksempler på algoritmer som løser problemer raskt ved å trekke tilfeldige tall. Dette medfører som regel en risiko for feil, da det kan finnes uheldige valg av tall eller svakheter ved måten de tilfeldige tallene trekkes på. Wigderson har vist at mange slike algoritmer kan erstattes med algoritmer uten denne svakheten, på bekostning av en moderat økning i beregningstid.

Wigderson ble født i Haifa, Israel. Etter å ha fullført laveregradsutdanning i Israel flyttet han til USA, der han oppnådde doktorgraden ved Princeton University i 1983. Senere har han arbeidet ved matematiske og datavitenskapelige institutter ved amerikanske og israelske universiteter. Siden 1999 har han vært professor ved School of Mathematics, Institute of Advanced Study, i Princeton, USA.

Han har samarbeidet vitenskapelig med et stort antall andre forskere, og har veiledet mange unge forskere i doktorgradsstudier og som postdoktorer.

Wigderson ble, sammen med László Lovász, tildelt Abelprisen for 2021. I komiteens begrunnelse står det at prisen tildeles dem «for deres grunnleggende bidrag til teoretisk datavitenskap og diskret matematikk, og deres ledende rolle i å gjøre dem til sentrale felt i moderne matematikk».

• diskret matematikk
• kompleksitetsklasser