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

Лесли Гэбриел Вэлиант

англ. Leslie Gabriel Valiant

Дата рождения

28 марта 1949 года

Место рождения

Будапешт, Венгрия

Научная сфера

Информатика

Известен как

учёный в области теоретической информатики. Теорема Вэлианта — Вазирани.

Лесли Вэлиант — деятель науки.

Ранние годы

Имеет еврейское происхождение.

Закончил Королевский колледж Кембриджа, Имперский колледж Лондона и Уорикский университет, где в 1974 получил степень доктора философии по информатике, защитив диссертацию по теме Decision Procedures for Families of Deterministic Pushdown Automata.

Карьера

Затем осуществлял педагогическую деятельность в вузах Карнеги — Меллон, Лида и Эдинбурга.

С 1982 преподаёт в Гарвардском университете, ныне занимает там пост профессора компьютерных наук и прикладной математики.

В 2010 удостоился престижной премии «Turing Award» со следующей формулировкой:

За вклад в теорию алгоритмов, включая приближенно правильное обучение, теорию сложности перечисления и алгебраических исчислений, а также теорию параллельных и распределённых вычислений

В 2013 выпустил книгу Probably Approximately Correct: Nature's Algorithms for Learning and Prospering in a Complex World.

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

Личная жизнь

О его семье известно следующее: два его сына, Грегори и Пол Валиант являются теоретиками компьютерных наук, преподавателями в Стэнфордском и Браунском вузах соответственно.

Труды

• Valiant, L.; Vazirani, V. (1986). "NP is as easy as detecting unique solutions". Theoretical Computer Science. 47: 85–93.
• Valiant, L. G. (1979). "The Complexity of Enumeration and Reliability Problems". SIAM Journal on Computing. 8 (3): 410.
• Valiant, Leslie (1984). "A theory of the learnable". Communications of the ACM. 27 (11): 1134–1142.
• Circuits of the mind. Oxford University Press, 1994, 2000.