Alistair Sinclair (nacido en 1960) es un informático y teórico computacional británico .
Sinclair recibió su licenciatura en matemáticas en St. John's College, Cambridge en 1979, y su doctorado. en informática 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 cargos docentes en la Universidad de Edimburgo y puestos visitantes 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 las cadenas de Markov para construir algoritmos de aproximación para problemas de conteo como la computación de lo permanente , con aplicaciones en diversos campos como algoritmos de emparejamiento, algoritmos geométricos, programación matemática, estadística y 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 aleatoria en tiempo totalmente polinomial para calcular lo permanente, para el cual Sinclair y sus coautores recibió el Premio Fulkerson en 2006. [3]
La inicial de Sinclair forma parte del nombre de la conjetura de GNRS sobre incrustaciones métricas de familias de gráficos menores cerrados.
{{cite journal}}: Citar diario requiere |journal=( ayuda )Mantenimiento CS1: varios nombres: lista de autores ( enlace )