Вэлиант, Лесли

В 1967—1970 годах учился в Королевском колледже Кембриджа, где получил степень бакалавра математики, а в 1970—1971 годах — в Имперском колледже Лондона, получив диплом по вычислительной науке^[4]. Затем окончил Уорикский университет, в котором получил степень доктора философии по информатике в 1974 году. В 1973—1974 годах был приглашённым ассистент-профессором в университете Карнеги — Меллон, в 1974—1976 годах — лектором в Лидском университете, а в 1977—1982 годах — лектором, затем ридером в Эдинбургском университете^[4]. В 1982 году начал преподавать в Гарвардском университете, где по состоянию на сентябрь 2026 года занимает должность профессора компьютерных наук и прикладной математики имени Т. Джефферсона Кулиджа в Школе инженерии и прикладных наук^[5].

Занимается исследованиями в области теоретической информатики. Среди работ — важный вклад в теорию сложности вычислений: введение класса сложности #P для задач подсчёта числа решений^[6]. В области машинного обучения разработал теорию приближенно правильного обучения (англ. Probably Approximately Correct Learning, PAC), получившую широкое практическое распространение. Также работал в областях параллельных и распределённых вычислений, голографических алгоритмов.

В статье «A Bridging Model for Parallel Computation» (1990) Вэлиант предложил модель массово-синхронных параллельных вычислений (BSP), связывающую параллельные алгоритмы с аппаратным обеспечением. Вычисление в ней разделяется на супершаги, каждый из которых включает локальные вычисления, обмен данными и барьерную синхронизацию.

В книге «Circuits of the Mind» (1994) Вэлиант предложил нейроидальную модель — вычислительную схему для описания памяти, обучения и рассуждения с учётом ограничений нейронных связей^[7]. В исследованиях нейронных вычислений он также адаптировал идеи PAC-обучения для оценки количественных ограничений таких систем^[6].

Теорема Вэлианта — Вазирани утверждает, что любую задачу из класса NP можно за рандомизированное полиномиальное время свести к задаче с не более чем одним решением; тем самым трудность NP-задач сохраняется и в случае уникального свидетеля, изучаемом в рамках класса UP^[8].

В книге «The Importance of Being Educable» (2024) Вэлиант предложил концепцию обучаемости (англ. educability) как способности приобретать системы убеждений из собственного опыта и от других людей, а затем интегрировать и применять их в новых ситуациях. Концепция объединяет обучение на примерах, усвоение инструкций и интегративное применение знаний; в отличие от неё, современное машинное обучение реализует прежде всего обучение на примерах^[9].

• The Importance of Being Educable: A New Theory of Human Uniqueness. — Princeton University Press, 2024. — 272 p. — ISBN 978-0-691-23056-6^[10].

• 1985 — Стипендия Гуггенхайма
• 1986 — Премия Неванлинны.
• 1997 — Премия Кнута.
• 2008 — Премия Европейской ассоциации теоретической информатики.
• 2010 — Премия Тьюринга «за вклад в теорию алгоритмов, включая приближенно правильное обучение^[en], теорию сложности перечисления и алгебраических исчислений, а также теорию параллельных и распределённых вычислений»^[11].
• 2012 — почётный доктор Высшей нормальной школы Лиона^[12].
• 2013 — почётный доктор наук Уорикского университета^[12].
• 2013 — почётный доктор математики Университета Уотерлу^[12].
• 2018 — почётный доктор инженерных наук Лидского университета^[12].