Premio Abel para el estudio de la complejidad de los algoritmos

Lovász y Wigderson

Lovász y Wigderson son los nuevos ganadores del Premio Abel. Imagen: Abel Prize

  • László Lovász (Universidad Eötvös Loránd, Hungría) y Avi Wigderson (Instituto de Estudios Avanzados de Princeton, EE. UU.) son los ganadores del Premio Abel 2021 de la Academia Noruega de Ciencias y Letras.
  •  “Un eje central en la contribución científica de los galardonados es la incorporación de métodos aleatorios y probabilísticos a la resolución de problemas”, afirma Javier Aramayona, investigador del ICMAT.
  • Estas ideas son la base teórica de la criptografía moderna.

Madrid, 17 de marzo de 2021. La teoría de la complejidad computacional estudia la velocidad y eficiencia de los algoritmos y aporta las bases teóricas fundamentales para la criptografía actual. Es una de las ramas principales de teoría de la computación, junto al diseño de algoritmos. Mientras que esta última desarrolla métodos eficientes para resolver problemas computables, la complejidad computacional muestra las limitaciones inherentes en los algoritmos. “Además de ser un campo fascinante desde un punto de vista puramente teórico, tiene aplicaciones importantes a la vida real, como la transmisión segura de información y el diseño de redes de comunicación robustas”, asegura Javier Aramayona, investigador del ICMAT.

La complejidad computacional nació en la década de 1970 y desde entonces está ligada a las matemáticas discretas, en concreto, a la teoría de grafos, las series y las permutaciones. Por un lado, estas son las herramientas básicas para el estudio de los algoritmos, pero, por otro, las aplicaciones, los conceptos y las técnicas de la complejidad computacional han dado lugar a nuevos retos, han permitido nuevos enfoques de investigación y han resuelto importantes problemas abiertos en las matemáticas puras y aplicadas.

László Lovász y Avi Wigderson han liderado estos avances durante las últimas décadas y, por ello, hoy han sido reconocidos con el Premio Abel de la Academia Noruega de Ciencias y Letras. “Un eje central en la contribución científica de los galardonados es la incorporación de métodos aleatorios y probabilísticos a la resolución de problemas”, declara Aramayona. El premio incluye una cuantía de unos 750 000 euros y es el reconocimiento más prestigioso de las matemáticas a toda una carrera.

Lovász ha sido pionero en idear las conexiones entre las matemáticas discretas y la ciencia computacional. Ha trabajado tanto desarrollando los fundamentos teóricos como en el diseño de aplicaciones prácticas. Una de sus principales contribuciones es el algoritmo LLL, en el que se basan los únicos sistemas de encriptación conocidos capaces de resistir el ataque de un ordenador cuántico, de momento. Debe su nombre a Lovász y los hermanos Arjen y Hendrik Lenstra, y adicionalmente ha sido aplicado con éxito a la teoría de números y a la computación móvil.

También es el autor del “lema local”, una herramienta para demostrar la existencia de objetos combinatorios poco comunes. Por otro lado, mostró cómo ejecutar cierto tipo de programas –llamados semidefinidos– de forma eficiente, lo que revolucionó el diseño de algoritmos. También ha contribuido a la llamada teoría de los paseos aleatorios y ha estudiado las demostraciones verificables probabilísticamente –que ofrecen la posibilidad de comprobar demostraciones matemáticas leyendo únicamente un pequeño número de signos–. “Este trabajo constituye la piedra fundacional para el diseño de buenas aproximaciones para problemas de optimización”, afirma Aramayona.

Por su parte, Avi Widgerson es experto en el papel de la aleatoriedad en la informática. Un algoritmo aleatorizado es aquel que lanza monedas para obtener una solución –muy probablemente– correcta. Habitualmente, introducir la aleatoriedad permite convertir una problema difícil –irresoluble en un ordenador en un tiempo limitado– en uno fácil. Wigderson demostró que todo algoritmo aleatorizado puede desaleatorizarse y convertirse en uno determinista de eficiencia comparable; además la desaleatorización es genérica y universal, independientemente de los detalles internos del algoritmo aleatorizado.

Su trabajo está estrechamente ligado a la construcción de objetos pseudoaleatorios –es decir, que parecen aleatorios–. Wigderson ha propuesto métodos para construir generadores pseudoaleatorios, capaces de convertir pocos bits realmente aleatorios en muchos bits pseudoaleatorios. También ideó demostraciones de conocimiento cero que permiten verificar enunciados, en situaciones en las que ninguna de las partes quiere revelar información adicional, aparte de la validez del enunciado, y que hoy en día se emplean en las criptomonedas. “Son conceptos de suma importancia práctica, cuyo objetivo es convencer a alguien de que se posee cierta información sin revelar ningún dato adicional aparte de que se dispone de la información”, señala Aramayona. Wigderson probó que las demostraciones de conocimiento cero pueden servir para verificar, en secreto, cualquier resultado público sobre datos secretos.

László Lovász

László Lovász (1948, Budapest, Hungría) es catedrático del Instituto de Matemáticas de la Universidad Eötvös Loránd (Hungría). Estudió y obtuvo el doctorado –en 1970– en esa misma institución, y para entonces ya había intervenido en congresos internacionales y tenía 15 artículos publicados. Tras ello, fue contratado por la misma universidad y después por la Universidad József Attila de Szeged (Hungría), donde se convirtió en Catedrático de Geometría en 1978. Regresó a Eötvös Loránd en 1982 como Catedrático de Ciencia Computacional. En 1993 Lovász fue nombrado Profesor William K. Lanman de Ciencia Computacional y Matemáticas en la Universidad de Yale. En 1999 fue nombrado investigador jefe en Microsoft, y en 2006 regresó a la Universidad Eötvös Loránd, donde es profesor en la actualidad.

De 2007 a 2010 fue presidente de la Unión Matemática Internacional. Entre sus numerosos galardones destacan el Premio Wolf 1999, el Premio Knuth 1999, el Premio Gödel 2001 y el Premio Kyoto 2010.

Avi Wigderson

Wigderson (Haifa, Israel, 1956) es miembro del Instituto de Estudios Avanzados de Princeton (EE UU). Graduado en Ciencias de la Computación por el Instituto Tecnológico de Israel, realizó su tesis doctoral sobre la complejidad combinatoria en Princeton. En 1986 Wigderson regresó a Israel para ocupar un puesto en la Universidad Hebrea de Jerusalén, donde se convirtió en catedrático en 1991. En 1999 Wigderson se incorporó al Instituto de Estudios Avanzados de Princeton, donde ha permanecido desde entonces.

En 1994, obtuvo el Premio Rolf Nevanlinna de ciencia computacional. Entre sus muchos otros galardones se encuentran el Premio Gödel 2009 y el Premio Knuth 2019.

Acerca del Premio Abel

El Premio Abel está financiado por el gobierno noruego y dotado con 7,5 millones de coronas noruegas (unos 750 000 euros). Conmemora, con su nombre, la figura del célebre matemático noruego Niels Henrik Abel (1802-1829).

Más información: www.abelprize.no