Premio ACM Turing 2023 otorgado al profesor Avi Wigderson

 (awards.acm.org)
1 puntos por GN⁺ 2024-04-12 | 1 comentarios | Compartir por WhatsApp
  • ACM eligió a Avi Wigderson como ganador del ACM A.M. Turing Award 2023, en reconocimiento a sus aportes que renovaron la comprensión de la teoría de la computación y del papel de la aleatoriedad en el cómputo
  • Wigderson es Herbert H. Maass Professor en el Institute for Advanced Study, y una figura que ha liderado ampliamente la teoría de la complejidad computacional, los algoritmos, la criptografía, la computación paralela y distribuida, la combinatoria y la teoría de grafos
  • Su aporte central es la investigación en hardness for randomness, que mostró que, bajo supuestos computacionales ampliamente aceptados, los algoritmos probabilísticos de tiempo polinomial pueden simularse de manera determinista
  • Sus trabajos relacionados presentaron generadores seudoaleatorios, simulaciones en tiempo subexponencial de BPP y compromisos hardness-vs-randomness, e influyeron en varias áreas de la informática teórica
  • El Turing Award entrega un premio de 1 millón de dólares con apoyo de Google, y Wigderson es valorado no solo por sus logros técnicos, sino también como mentor que guió a jóvenes investigadores

Contexto del ACM Turing Award

  • ACM eligió a Avi Wigderson como ganador del ACM A.M. Turing Award 2023
  • Las razones del premio son sus contribuciones fundamentales a la teoría de la computación, sus logros al replantear la comprensión del papel de la aleatoriedad en el cómputo y su liderazgo intelectual durante décadas en la informática teórica
  • Wigderson es Herbert H. Maass Professor en el Departamento de Matemáticas del Institute for Advanced Study, en Princeton, Nueva Jersey

  • Principales áreas de actividad

    • Teoría de la complejidad computacional
    • Algoritmos y optimización
    • Aleatoriedad y criptografía
    • Computación paralela y distribuida
    • Combinatoria y teoría de grafos
    • Conexiones entre la informática teórica y las matemáticas y la ciencia
    • El ACM A.M. Turing Award es conocido como el “Premio Nobel de la computación” y, con el apoyo financiero de Google, Inc., entrega un premio de 1 millón de dólares
    • El premio lleva el nombre del matemático británico Alan M. Turing, quien sentó las bases matemáticas de la computación

Preguntas que aborda la informática teórica

  • La informática teórica trata los fundamentos matemáticos de la informática y aborda preguntas como “¿este problema puede resolverse mediante cómputo?” y “si puede resolverse, ¿cuánto tiempo y cuántos recursos se necesitan?”
  • Este campo también explora los principios para diseñar algoritmos eficientes
  • Los algoritmos son la base que hace posibles las tecnologías de cómputo usadas en la vida diaria
  • La informática teórica también aborda desafíos intelectuales que no mejoran de inmediato las aplicaciones prácticas, pero sus avances de investigación pueden impulsar el desarrollo de múltiples áreas
    • Criptografía
    • Biología computacional
    • Diseño de redes
    • Aprendizaje automático
    • Computación cuántica

Por qué la aleatoriedad es importante en el cómputo

  • Las computadoras son, en esencia, sistemas deterministas, y para una entrada dada el conjunto de instrucciones de un algoritmo determina de manera única el cálculo y la salida
  • La aleatoriedad se refiere a la ausencia de un patrón claro o de previsibilidad en eventos o resultados
  • En el mundo real hay muchos eventos que parecen aleatorios, como los sistemas meteorológicos, los fenómenos biológicos y los fenómenos cuánticos
  • Para aumentar la eficiencia, los científicos de la computación han ampliado los algoritmos para que tomen decisiones aleatorias durante el proceso de cómputo
  • Muchos problemas para los que no se conocían algoritmos deterministas eficientes también pueden resolverse de forma eficiente con algoritmos probabilísticos que tienen una pequeña probabilidad de error
    • Esa probabilidad de error puede reducirse de manera eficiente
  • La pregunta central es si la aleatoriedad es indispensable, si puede eliminarse y cuál es la calidad de la aleatoriedad necesaria para el éxito de los algoritmos probabilísticos
  • Comprender mejor el comportamiento de la aleatoriedad y la seudoaleatoriedad en el cómputo puede llevar al desarrollo de mejores algoritmos y a una mejor comprensión de la naturaleza misma del cómputo

Principales aportes de investigación de Wigderson

  • Wigderson ha liderado durante 40 años la investigación en informática teórica y realizó aportes fundamentales para comprender el papel de la aleatoriedad y la seudoaleatoriedad en el cómputo
  • Los científicos de la computación descubrieron una conexión importante entre la aleatoriedad y la dificultad computacional, es decir, la identificación de problemas naturales para los que no existen algoritmos eficientes
  • Wigderson y sus coautores publicaron investigaciones influyentes sobre hardness for randomness
  • Estos trabajos mostraron que, bajo supuestos computacionales estándar y ampliamente aceptados, todos los algoritmos probabilísticos de tiempo polinomial pueden derandomizarse de manera eficiente
  • Este resultado muestra que la aleatoriedad podría no ser estrictamente necesaria para el cómputo eficiente
  • Esa línea de investigación cambió el papel de la aleatoriedad en el cómputo y la forma de pensar sobre ella

  • Tres artículos representativos

Alcance de su impacto y aportes adicionales

  • Los tres artículos de Wigderson influyeron en varias áreas de la informática teórica más allá de la aleatoriedad y la derandomización
  • Las ideas de estos artículos fueron usadas después en trabajos influyentes de varios investigadores destacados
  • En un artículo con Omer Reingold, Salil Vadhan y Michael Capalbo, presentó la primera construcción combinatoria eficiente de un expander graph
    • Un expander graph es un grafo disperso con fuertes propiedades de conectividad
    • Tiene aplicaciones importantes tanto en matemáticas como en informática teórica
  • Además de la aleatoriedad, Wigderson mostró liderazgo intelectual en los siguientes campos
    • multi-prover interactive proofs
    • Criptografía
    • Complejidad de circuitos

Mentoría y evaluación

  • Wigderson es reconocido no solo por sus contribuciones técnicas revolucionarias, sino también como un mentor y colega respetado que guió a muchos jóvenes investigadores
  • Su vasto conocimiento, capacidad técnica, cercanía, entusiasmo y generosidad se consideran factores que impulsaron a jóvenes investigadores destacados a seguir carreras en informática teórica
  • El presidente de ACM, Yannis Ioannidis, señaló que Wigderson también recibió el Abel Prize, considerado uno de los máximos honores a la trayectoria en el campo de las matemáticas
  • Ioannidis evaluó que las matemáticas son la base de la informática y que el trabajo de Wigderson conectó diversas subáreas de las matemáticas con la informática teórica
  • Jeff Dean, Senior Vice President de Google, afirmó que la investigación de Wigderson sobre aleatoriedad y otros temas marcó la agenda de la informática teórica durante los últimos 30 años
  • Dean también destacó que Wigderson fue un mentor que generó ideas y direcciones de investigación, y motivó a jóvenes investigadores a trabajar en esas direcciones

Turing Award y otros artículos importantes de Wigderson

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-04-12
Opiniones en Hacker News

  • Los dos artículos principales de Wigderson mencionados en el anuncio fueron escritos en coautoría con Noam Nisan, uno de los profesores que creó el conocido curso en línea From Nand to Tetris

    • El profesor Nisan también es una figura impresionante. Después de lograr resultados de primer nivel en teoría de la computación, también dejó una gran huella en un campo bastante distinto: la teoría algorítmica de juegos
      Me gusta que una sola persona pueda conseguir logros tan variados, y también es notable el sistema que permitió esa flexibilidad
    • También hay un libro. Hace poco salió la segunda edición

  • También hay un buen artículo de Quanta: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Me dio risa la variedad de poses que le hicieron hacer a Wigderson. Se ve demasiado incómodo. Algo como: “Bueno, siéntese en esta silla y mire pensativo por la ventana”

    • Me pareció interesante la parte donde “la irrazonable efectividad de la aleatoriedad” llevó a Wigderson a pensar en la naturaleza misma de la aleatoriedad
      Entiendo que las clases de complejidad tratan sobre el rendimiento en el peor caso, pero me gustaría saber, a grandes rasgos, cómo se demuestra que, aun teniendo un buen generador de números pseudoaleatorios y buenos algoritmos aleatorizados, ninguna combinación de RNG + seed + problem instance requiere tiempo exponencial
    • Según la corrección, el artículo original decía que Wigderson había asistido a la University of Haifa, pero en realidad se graduó del Technion en Haifa, Israel
      Me pregunto cómo se confundió el periodista con eso
    • La pose de “sentado en una silla mirando por la ventana” parece una pose al estilo Martin Scorsese o Sopranos. Es como una escena de un viejo gánster en un asilo

  • Scott Aaronson escribió sobre cómo una conferencia de Avi Wigderson influyó en su propia trayectoria: https://scottaaronson.blog/?p=2925

  • Hay más información en “Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness”: [1] y copia archivada [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Me pregunto por dónde conviene empezar para ponerse al día con la parte de la investigación de Wigderson sobre el intercambio entre dificultad y aleatoriedad
    No es muy común que nunca haya oído hablar de un ganador del premio Turing, pero esta persona estaba completamente fuera de mi radar

    • Puedes leer su libro: https://www.math.ias.edu/avi/book
    • Me pregunto cuáles son esas “suposiciones computacionales estándar y ampliamente aceptadas”
      Supongo que quizá significa que ni siquiera la aproximación probabilística de problemas NP-completos puede hacerse en tiempo polinomial, o tal vez que la versión sin aleatoriedad sigue siendo un algoritmo de aproximación; me confunde

  • Acabo de tomar el libro de Wigderson y hasta ahora me gusta: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • Para investigación personal y fines educativos, se puede ver el borrador final del libro aquí: https://www.math.ias.edu/avi/book
    • Lo estuve viendo y parece más adecuado para estudiantes de posgrado o alumnos avanzados de licenciatura
      Me pregunto si alguien puede recomendar un libro que trate los temas de computación de forma más básica para alguien cuya formación de pregrado en ciencias de la computación/matemáticas está algo oxidada

  • En un artículo relacionado aparece esta frase: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    “Si una proposición es demostrable, entonces también tiene una prueba de conocimiento cero”; siento que me explota la cabeza
    También es absurdamente sorprendente eso de que “si en un algoritmo probabilístico se sustituyen bits aleatorios por bits pseudoaleatorios, se obtiene un algoritmo determinista eficiente para el mismo problema”
    Como la IA también es cómputo probabilístico, si lo estoy leyendo bien, ¿no significaría que se podría reducir la complejidad de los modelos actuales en varios órdenes de magnitud? Si es una confusión de principiante, agradecería que alguien me sacara de ella

    • No sé exactamente qué quiere decir, pero al menos no significa eso. La IA ya usa pseudoaleatoriedad y es determinista
      Hay excepciones, como algunos chips aceleradores de IA poco comunes que usan computación analógica para mejorar la eficiencia
    • Lamentablemente, no. Primero, ese resultado se aplica a problemas de decisión, no a problemas de búsqueda
      Segundo, el algoritmo determinista que se obtiene es mucho menos eficiente que el algoritmo aleatorizado. Solo que, bajo supuestos débiles, pertenece a la misma clase de complejidad

  • Me gustó esta parte del artículo: “Las aplicaciones no son la motivación, pero sé que incluso la investigación básica puede encontrar usos. Piensen en Alan Turing. Escribió un artículo matemático de lógica sobre el Entscheidungsproblem en una revista poco conocida. Las aplicaciones no eran la motivación”
    Es parecido a la anécdota del plato de Feynman. Empezó con una reacción casual a algo que vio en la cafetería de la universidad y terminó llevándolo al premio Nobel
    Ampliando la idea, la academia moderna se está moviendo justo hacia la dirección de reprimir este tipo de exploración impulsada por la curiosidad

  • Según la ACM, Avi Wigderson fue elegido ganador del ACM A.M. Turing Award 2023 por sus contribuciones fundamentales a la teoría de la computación, incluida la reformulación de nuestra comprensión del papel de la aleatoriedad en la computación, y por décadas de liderazgo intelectual en la informática teórica
    Wigderson es Herbert H. Maass Professor en la School of Mathematics del Institute for Advanced Study en Princeton, Nueva Jersey, y ha sido una figura clave en teoría de la complejidad computacional, algoritmos y optimización, aleatoriedad y criptografía, computación paralela y distribuida, combinatoria, teoría de grafos, y las conexiones entre la informática teórica y las matemáticas y la ciencia
    En 2021 también recibió el premio Abel, una combinación bastante singular de los máximos honores en matemáticas teóricas/abstractas y ciencias de la computación

    • La superposición entre la informática teórica y las matemáticas es mucho mayor de lo que la mayoría cree
      Como ejemplo simple, si se mira la lista de materias de informática teórica del MIT https://catalog.mit.edu/subjects/6/, se puede ver cuántas materias están cruzadas con course 18, que es matemáticas
    • Estrictamente hablando, el máximo honor en matemáticas es la Fields Medal
      Aunque claro, no soy quién para decirlo

  • Me gustaría recibir recomendaciones de recursos para estudiar probabilidad/aleatoriedad y computación, desde materiales amigables para principiantes hasta avanzados
    En Google aparece “Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis” de Eli Upfal y Michael Mitzenmacher, pero no logro encontrar buenos libros, textos o videos para principiantes/introductorios