Premio Turing 2023: Avi Wigderson gana el premio de informática por aprovechar la aleatoriedad

el matemático Avi Wigderson ha ganado el premio Turing 2023, a menudo denominado el premio Nobel de informática, por su trabajo para comprender cómo la aleatoriedad puede dar forma y mejorar los algoritmos informáticos.

Wigderson, quien también ganó el prestigioso premio abel en 2021 por sus contribuciones matemáticas a la informática, quedó desconcertado por el premio. «El [Turing] El comité me engañó haciéndome creer que íbamos a tener una conversación sobre la colaboración”, dice. “Cuando me acerqué, todo el comité estaba allí y me lo dijeron. Estaba emocionado, sorprendido y feliz”.

Las computadoras funcionan en un manera predecible a nivel de hardware, pero esto puede dificultarles el modelado de problemas del mundo real, que a menudo tienen elementos de aleatoriedad e imprevisibilidad. Wigderson, del Instituto de Estudios Avanzados de Princeton, Nueva Jersey, ha demostrado a lo largo de décadas de carrera que las computadoras también pueden aprovechar la aleatoriedad en los algoritmos que ejecutan.

En la década de 1980, Wigderson y sus colegas descubrieron que al insertar aleatoriedad en algunos algoritmos, podían hacerlos más fáciles y rápidos de resolver, pero no estaba claro cuán general era esta técnica. «Nos preguntábamos si esta aleatoriedad es esencial, o tal vez siempre puedas deshacerte de ella de alguna manera si eres lo suficientemente inteligente», dice.

Uno de los descubrimientos más importantes de Wigderson fue dejar clara la relación entre los tipos de problemas, en términos de su dificultad para resolverlos, y la aleatoriedad. También demostró que ciertos algoritmos que contenían aleatoriedad y eran difíciles de ejecutar podían volverse deterministas, o no aleatorios, y más fáciles de ejecutar.

Estos hallazgos ayudaron a los científicos informáticos a comprender mejor una de las conjeturas no probadas más famosas de la informática, llamada «P ≠ NP”, que propone que los problemas fáciles y difíciles de resolver para una computadora son fundamentalmente diferentes. Utilizando la aleatoriedad, Wigderson descubrió casos especiales en los que las dos clases de problemas eran iguales.

Wigderson comenzó a explorar la relación entre la aleatoriedad y las computadoras en la década de 1980, antes de que existiera Internet, y se sintió atraído por las ideas en las que trabajó por curiosidad intelectual, más que por cómo podrían usarse. «Soy una persona muy poco práctica», dice. «Realmente no me motivan las solicitudes».

Sin embargo, sus ideas se han vuelto importantes para una amplia gama de aplicaciones informáticas modernas, desde la criptografía hasta la computación en la nube. «El impacto de Avi en la teoría de la computación en los últimos 40 años es insuperable», dice Oded Goldreich en el Instituto Weizmann de Ciencias en Israel. «La diversidad de las áreas en las que ha contribuido es sorprendente».

Una de las formas inesperadas en que las ideas de Wigderson se utilizan ahora ampliamente fue su trabajo, con Goldreich y otros, sobre pruebas de conocimiento cero, que detallan formas de verificar información sin revelar la información en sí. Estos métodos son fundamentales para CRIPTOMONEDAS y cadenas de bloques hoy como una forma de establecer confianza entre diferentes usuarios.

Aunque se han logrado grandes avances en la teoría de la computación a lo largo de su carrera, Wigderson dice que el campo todavía está lleno de problemas interesantes y sin resolver. “No te puedes imaginar lo feliz que estoy de estar donde estoy, en el campo en el que estoy”, dice. «Está lleno de preguntas intelectuales».

Wigderson recibirá un premio de 1 millón de dólares como parte del premio Turing.