La matemàtica discreta en la informàtica teòrica (László Lovász i Avi Wigderson, Premi Abel 2021)

Ciència computacional teòrica: Aquest migdia a Oslo, en una cerimònia telemàtica sense audiència presencial, el president de l’Acadèmia Noruega de Ciències i Lletres, Hans Petter Graver, ha anunciat la concessió del Premi Abel en l’edició d’enguany a László Lovász i a Avi Wigderson. Tal com ha explicat el president del Comitè Abel, Hans Munthe-Kaas, la concessió respon a “les llurs contribucions fonamentals a la ciència computacional teòrica i a la matemàtica discreta” i “al llur paper destacat en transformar-les en camps centrals de la matemàtica moderna”. Alex Bellos ha estat l’encarregat de fer una exposició sobre el tema, i de parlar amb Lovász i Wigderson per comunicar-li la concessió del guardó. El Premi Abel, establert l’1 de gener del 2002, és dotat actualment en 7,5 milions de corones noruegues (uns 740.000 €). La decisió de la concessió recau en el Comitè Abel, integrat per cinc matemàtics, que treballen a través de nominacions confidencials arribades abans del 15 de setembre.

László Lovász

Lovász László (*Budapest, 9.3.1948) formà part d’un grup d’estudiants de secundària que, en el marc d’un programa experimental, reberen lliçons de matemàtica especialitzada. En aquell curs coneixeria a Katalin Vesztergombi, amb la qui es casaria i amb la qui col·laboraria en nombrosos treballs matemàtics. Amb 15 anys, Lovász guanyaria una medalla d’argent a l’Olimpíada Matemàtica Internacional del 1963. En les tres edicions següents guanyaria tres medalles d’or, i dos premis especials. El seu caràcter de prodigi de les matemàtica fou corroborat en un concurs televisiu. A partir del 1965 començà a publicar articles sobre teoria de grafs. En aquesta etapa conegué Pál Erdős (1913-1996). Estudià matemàtiques a la Universitat Eötvös Loránd de Budapest, on el 1970 presentà la tesi de candidatura. El 1971 s’hi doctorà, amb Tibor Gallai (1912-1992) com a supervisor.

Lovász orientà les seves aportacions en combinatòria i teoria de grafs, i en matemàtica discreta en general, a les qüestions obertes de la ciència computacional teòrica i de la complexitat computacional en particular. El 1972 demostrà la conjectura de Berge segons la qual el complement d’un graf perfecte és també perfecte (Lovász, 1972). En un treball amb Erdős sobre hipergràfs 3-cromàtics posava les bases del que ara es coneix com a lemma local de Lovász.

Després de l’etapa en la Universitat Eötvös Loránd de Budapest, passà a la Universitat József Attila de Szeged, on guanyà la càtedra de geometria (1978). En aquell any, resolia la conjectura de Kneser (que si tots els subconjunts n d’un conjunt de 2n - k elements es divideixen en k + 1 classes, una de les classes conté dos subconjunts n disjunts) amb una prova basada en topologia algebraica (Lovász, 1978). El 1979 demostrava que la capacitat d’error-zero de Shannon del pentàgon és l’arrel quadrada de 5 (Lovász, 1979).

Amb els germans Arjen i Hendrik Lenstra, Lovász inventà l’algoritme de reducció de graella en temps polinòmic que ara es coneix com a LLL per les sigles dels tres autors (Lenstra et al., 1982). El mateix any, Lovász tornava a la Eötvös Loránd de Budapest com a catedràtic de ciència computacional.

El 1993 ocupà la càtedra William K. Lanman de Ciència Computacional i Matemàtica de la Universitat de Yale. En aquesta etapa col·laborà en el desenvolupament de les proves comprovables probabilísticament (Feige et al., 1998).

El 1999 deixà la universitat per treballar com a investigador a Microsoft. El 2006, tornà a Budapest per esdevindre professor a la Universitat Eötvös Loránd i investigador de l’Institut Alfréd Rényi de Matemàtiques.

Entre el 2007 i el 2010 fou president de la Unió Matemàtica Internacional. Del 2014 al 2020 ha estat president de l’Acadèmia Hongaresa de Ciències.

.

Fa quatre anys i mig, amb motiu del 60è aniversari d’Avi Wigderson, László Lovász pronunciava a Princeton una conferència sobre el sentit del concepte genèric

Avi Wigderson

אבי ויגדרזון‎ (*9.9.1956) estudià al Technion de Haifa, on es graduà en ciències computacionals (1980). Passà a Princeton on, sota la supervisió de Richard Lipton (*1946), realitzà la tesi doctoral sobre estudis en complexitat computacional, defensada el 1983.

El 1986, Widgerson tornà a Israel per ocupar una plaça en la Universitat Hebrea de Jerusalem, on esdevindria professor titular en el 1991.

Amb Oded Goldreich i Silvio Micali treballà en la construcció de sistemes de prova amb coneixement zero. Aquests autors demostraren que aquestes proves poden utilitzar-se per demostrar, en secret, qualsevol resultat públic sobre dades secretes, i d’ací l’aplicació que han tingut en criptografia i criptomoneda en les darreres dècades.

Amb Noam Nisan, Widgerson treballà en la relació entre la duresa d’un problema i l’aleatorietat. La introducció d’un generador pseudoaleatori en un algoritme pot contribuir a atacar la duresa d’un problema. Amb Russell Impagliazzo, demostrà amb tot que l’aleatorietat és un recurs comparable amb el temps.

El 1999, Widgerson s’uní a l’Institute for Advanced Study (IAS) de Princeton. El 2000, juntament amb Omer Reingold i Salil Vadhan, desenvolupà el producte graf de ziga-zaga, en el que el producte hereta la mida del factor graf gran i el grau del factor graf petit, i les propietats d’expansió de tots dos. La iteració d’aquest producte genera expansors de grau constant de tota mida que actuen com una ona d’entropia.

Fa unes setmanes, Wigderson parlava sobre proves amb coneixement zero al segon canal de Numberphile

Lligams:

- Lovász and Wigderson to share the Abel Prize, comunicat de premsa de la concessió.

- Pàgina web de Lászlo Lovász a la Universitat Eötvös Loránd de Budapest.

- Pàgina web d’Avi Wigderson a l’Institute for Advanced Study de Princeton.

- Randomness and Pseudorandomness. Avi Wigderson (2009).