Algoritmes aleatoritzats (Avi Wigderson, Premi Turing 2023)

Matemàtiques: El mes passat l’Association for Computing Machinery anunciava la concessió del 2023 ACM A.M. Turing Award a Avi Wigderson «per contribucions fonamentals a la teoria de la computació, incloent la transformació de la nostra comprensió del rol de l’aleatorietat en computació i matemàtic, i per dècades de lideratge intel·lectual en la ciència computacional teòrica». El premi va dotat amb un milió de US$.

Duresa i aleatorietat

Nisan & Wigderson (1994) introduïren un nou tipus de generador pseudoaleatori, i demostraren que una simulació determinista eficient d’algoritmes aleatoritzats és possible.

Temps polinomial probabilístic d’error limitat

Babai et al. (1993) empraren l’amplificació de duresa per demostrar que el temps polinominal probabilístic d’error limitat es pot simular en un temps subexponencial per a un nombre infinit de longituds.

Un generador pseudoaleatori més fort

Impagliazzo & Wigderson (1997) introduïren un generador pseudoaleatori amb un balanç essencialment òptim entre duresa i aleatorietat.

Avi Wigderson avui

Avi Wigderson ocupa la plaça Herbert H. Maass de professor a la School of Mathematics de l’Institute for Advanced Study de Princeton. Entre el 1982 i el 2023 ha participat en 247 publicacions, que han estat citades en 11.340 ocasions i descarregats 71.729 vegades. El seu tema principal ha estat la complexitat computacional i la criptografia, i darrerament l’anàlisi de funció booleà.

Lligams:

- La matemàtica discreta en la informàtica teòrica (László Lovász i Avi Wigderson, Premi Abel 2021)

- BPP has subexponential time simulations unlessEXPTIME has publishable proofs. László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson. Computational Complexity 3: 307-318 (1993).

- Hardness vs randomness. Noam Nisan, Avi Wigderson. Journal of Computer and System Sciences 49: 149-167 (1994)

- P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. Russell Impagliazzo, Avi Wigderson. Proceedings of the twenty-ninth anual ACM symposium on Theory of computing. 220-229 (1997).