El Premio Abel reconoce las relaciones de la matem¨¢tica discreta con las ciencias de la computaci¨®n

El matem¨¢tico L¨¢zl¨® Lov¨¢sz y el inform¨¢tico te¨®rico Avi Widgerson son los galardonados del premio Abel 2021 por ¡°sus contribuciones fundamentales a la inform¨¢tica te¨®rica y las matem¨¢ticas discretas, as¨ª como su destacado papel para convertirlas en campos centrales de las matem¨¢ticas modernas¡±. Ambos han trabajado en una de las estructuras discretas m¨¢s populares, los grafos, y sus resultados se aplican en diferentes contextos de la criptograf¨ªa.

Widgerson (1956) creci¨® en la costera ciudad israel¨ª de Haifa, en una familia jud¨ªa de origen polaco que sobrevivi¨® al holocausto nazi. En 1983, obtuvo su doctorado en el ¨¢rea de la complejidad computacional en la universidad de Princeton y, desde entonces, su carrera ha sido mete¨®rica. El premio Abel es el ¨²ltimo de una larga lista de reconocimientos a los influyentes, innovadores y profundos trabajos de Widgerson en la fundamentaci¨®n de la inform¨¢tica te¨®rica. Entre ellos, el premio Nevanlinna, el premio G?del y el premio Knuth.

Por su parte, Lov¨¢sz (Budapest, 1948) fue un ni?o prodigio de las matem¨¢ticas ¨Cgan¨® tres medallas de oro en las olimpiadas matem¨¢ticas internacionales, en dos ocasiones con un reconocimiento especial del jurado¨C, dentro de una generaci¨®n de oro de j¨®venes matem¨¢ticos brillantes, estimulados por el ambiente cient¨ªfico ¨²nico de la Budapest de postguerra. Entre las influencias del joven Lov¨¢sz, destaca al m¨ªtico y errante matem¨¢tico P¨¢ul Erd?s, con qui¨¦n estableci¨® una colaboraci¨®n muy fruct¨ªfera desde su adolescencia. Del mismo modo que Widgerson, el premio Abel es el colof¨®n a una serie de reconocimientos: los premios G?del y Knuth, as¨ª como el premio Wolf, el premio Kyoto y el premio Hipatia de Barcelona.

Los objetos de inter¨¦s de ambos investigadores son las estructuras discretas. Estas son, por ejemplo, los conjuntos finitos, los n¨²meros enteros, las f¨®rmulas l¨®gicas o los algoritmos

Los objetos de inter¨¦s de ambos investigadores son las estructuras discretas. Estas son, por ejemplo, los conjuntos finitos, los n¨²meros enteros, las f¨®rmulas l¨®gicas o los algoritmos; en contraposici¨®n, la funci¨®n temperatura de una habitaci¨®n, la curvatura del ala de un avi¨®n, en donde la variaci¨®n se da de manera suave para puntos cercanos, son estructuras continuas. En definitiva, las estructuras discretas son objetos matem¨¢ticos que pueden dividirse en partes bien delimitadas. El ejemplo por excelencia son los grafos: objetos formados por conjuntos de puntos y relaciones entre ellos ¨Cllamados v¨¦rtices y aristas, respectivamente¨C. Los grafos sirven para modelar, por ejemplo, la red de metro de una ciudad o las relaciones entre individuos en una red social; en este segundo caso, el grafo subyacente se construye tomando como v¨¦rtices las personas y dos personas estar¨¢n conectadas mediante una arista si se conocen.

Lov¨¢sz ha iniciado muchas de las teor¨ªas de este campo de investigaci¨®n y ha obtenido importantes resultados. Entre ellos, ha demostrado conjeturas abiertas, como la llamada conjetura de Kneser, formulada en el a?o 1955, o la escurridiza conjetura de los grafos perfectos. Tambi¨¦n ha abierto campos completamente inexplorados: la optimizaci¨®n discreta, la teor¨ªa de emparejamientos en grafos o el algoritmo LLL, resultado que hoy en d¨ªa es fundamental en toda la teor¨ªa de criptograf¨ªa post-cu¨¢ntica. En los ¨²ltimos a?os, Lov¨¢sz ha sido uno de los m¨¢ximos desarrolladores de la teor¨ªa de grafos l¨ªmite, una teor¨ªa unificadora que intenta mezclar la matem¨¢tica discreta y los objetos continuos.

Widgerson tambi¨¦n ha trabajado con grafos, en concreto, en resultados de complejidad. Dada una estructura discreta muy grande ¨Cpor ejemplo, pensemos en el grafo asociado a alguna de las redes sociales tan populares hoy en d¨ªa¨C, y una propiedad que queramos estudiar ¨Cpor ejemplo, la aparici¨®n de comunidades muy conectadas, que ser¨ªan grupos de v¨¦rtices entrelazados con muchas aristas, los denominados cl¨²sters. ?Podemos inventar un mecanismo que compruebe esa propiedad, de forma eficiente?

Este problema de decisi¨®n ¨C¨²nicamente nos interesa saber si se puede o no¨C es extremadamente dif¨ªcil ¨Cy costoso en tiempo¨C si el grafo es grande. En este sentido, la teor¨ªa de la complejidad busca algoritmos que funcionen mejor que los ya conocidos y/o demostrar formalmente que no se puede mejorar la eficiencia de un algoritmo dado. Posiblemente el problema estrella de este campo es el famoso P=NP, uno de los siete problemas del milenio, y sobre el que Widgerson ha realizado contribuciones fundacionales que han dado lugar a la teor¨ªa de complejidad tal y como la conocemos hoy.

En cierto modo, la teor¨ªa de complejidad ha crecido alrededor Widgerson en los ¨²ltimos 40 a?os. Pero adem¨¢s, Widgerson ha contribu¨ªdo de manera decisiva en muchas otras direcciones: es uno de los investigadores de referencia en las llamadas pruebas de conocimiento cero, y fue el creador del llamado producto zig-zag para la construcci¨®n de grafos expansores ¨Cque son grafos muy bien conectados, pero a la vez con muy pocas aristas; estas estructuras ya fueron objeto de estudio de los anteriores galardonados con el premio Abel, en parte por su conexi¨®n con otras ramas de las matem¨¢ticas como la teor¨ªa de grupos.

Los dos galardonados coinciden en el uso de ideas probabil¨ªsticas muy novedosas que permiten obtener resultados que, de manera determinista ser¨ªa imposible. As¨ª, Lov¨¢sz invent¨® el denominado lema local, que permite demostrar la existencia de objetos combinatorios que, de otra forma, ser¨ªa impensable encontrar. Y, por su parte, Widgerson ha realizado contribuciones esenciales en el uso de la probabilidad para encontrar algoritmos eficientes que mejoran cualquier algoritmo determinista.

El reconocimiento del trabajo de toda una vida de Lov¨¢sz y Widgerson confirma, una vez m¨¢s, el papel fundamental de la matem¨¢tica discreta, de las ciencias de la computaci¨®n y de su interacci¨®n en el desarrollo de las matem¨¢ticas contempor¨¢neas

Juanjo Ru¨¦ es investigador del Departamento de Matem¨¢ticas y del Instituto de Matem¨¢ticas (ImTech) de la Universitat Polit¨¨cnica de Catalunya, y miembro investigador del Centre de Recerca Matem¨¤tica (CRM) y de la Barcelona Graduate School of Mathematics (BGSMath)

Caf¨¦ y Teoremas es una secci¨®n dedicada a las matem¨¢ticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matem¨¢ticas (ICMAT), en la que los investigadores y miembros del centro describen los ¨²ltimos avances de esta disciplina, comparten puntos de encuentro entre las matem¨¢ticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar caf¨¦ en teoremas. El nombre evoca la definici¨®n del matem¨¢tico h¨²ngaro Alfred R¨¦nyi: ¡°Un matem¨¢tico es una m¨¢quina que transforma caf¨¦ en teoremas¡±.

Traducci¨®n, edici¨®n y coordinaci¨®n: ?gata A. Tim¨®n Garc¨ªa-Longoria (ICMAT)

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aqu¨ª para recibir nuestra newsletter semanal.