Ученый-компьютерщик Ави Вигдерсон известен тем, что прояснил роль случайности в алгоритмах и изучил их сложность. Лидер в области вычислительной теории является последним лауреатом премии А. М. Тьюринга, которую иногда называют «Нобелевской премией» в области компьютерных наук, сообщает «nature».
Он получил премию Тьюринга «за фундаментальный вклад в теорию вычислений, в том числе за изменение нашего понимания роли случайности в вычислениях, и за десятилетия интеллектуального лидерства в теоретической информатике», объявила 10 апреля Ассоциация вычислительной техники (ACM) в Нью-Йорке.
Вигдерсон родился в Хайфе, Израиль, в 1956 году. Учился в Технионе — Израильском технологическом институте в Хайфе, а затем в Принстонском университете.
Он известен своими работами по вычислительной сложности, которые изучают, как определенные задачи по своей природе медленно решаются, даже в принципе, и по случайности в вычислениях. Многие практические алгоритмы делают случайный выбор для более эффективного достижения своих целей. В серии новаторских исследований 1990-х годов Вигдерсон и его коллеги показали, что обычные, детерминированные алгоритмы в принципе могут быть примерно такими же эффективными, как и «рандомизированные».
Полученные результаты помогли подтвердить, что случайные алгоритмы могут быть такими же точными, как и детерминированные.
Премия Тьюринга названа в честь знаменитого британского математика и дешифровщика Алана Тьюринга (1912–1954), который в 1930-х годах заложил концептуальные основы современной вычислительной техники. «Я чувствую себя как дома с математикой», — говорит Вигдерсон, добавляя, что теоретическая информатика как интеллектуальная задача неотличима от математики. «Мы доказываем теоремы, как математики».
