El Premio Abel reconoce las relaciones de las matemáticas discretas con la informática



El periódico digital de Alicantur Noticias

El Premio Abel reconoce las relaciones de las matematicas discretas

El matemático Lázló Lovász y el informático teórico Avi Widgerson son los ganadores del Premio Abel 2021 por «sus contribuciones fundamentales al cálculo teórico y las matemáticas discretas, así como su papel principal en convertirlas en campos centrales de las matemáticas modernas». Ambos trabajaron sobre una de las estructuras discretas más populares, los gráficos y sus resultados se aplican en diferentes contextos criptográficos.

Widgerson (1956) creció en la ciudad costera israelí de Haifa en una familia judía de origen polaco que sobrevivió al holocausto nazi. En 1983, obtuvo su doctorado en complejidad computacional de la Universidad de Princeton y su carrera ha sido meteórica desde entonces. El premio Abel es el último de una larga lista de honores para el trabajo influyente, innovador y perspicaz de Widgerson sobre los fundamentos de la computación teórica. Estos incluyen 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 – ganó tres medallas de oro en las Olimpiadas Internacionales de Matemáticas, dos veces con reconocimiento especial del jurado – dentro de una generación de oro de brillantes jóvenes matemáticos estimulados por el entorno científico único de post -la guerra de Budapest. Entre las influencias del joven Lovász destaca el mítico y errante matemático Pául Erdős, con quien estableció una fructífera colaboración desde la adolescencia. Al igual que Widgerson, el Premio Abel es la culminación de una serie de reconocimientos: los Premios Gödel y Knuth, así como el Premio Wolf, el Premio Kyoto y el Premio Barcelona Hypatia.

Los objetos de interés para ambos investigadores son estructuras discretas. Estos son, por ejemplo, conjuntos finitos, números enteros, fórmulas lógicas o algoritmos.

Los objetos de interés para ambos investigadores son estructuras discretas. Estos son, por ejemplo, conjuntos finitos, números enteros, fórmulas lógicas o algoritmos; por el contrario, la función de la temperatura de una habitación, la curvatura del ala de un avión, donde la variación ocurre regularmente para los puntos vecinos, son estructuras continuas. En resumen, las estructuras discretas son objetos matemáticos que se pueden dividir en partes bien definidas. El ejemplo por excelencia son los gráficos: objetos formados por conjuntos de puntos y relaciones entre ellos – denominados vértices y arcos respectivamente -. Los gráficos se utilizan para modelar, por ejemplo, la red metropolitana de una ciudad o las relaciones entre individuos en una red social; en este segundo caso, el siguiente gráfico se construye tomando personas como vértices y dos personas estarán conectadas por un borde si se conocen.

Lovász inició muchas de las teorías en este campo de investigación y logró importantes resultados. Entre ellos, mostró hipótesis abiertas, como las llamadas Conjetura de Kneser, formulado en 1955, o el escurridizo conjetura de la gráfica perfecta. También ha abierto campos completamente inexplorados: optimización discreta, teoría del acoplamiento en gráficos o la Algoritmo LLL, resultado hoy fundamental en toda la teoría de la criptografía poscuántica. En los últimos años, Lovász ha sido uno de los principales desarrolladores de la teoría de gráficos de límites, una teoría unificadora que intenta mezclar matemáticas discretas y objetos continuos.

Widgerson también ha trabajado con gráficos, en particular, en resultados de complejidad. Dada una estructura discreta muy grande – por ejemplo, pensemos en el gráfico asociado a una de las redes sociales tan populares hoy – y una propiedad que queremos estudiar – por ejemplo, la aparición de comunidades altamente conectadas, que serían grupos de entrelazados vértices con muchas aristas, los llamados clústeres. ¿Podemos inventar un mecanismo que controle esta propiedad de manera eficiente?

Este problema de decisión (solo nos interesa si se puede hacer o no) es extremadamente difícil y lleva tiempo si el gráfico es grande. En este sentido, teoría de la complejidad Busque algoritmos que funcionen mejor que los ya conocidos y / o demuestren formalmente que la eficiencia de un algoritmo dado no se puede mejorar. Quizás el principal problema en este campo es el famoso P = NP, uno de los siete problemas del milenio, y sobre el que Widgerson hizo aportes fundamentales que dieron lugar a la teoría de la complejidad tal como la conocemos hoy.

En cierto sentido, la teoría de la complejidad ha crecido en torno a Widgerson durante los últimos 40 años. Pero además, Widgerson ha contribuido de forma decisiva en muchas otras direcciones: es uno de los investigadores líderes en la denominada prueba de conocimiento cero, y fue el creador del llamado producto en zigzag para la construcción de gráficos de expansión –Que son gráficos muy bien conectados, pero a la vez con muy pocas aristas; Estas estructuras ya estaban siendo estudiadas por anteriores galardonados con el Premio Abel, en parte debido a su conexión con otras ramas de las matemáticas como la teoría de grupos.

Los dos ganadores coinciden en el uso de ideas probabilísticas muy novedosas que permitan obtener resultados que, de forma determinista, serían imposibles. Así, Lovász inventó el llamado lema local, lo que nos permite probar la existencia de objetos combinatorios que de otro modo sería impensable encontrar. Y, por su parte, Widgerson ha hecho contribuciones esenciales en el uso de la probabilidad para encontrar algoritmos eficientes que mejoren cualquier algoritmo determinista.

El reconocimiento del trabajo de toda la vida de Lovász y Widgerson confirma, una vez más, el papel fundamental de la matemática discreta, la informática y su interacción en el desarrollo de la matemática contemporánea.

Rue Juanjo Es investigador del Departamento de Matemáticas y del Instituto de Matemáticas (ImTech) de la Universidad Politécnica de Cataluña, y miembro investigador del Centro de Investigaciones Matemáticas (CRM) y de la Escuela Técnica Superior de Matemáticas de Barcelona (BGSMath).

Café y teoremas es una sección dedicada a las matemáticas y el entorno en el que se crea, coordinada por el Instituto de Ciencias Matemáticas (ICMAT), en la que investigadores y miembros del centro describen los últimos avances en esta disciplina, comparten puntos de encuentro entre las matemáticas y otros y expresiones culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar el 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 el café en teoremas».

Traducción, edición y coordinación: Ágata A. Timón García-Longoria (ICMAT)

Puedes seguir SUJETO en Facebook, Gorjeo es Instagramo regístrate aquí para recibir nuestro boletín semanal.