Войти
Алистер Синклер (родился в 1960 г.), британский ученый-компьютерщик и теоретик вычислений.
Синклер получил степень бакалавра по математике от Св. John’s College, Кембридж в 1979 году, и его докторская степень. получил степень бакалавра компьютерных наук в Эдинбургском университете в 1988 году под руководством Марка Джеррама. Он является профессором отделения компьютерных наук в Калифорнийском университете в Беркли и работал на факультете должности в Эдинбургском университете и должности в DIMACS и Международном институте компьютерных наук в Беркли.
Научные интересы Синклера включают разработку и анализ рандомизированных алгоритмов, вычислительные приложения случайных процессов и нелинейных динамических систем, методы Монте-Карло в статистической физике и комбинаторная оптимизация. Вместе со своим советником Марком Джеррамом Синклер исследовал смешивающее поведение цепей Маркова, чтобы построить алгоритмы аппроксимации для задач подсчета, таких как вычисление перманента, с приложениями в различных областях, таких как алгоритмы сопоставления, геометрические алгоритмы, математическое программирование, статистика, приложения на основе физики и динамические системы. Эта работа оказала большое влияние на теоретическую информатику и была отмечена премией Гёделя в 1996 году. Уточнение этих методов привело к полностью полиномиальному алгоритму рандомизированной аппроксимации по времени для вычисления перманента, для которого Синклер и его соавторы получили Премию Фулкерсона в 2006 году.
Первоначальный текст Синклера является частью названия гипотезы GNRS о метрических вложениях семейств минно-замкнутых графов.
.
