Informaticianul câștigă premiul Turing pentru munca fundamentală asupra aleatoriei

om de știință în calcul și matematician Avi Wigderson al Institutului pentru Studii Avansate (IAS) de la Universitatea Princeton a câștigat cel 2023 AM Premiul Turing. Premiul, care este acordat anual de Asociația pentru Mașini de Calcul (ACM) unui informatician pentru contribuțiile sale în domeniu, vine cu 1 milion de dolari datorită Google. Este numit în onoarea matematicianului britanic Alan Turing, care a contribuit la dezvoltarea unei baze teoretice pentru înțelegerea calculului mașină.

Wigderson este onorat „pentru contribuțiile fundamentale la teoria calculului, inclusiv pentru remodelarea înțelegerii noastre a rolului aleatoriei în calcul și pentru deceniile sale de conducere intelectuală în informatica teoretică”. A câștigat și prestigiosul Premiul Abel (în esență, Nobelul pentru matematică) în 2021 pentru munca sa în informatica teoretică – prima persoană care a fost atât de dublă onorat.

„Avi a adus contribuții fundamentale la teoria calculului de la algoritmi paraleli la criptografie la absolut toate aspectele teoriei complexității.” spuse Shafi Goldwasser, director al Institutului Simons pentru Teoria Calculului, care a câștigat premiul Turing 2012. „Numerele sale contribuții de-a lungul deceniilor în domeniile derandomizării și pseudoaleatoriei ne-au condus la o înțelegere profundă a rolului profund al aleatoriei în calcul.”

Născut în Haifa, Israel, Wigderson era fiul unui inginer electrician și al unei asistente. Tatăl său i-a transmis fiului său dragostea de a rezolva puzzle-uri și matematică. Wigderson era student la Technion (Institutul Israelian de Tehnologie) și a continuat să-și obțină doctoratul în informatică la Princeton în 1983. A deținut câteva funcții pe termen scurt înainte de a se alătura facultății de la Universitatea Ebraică trei ani mai târziu. El a fost cu IAS din 1999 și rezident cu normă întreagă din 2003.

În timp ce computerele sunt sisteme fundamental deterministe, cercetătorii au descoperit în anii 1970 că își pot îmbogăți algoritmii lăsându-i să facă alegeri aleatorii în timpul calculului, în speranța de a-și îmbunătăți eficiența. Și a funcționat. A fost mai ușor pentru informaticieni să înceapă cu o versiune randomizată a unui algoritm determinist și apoi să o „de-randomizeze” pentru a obține un algoritm care era determinist.

În 1994, Wigderson a fost co-autor al a paper seminalr despre duritate versus aleatorie cu Noam Nisan, demonstrând că, oricât de utilă poate fi aleatorietatea, nu este o necesitate. În esență, „Fiecare algoritm probabilist care este eficient poate fi înlocuit cu unul determinist, deci nu aveți nevoie cu adevărat [randomness]”, a spus el. “Puterea despre care se crede că este în algoritmii probabilistici nu există.” Ulterior, el a coautor doi Mai mult foarte influent lucrări care extind în continuare această lucrare despre aleatorie, printre multe altele.

Cartea lui Wigderson din 2019, Matematică și calcul: o teorie care revoluționează tehnologia și știința, este disponibil pentru descărcare pe site-ul său. „O temă centrală este că calculul are loc peste tot, nu doar în computere”, a spus Wigderson pentru Ars. „Face parte din procesele din creierul nostru, din modul în care putem vorbi și din celulele corpului nostru, dar și din creșterea copacilor sau a vremii și a lucrurilor cerești. În toate aceste procese naturale, există legile naturii, care sunt locale, și ele evoluează sisteme. La fel ca într-un computer, există reguli foarte simple și începi cu o problemă și descoperi o soluție complexă pentru aceasta. Deci, metodologia este aplicabilă în esență oricărui proces sau studiu științific. Există colaborări fantastice cu statistici. fizica, cu fizica cuantică, cu biologia computațională, cu economia, cu știința socială – o mulțime de conexiuni frumoase, extrem de fructuoase.”

Cercetarea proprie a lui Wigderson este pur teoretică. „Nu sunt motivat de aplicații”, a spus el. „Dar știu că lucrarea fundamentală, găsim utilizări. Gândește-te la Alan Turing. A scris o lucrare de matematică în logică într-un jurnal obscur despre Entscheidungsproblem. Nu a fost motivat de cerere. Dar asta este ceea ce începe informatica. El însuși a recunoscut că modelul pe care îl sugera este atât de simplu, încât putem începe să-l construim.”

Acestea fiind spuse, el mărturisește că a fost plăcut surprins de eventuala aplicare a lucrării sale dovezi interactive fără cunoștințe la mijlocul anilor 1980. Împreună cu Silvio Micali și Oded Goldreich, Wigderson a extins lucrările anterioare ale lui Micali privind demonstrațiile interactive la problemele NP, ajungând la concluzia că soluția pentru fiecare astfel de problemă poate fi demonstrată și cu o dovadă de cunoștințe zero.

„Practic am descoperit că tot ceea ce poate fi dovedit, poate fi dovedit, fără a dezvălui persoanei care verifică dovada orice cunoștințe pe care nu le cunoștea”, a spus Wigderson. „Motivația a venit din criptografie, unde vreau să vă demonstrez că mi-am selectat cheia secretă așa cum o cere protocolul, dar nu vreau să vă spun care este cheia mea secretă. Rezultatul este foarte general și deși foarte satisfăcătoare, a fost o soluție teoretică pe care mi s-a părut foarte complicat de implementat.Dar acum variante ale acesteia fac parte din blockchain-uri și alte sisteme cripto.Așa că, uneori, suntem surprinși de diligența oamenilor cărora le pasă cu adevărat de practică și își doresc cu adevărat vezi lucrurile mergând.”

Wigderson rămâne la fel de activ curios ca întotdeauna și este deosebit de încântat să colaboreze cu noi grupuri de postdoc în fiecare an. Un proiect actual se referă optimizare convexă în contexte non-euclidiene. Optimizarea convexă a fost aplicată pe scară largă în învățarea automată, procesarea semnalului, viziunea computerizată și sistemele de control automat, de exemplu. Proiectul lui Wigderson urmărește „să generalizeze teoria la varietati, la structuri care apar într-o varietate de domenii matematice și fizice – teoria informației cuantice, teoria invariante și cu siguranță în informatică”, a spus el. “Apare și în analiză, pentru demonstrarea inegalităților și în algebră pentru demonstrarea identităților. Este destul de larg și sunt foarte încântat de asta.”