И лауреатом премии Тьюринга в этом году становится...

Abstract

Изложение работы, за которую Ави Вигдерсон был удостоен премии ACM имени А. М. Тьюринга 2023 года, в частности концепции «сложность против случайности», разработанной им совместно с Нисаном и другими учёными. В видео показано, что при наличии естественных сложных задач каждый эффективный рандомизированный алгоритм в принципе может быть заменён эффективным детерминированным алгоритмом, что кардинально меняет наше понимание роли случайности в вычислениях.