Michael Fredric Sipser (nacido el 17 de septiembre de 1954) es un científico informático teórico estadounidense que realizó contribuciones tempranas a la teoría de la complejidad computacional . Es profesor de matemáticas aplicadas y fue decano de ciencias en el Instituto Tecnológico de Massachusetts .
Sipser nació y creció en Brooklyn, Nueva York, y se mudó a Oswego, Nueva York, cuando tenía 12 años. Obtuvo su licenciatura en matemáticas en la Universidad de Cornell en 1974 y su doctorado en ingeniería en la Universidad de California en Berkeley en 1980 bajo la dirección de Manuel Blum . [1] [2]
Se unió al Laboratorio de Ciencias de la Computación del MIT como investigador asociado en 1979 y luego fue miembro del personal de investigación en IBM Research en San José. En 1980, se unió a la facultad del MIT. Pasó el año académico 1985-1986 en la facultad de la Universidad de California en Berkeley y luego regresó al MIT. Desde 2004 hasta 2014, se desempeñó como jefe del departamento de Matemáticas del MIT. Fue nombrado decano interino de la Escuela de Ciencias del MIT en 2013 y decano en 2014. [3] Se desempeñó como decano hasta 2020, cuando fue sucedido por Nergis Mavalvala . [4] Es miembro de la Academia Estadounidense de Artes y Ciencias. [5] En 2015 fue elegido miembro de la Sociedad Matemática Estadounidense "por contribuciones a la teoría de la complejidad y por liderazgo y servicio a la comunidad matemática". [6] Fue elegido miembro del ACM en 2017. [7]
Sipser se especializa en algoritmos y teoría de la complejidad , específicamente en códigos de corrección de errores eficientes, sistemas de prueba interactivos, aleatoriedad, computación cuántica y en el establecimiento de la dificultad computacional inherente de los problemas. Introdujo el método de restricción probabilística para probar límites inferiores superpolinómicos en la complejidad de los circuitos en un artículo conjunto con Merrick Furst y James B. Saxe . [8] Su resultado fue mejorado posteriormente para ser un límite inferior exponencial por Andrew Yao y Johan Håstad . [9]
En un teorema de desaleatorización temprano , Sipser demostró que BPP está contenido en la jerarquía polinómica , [10] posteriormente mejorado por Peter Gács y Clemens Lautemann para formar lo que ahora se conoce como el teorema de Sipser-Gács-Lautemann . Sipser también estableció una conexión entre los grafos expansores y la desaleatorización. [11] Él y su estudiante de doctorado Daniel Spielman introdujeron los códigos expansores , una aplicación de los grafos expansores. [12] Con su compañero de posgrado David Lichtenstein, Sipser demostró que Go es PSPACE difícil. [13]
En la teoría de la computación cuántica, introdujo el algoritmo adiabático junto con Edward Farhi , Jeffrey Goldstone y Samuel Gutmann. [14]
Sipser lleva mucho tiempo interesado en el problema P versus NP . En 1975, apostó una onza de oro con Leonard Adleman a que el problema se resolvería con una prueba de que P≠NP a finales del siglo XX. Sipser le envió a Adleman una moneda de oro estadounidense en 2000 porque el problema seguía (y sigue) sin resolverse. [15]
Sipser es el autor de Introducción a la teoría de la computación , [16] un libro de texto sobre informática teórica .
Sipser vive en Cambridge, Massachusetts, con su esposa, Ina, y tiene dos hijos: una hija, Rachel, que se graduó de la Universidad de Nueva York, y un hijo menor, Aaron, que se graduó del MIT. [1]