За что присуждена премия Тьюринга 2023 года

Премия Тьюринга 2023 года присуждена Ави Вигдерсону, математику, обнаружившему странную связь между вычислениями и случайностью.

10 апреля 2024 года Вигдерсон объявлен лауреатом Премии А.М. Тьюринга Ассоциации вычислительной техники (ACM), которую часто называют "Нобелевской премией в области вычислительной техники".

"Вигдерсон - выдающаяся интеллектуальная сила в теоретической информатике. Эта дисциплина привлекает  многообещающих молодых исследователей для работы над самыми сложными задачами, - сказал в заявлении Яннис Иоаннидис, президент ACM. - Премия Тьюринга этого года присуждается за конкретную работу Вигдерсона в области случайности, а также за косвенное, но существенное влияние, которое он оказал на всю область теоретической информатики".

Компьютерные алгоритмы по своей природе детерминированы, что позволяет делать прогнозы, но также ограничивает понимание беспорядочной случайности, встречающейся в реальном мире. На самом деле, многие задачи считаются вычислительно “сложными”, потому что детерминированным алгоритмам трудно решать их эффективно.

Но Вигдерсон и его коллега Ричард Карп, специалист по информатике из Калифорнийского университета в Беркли, нашли способ снизить сложность вычислений. Они обнаружили, что добавление случайности в алгоритмы улучшило их способность решать недетерминированные задачи.

"С самых первых дней информатики исследователи признавали, что включение случайности давало возможность создания более быстрых алгоритмов для широкого спектра приложений. Вигдерсон открыл новые горизонты в этой области ", - сказал в своем заявлении Джефф Дин, главный научный сотрудник Google Research и Google DeepMind.