Zbivanja - članak

Odjel za prirodoslovlje i matematiku Matice hrvatske

LÁSZLÓ LOVÁSZ I AVI WIGDERSON – DOBITNICI ABELOVE NAGRADE 2021.

Članak Darka Veljana 

Profesor emeritus Sveučilišta Eötvös Loránd u Budimpešti, Mađarska, László Lovász, te profesor s Institute for Advanced Studies (IAS) u Princetonu, N.J., SAD, Avi Wigderson dobili su Abelovu nagradu 2021. godine za bitne doprinose u kombinatorici i diskretnoj matematici i primjene u teorijskom računarstvu, posebice u kriptografiji.

László Lovász je rođen 1948. u Budimpešti. Nakon osnovne škole, bio je prva generacija učenika nove eksperimentalne matematičke gimnazije zajedno sa svojom budućom suprugom, suradnicom i koautoricom Katalin Vesztergombi. László je osvojio od 1963. do 1966. tri zlatne i jednu srebrnu medalju na Međunarodnim matematičkim olimpijadama za učenike srednjih škola, a u to je doba na mađarskoj televiziji osvojio prvu nagradu kao sudionik zatvoren u staklenom kavezu rješavajući napamet postavljena matematička zadatke. Već tada su ga zvali „Laci-Wunderkind“. Doktorirao je 1971. Otad ga je u svijet ozbiljne matematike uveo legendarni Paul Erdös (1913. – 1996.). Kombinatorika, teorija grafova i velike mreže (primjerice, internet) bile su glavne Lovászove grane istraživanja. Podsjetimo se, graf je (konačan) skup vrhova od kojih su neki (susjedni) povezani bridom. Već je 1972. Laci riješio slutnju o savršenom grafu: komplement savršenog također je savršen. Graf je savršen ako je u svakom induciranom podgrafu veličina najveće klike (u kojoj su svaka dva vrha spojena bridom) jednaka kromatskom broju (tj. najmanjem broju boja s kojima se mogu obojiti vrhovi tako da su susjedni vrhovi različito obojeni). Komplement grafa ima iste vrhove, a bridovi i ne-bridovi se zamijene, tj. bridovi se izbrišu, a tamo gdje ih nema – postaju. Npr., bipartitni grafovi su savršeni, jer su veličina najveće klike i kromatski broj jednaki 2. Godine 1978. topološkim je metodama dokazao Kneserovu slutnju iz 1955.: ako sve n-člane podskupove (2n+k)-članog skupa razvrstamo u k+1 klasa, onda bar jedna klasa sadrži dva disjunktna n-skupa. LLL algoritam (nazvan prema autorima Lenstra-Lenstra-Lovász) osmišljen je 1982. Njime se veliki cjelobrojni vektor neke rešetke rastavlja u zbroj najkraćih cjelobrojnih vektora. Među mnogim primjenama LLL algoritma u teoriji brojeva i drugdje u praksi je važan za zaštitu interneta, koju navodno neće moći probiti ni moguća kvantna računala u budućnosti. Rabeći LLL algoritam kasnije je oborena stara Mertensova slutnja iz teorije brojeva čija bi istinitost povlačila čuvenu Riemannovu hipotezu iz 1859. Lovászova hipoteza iz 1969. i danas je neriješena, a kaže da povezan vršno-tranzitivni graf ima Hamiltonov put. Graf je vršno-tranzitivan ako za svaka dva vrha postoji automorfizam grafa koji jedan vrh šalje u drugi. Hamiltonov put prolazi svakim vrhom točno jednom. Još jedna neriješena je Erdös-Faber-Lovászova slutnja (iz 1972.): unija od najviše n potpunih grafova svaki s n vrhova od kojih svaka dva imaju najviše jedan zajednički vrh, može se obojiti s n boja. Nedavno je najavljeno da bi slutnja mogla biti točna za dovoljno velike n. U teorijskom je računarstvu poboljšao granice tzv. Shannonovog kapaciteta. U kombinatornoj teoriji vjerojatnosti poznat je pojam „Lovász local lemma“. Tu je glavna ideja da ako (pod nekim uvjetima) dokažemo da je izvjesna vjerojatnost pozitivna, onda pripadni događaj ili objekt postoji.

Lászlo Lovász je objavio više stotina članaka u vrlo prestižnim časopisima. Autor je ili koautor više knjiga i monografija. Primjerice, Combinatorial Problems and Exercises (prvo izdanje 1979.), Matching Theory (1986.), Discrete Mathematics: Elementary and Beyond (2003., koju je napisao zajedno sa suprugom Katalin), Large Networks and Graph Limits (2012.) i druge. Osim u Budimpešti bio je profesor u Szegedu (gdje je bio voditelj katedre za geometriju), zatim profesor ili gostujući profesor na američkim sveučilištima Princeton, Yale, Chicago, njemačkom Bonnu, a nekoliko je godina radio u kompjutorskom centru tvrtke Microsoft. Dobio je i ranija priznanja za svoj rad: Wolfovu nagradu 1999., Knuthovu nagradu 1999., Kyoto nagradu 2010. i druge. László Lovász je bio predsjednik Međunarodne matematičke unije 2007. – 2010. Kao predsjednik Mađarske akademije znanosti 2014. – 2020. borio se (ali neuspješno) da mađarska vlada nema utjecaja na rad akademije. Otac je četvero djece, sa sedmero unučadi.

Avi Wigderson je rođen 1956. u Haifi, Izrael, u kibucu, od roditelja preživjelih Holocaust u Europi. Tamo je završio osnovnu i srednju školu i nakon tri godine izraelske vojske, upisuje (1980.) i izraelski institut tehnologije („Technion“), gdje proučava i diplomira teorijsko računarstvo i posebno probleme računarske složenosti („complexity theory“) algoritama.

Središnja tema njegovog znanstvenog rada u teorijskom računarstvu, posebice na Princeton Computer Science Departmentu je osim teorije složenosti u kojoj se proučavaju snaga, mogući dosezi, brzina izvršenja algoritama te učinkovitosti današnjih i budućih računala i osmišljavanje novih učinkovitih algoritama za današnja i buduća računala. Od 1999. godine Wigderson je profesor na IAS u Princetonu na području teorijskog računarstva, i autor (ili koautor ) više desetaka članaka iz tog područja, te koautor s H. Maassom knjige Mathematics and Computation: A Theory Revolutionizing Technology and Science, Princeton University Press, 2019. Profesor Wigderson se bavio s tzv. expanderima. J. Bourgain je dokazao da se svaki konačni metrički prostor može smjestiti u neki Euklidski prostor s velikom vjerojatnošću da se pritom dešavaju samo vrlo male distorzije. Primjerice, kad bi se na slučajan način uparila po dva računala, tada bi u toj mreži svi bili povezani, iako neki kablovi nedostaju. To se zove expanderi – jedna od Wigdersonovih omiljenih tema proučavanja.

Što se može, a što ne može riješiti računalom (barem načelno)? Tim se temama Avi Wigderson bavi i danas jer se još uvijek, načelno, ne znaju svi dosezi izračunljivosti i njihovo trajanje.

Osim teorije složenosti u teorijskom računarstvu, Avi Wigderson se bavi i paralelnim algoritmima, nekim aspektima kriptografije, distribuiranim računanjem, neuronskim mrežama i računalima, kao i teorijom grafova što ga je približilo Lovászovim istraživanjima. Avi Wigderson je bio profesor na Hebrew Sveučilištu u Izraelu na Berekelyu u Kaliforniji, SAD, a neko je vrijeme radio u IBM-ovom Institutu za istraživanje i na kraju na IAS u Princetonu. Dobitnik je više priznanja za svoj rad: Nevannlinina nagrada za teorijsko računarstvo 1994., Gödelova nagrada 2004., Knuthova nagrada 2019., i druge.

Prof. dr. sc. Darko Veljan, redoviti profesor u trajnom zvanju (sada u miru) na Prirodoslovno-matematičkom fakultetu - Matematički odsjek Sveučilišta u Zagrebu


❌

◀

▶

Pregled