Эндрю Яо

Эндрю Чи-Чих Яо получил докторскую степень по физике в Гарварде, затем ещё одну — по информатике и остановился на теории сложности. В 1979 году он основал коммуникационную сложность, а в 1982-м сформулировал задачу миллионеров: двум сторонам нужно вычислить функцию от своих секретных входов, не показывая их друг другу. Его ответ, запутанные схемы (garbled circuits), шифрует всю булеву схему вентиль за вентилем, так что её можно вычислить, не раскрывая ни одного промежуточного значения. Это стало стартом защищённых многосторонних вычислений, которые в 1987 году обобщили Голдрайх, Микали и Вигдерсон.

Премию Тьюринга он получил в 2000 году, в частности за теорию псевдослучайности на основе сложности. В 2004 году перешёл из Принстона в Университет Цинхуа в Пекине, где его элитная программа «класс Яо» подготовила заметную долю китайских специалистов по информатике. Он также внёс вклад в теорию схем квантовых вычислений.