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