Alistair Sinclair (nacido en 1960) es un científico informático y teórico computacional británico .
Sinclair recibió su licenciatura en matemáticas del St. John's College, Cambridge en 1979, y su doctorado en ciencias de la computación de la Universidad de Edimburgo en 1988 bajo la supervisión de Mark Jerrum . [1] Es profesor en la división de Ciencias de la Computación de la Universidad de California, Berkeley y ha ocupado puestos de profesor en la Universidad de Edimburgo y puestos de visita en DIMACS y el Instituto Internacional de Ciencias de la Computación en Berkeley.
Los intereses de investigación de Sinclair incluyen el diseño y análisis de algoritmos aleatorios , aplicaciones computacionales de procesos estocásticos y sistemas dinámicos no lineales, métodos de Monte Carlo en física estadística y optimización combinatoria . Con su asesor Mark Jerrum , Sinclair investigó el comportamiento de mezcla de cadenas de Markov para construir algoritmos de aproximación para problemas de conteo como el cálculo de la permanente , con aplicaciones en diversos campos como algoritmos de emparejamiento, algoritmos geométricos, programación matemática, estadística, aplicaciones inspiradas en la física y sistemas dinámicos. Este trabajo ha sido muy influyente en la informática teórica y fue reconocido con el Premio Gödel en 1996. [2] Un refinamiento de estos métodos condujo a un algoritmo de aproximación aleatorio de tiempo completamente polinomial para calcular la permanente, por el que Sinclair y sus coautores recibieron el Premio Fulkerson en 2006. [3]
Las iniciales de Sinclair forman parte del nombre de la conjetura GNRS sobre incrustaciones métricas de familias de gráficos menores cerrados.