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 a la informática teórica y las matemáticas discretas, así como su papel destacado en convertirlas en los campos centrales de las matemáticas modernas”. Ambos han trabajado en una de las estructuras discretas más populares, gráficos, y sus resultados se aplican en diferentes contextos de criptografía.
Widgerson (1956) creció en la ciudad costera israelí de Haifa, en una familia judía de origen polaco que sobrevivió a la masacre nazi. En 1983 obtuvo su doctorado en complejidad informática 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 honores para el trabajo influyente, innovador e informativo de Widgerson basado en computadoras teóricas. Entre ellos se encuentran el Premio Nevanlinna, el Premio Gödel y el Premio Knuth.
A su vez, Lovász (Budapest, 1948) fue un prodigio de las matemáticas – ganó tres medallas de oro en los Juegos Olímpicos Internacionales de Matemática, dos veces con un reconocimiento especial del jurado – dentro de una generación dorada de brillantes jóvenes matemáticos estimulados por el entorno científico único. de la Budapest de la posguerra. Bajo las influencias del joven Lovász se encuentra el mítico y errante matemático Pául Erdős, con quien ha disfrutado de una muy fructífera colaboración desde su adolescencia. Al igual que Widgerson, el premio Abel es la culminación de una serie de premios: los premios Gödel y Knuth, así como el premio Wolf, el premio Kyoto y el premio Barcelona Hypatia.
Los intereses de ambos investigadores son las estructuras discretas. Estos son, por ejemplo, conjuntos finitos, números enteros, fórmulas lógicas o algoritmos.
Los intereses de ambos investigadores son las estructuras discretas. Estos son, por ejemplo, conjuntos finitos, números enteros, fórmulas lógicas o algoritmos; por otro lado, la función de temperatura de una habitación, la curvatura del ala de un avión, donde la variación ocurre suavemente para puntos cercanos, 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, llamados vértices y aristas, respectivamente. Los gráficos se utilizan 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 gráfico subyacente se compila para tomar 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ó conjeturas abiertas, como el llamado La sospecha de Kneser, formulado en 1955, o el escurridizo conjetura de carta perfecta. También abrió campos completamente sin explotar: optimización discreta, la teoría de emparejamientos en gráficos o la Algoritmo LLL, un resultado que es hoy fundamental en toda la teoría de la criptografía post-cuántica. En los últimos años, Lovász ha sido uno de los mejores desarrolladores de la teoría de restringir gráficos, una teoría unificadora que intenta mezclar matemáticas discretas y objetos continuos.
Widgerson también trabajó específicamente en gráficos sobre resultados de complejidad. Dada una estructura discreta muy grande – pensemos, por ejemplo, en el gráfico asociado a una de las redes sociales que son tan populares hoy – y una característica que queremos estudiar – por ejemplo, la aparición de comunidades altamente conectadas, qué grupos de vértices entretejidos con muchas aristas, los llamados racimos. ¿Podemos idear un mecanismo que controle efectivamente esta propiedad?
Este problema de decisión, solo queremos saber si se puede hacer o no, es extremadamente difícil y requiere mucho tiempo cuando el gráfico es grande. En este sentido, teoría de la complejidad Busque algoritmos que funcionen mejor que lo que ya se conoce y / o que puedan demostrar formalmente que la eficiencia de un algoritmo dado no se puede mejorar. Quizás el problema estrella en esta zona sea el más 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 modo, la teoría de la complejidad ha crecido en torno a Widgerson durante los últimos cuarenta años. Pero además, Widgerson ha hecho una contribución decisiva en muchos otros campos: es uno de los investigadores líderes en el llamado pruebas de conocimiento cero, y fue el creador del llamado producto en zigzag para la construcción de agrandar gráficos –Estos son gráficos muy bien enlazados, pero a la vez con muy pocos bordes; Estas estructuras ya han sido objeto de estudio por anteriores beneficiarios del Premio Abel, en parte por su asociación con otras ramas de las matemáticas como la teoría de grupos.
Los dos ganadores coinciden en utilizar muchas nuevas ideas probables que permitan obtener resultados que serían imposibles de forma determinista. Entonces, Lovász ideó el llamado lema local, lo que permite demostrar la existencia de objetos combinatorios que de otro modo sería impensable encontrar. Y por su parte, Widgerson ha hecho contribuciones vitales 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 reafirma el papel fundamental de las matemáticas discretas, la informática y su interacción en el desarrollo de las matemáticas contemporáneas.
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 Superior de Matemáticas de Barcelona (BGSMath).
Café y declaraciones 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 materia, compartiendo puntos de encuentro entre las matemáticas y otros y expresiones culturales y recordemos a quienes caracterizaron su desarrollo y supieron convertir el café en declaraciones. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que convierte el café en declaraciones”.
Traducción, edición y coordinación: Ágata A. Timón García-Longoria (ICMAT)
Puedes seguir SUJETO en Facebook, Gorjeo y Instagramo regístrate aquí para recibir nuestro boletín semanal.
