Alistair Sinclair (nacido en 1960) es un británico experto en informática y teórico computacional .
Sinclair recibió su licenciatura en matemáticas de St. John's College, Cambridge en 1979, y su Ph.D. 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 en la Universidad de California, Berkeley y ha ocupado cargos docentes en la Universidad de Edimburgo y puestos de visitante 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 el cálculo del 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 aleatoria en tiempo completamente 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 grafos cerrados menores.
Referencias
- ^ John, Sinclair, Alistair (1988). "Algoritmos aleatorios para contar y generar estructuras combinatorias". hdl : 1842/11392 . Cite journal requiere
|journal=
( ayuda ) - ^ "Cita del Premio Gödel 1996" . Archivado desde el original el 2 de abril de 2015 . Consultado el 14 de diciembre de 2011 .
- ^ Cita del premio Fulkerson 2006 , Avisos de la AMS, diciembre de 2006, volumen 53, número 11
- Complejidad computacional del "Premio Fulkerson" . Consultado el 11 de abril de 2017.