Avi Wigderson
Więcej informacji
- Afiliacja
- Institute for Advanced Study, Princeton
- Znany z
- dowodów z wiedzą zerową dla NP, protokołu GMW, derandomizacji
Izraelski teoretyk złożoności, który wykazał, że każde zdanie z klasy NP można udowodnić, nie ujawniając niczego więcej, laureat Nagrody Turinga za rok 2023.
W 1986 roku Wigderson wraz z Odedem Goldreichem i Silviem Micalim pokazał, że dowody z wiedzą zerową istnieją dla każdego problemu z klasy NP, a nie tylko dla kilku starannie wybranych. W następnym roku powstał protokół GMW: ogólny sposób, by kilka stron wspólnie obliczyło funkcję, nie pokazując sobie nawzajem swoich danych. Razem z Ben-Orem i Shafi Goldwasser podał w 1988 roku wersję informacyjnie teoretyczną.
Większość jego prac dotyczy jednak roli losowości w obliczeniach — kiedy jest potrzebna, a kiedy można ją zastąpić konstrukcjami deterministycznymi. Ten nurt przyniósł mu Nagrodę Abela w 2021 roku, dzieloną z Lászlóm Lovászem, oraz Nagrodę Turinga, w której uzasadnieniu kryptografia figurowała wśród kilku zastosowań.