Y el Premio Turing de este año es para...

Abstract

Una exposición del trabajo que le valió a Avi Wigderson el Premio A.M. Turing de la ACM de 2023, en concreto el marco «dificultad frente a aleatoriedad» que desarrolló junto con Nisan y otros. El vídeo muestra cómo, si existen problemas naturalmente difíciles, cualquier algoritmo aleatorio eficiente puede, en principio, sustituirse por uno determinista eficiente, lo que redefine nuestra comprensión del papel de la aleatoriedad en la computación.