Michael Fredric Sipser (nacido el 17 de septiembre de 1954) es un informático teórico estadounidense que ha realizado contribuciones tempranas a la teoría de la complejidad computacional . Es profesor de Matemáticas Aplicadas y fue Decano de Ciencias en el Instituto de Tecnología de Massachusetts .
Michael Sipser | |
---|---|
Nació | Michael Fredric Sipser 17 de septiembre de 1954 |
Nacionalidad | americano |
alma mater | |
Premios |
|
Carrera científica | |
Campos | |
Instituciones | MIT |
Tesis | El no determinismo y el tamaño de los autómatas finitos bidireccionales (1980) |
Asesor de doctorado | Manuel Blum |
Estudiantes de doctorado | |
Sitio web | matemáticas |
Biografía
Sipser nació y se crió en Brooklyn, Nueva York y se mudó a Oswego, Nueva York cuando tenía 12 años. Obtuvo su licenciatura en matemáticas de la Universidad de Cornell en 1974 y su doctorado en ingeniería de 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 incorporó 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 seguido por Nergis Mavalvala . [4] Es miembro de la Academia Estadounidense de Artes y Ciencias. [5] En 2015 fue elegido miembro de la American Mathematical Society "por sus contribuciones a la teoría de la complejidad y por su liderazgo y servicio a la comunidad matemática". [6] Fue elegido miembro de la ACM en 2017. [7]
Carrera científica
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 demostrar límites inferiores superpolinomiales en la complejidad del circuito en un documento conjunto con Merrick Furst y James B. Saxe . [8] Su resultado fue mejorado más tarde para ser un límite inferior exponencial por Andrew Yao y Johan Håstad . [9]
En un teorema de desaleatorización temprano , Sipser mostró que BPP está contenido en la jerarquía polinomial , [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 gráficos de expansión y la desaleatorización. [11] Él y su estudiante de doctorado Daniel Spielman introdujeron los códigos expansores , una aplicación de gráficos expansores. [12] Con su compañero estudiante 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 ha estado interesado durante mucho tiempo en el problema de 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 águila de oro estadounidense en 2000 porque el problema seguía (y sigue) sin resolverse. [15]
Libros notables
Sipser es el autor de Introducción a la teoría de la computación , [16] un libro de texto para la informática teórica .
Vida personal
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]
Referencias
- ^ a b Trafton, Anne, "Michael Sipser nombrado decano de la Escuela de Ciencias: Sipser se ha desempeñado como decano interino desde la partida de Marc Kastner" , Oficina de noticias del MIT, 5 de junio de 2014
- ^ Michael Sipser en el Proyecto de genealogía matemática
- ^ Matemáticas del MIT | Directorio de personas Archivado el 18 de diciembre de 2008 en la Wayback Machine.
- ^ "Escuela de Ciencias | Historia del MIT" . Consultado el 25 de agosto de 2020 .
- ^ "Membresía" . Academia Estadounidense de Artes y Ciencias . Consultado el 23 de septiembre de 2014 .
- ^ 2016 Class of the Fellows of the AMS , American Mathematical Society , consultado el 16 de noviembre de 2015.
- ^ ACM reconoce a los becarios de 2017 por realizar contribuciones transformadoras y promover la tecnología en la era digital , Association for Computing Machinery, 11 de diciembre de 2017 , consultado el 13 de noviembre de 2017
- ^ Furst, Merrick; Saxe, James B .; Sipser, Michael (1984). "Paridad, circuitos y jerarquía polinomial-temporal". Teoría de sistemas matemáticos . 17 (1): 13-27. doi : 10.1007 / BF01744431 . Señor 0738749 . S2CID 14677270 .
- ^ "Vignette de investigación: problemas difíciles hasta el final | Instituto Simons para la teoría de la computación" . simons.berkeley.edu . Consultado el 17 de septiembre de 2015 .
- ^ Sipser, Michael (1983). "Un enfoque teórico de la complejidad de la aleatoriedad". Actas del 15º Simposio ACM sobre Teoría de la Computación .
- ^ Sipser, Michael (1986). "Expansores, aleatoriedad o tiempo versus espacio". Actas de la Conferencia sobre Estructura en Complejidad . Apuntes de conferencias en Ciencias de la Computación. 223 : 325–329. doi : 10.1007 / 3-540-16486-3_108 . ISBN 978-3-540-16486-9.
- ^ Sipser, Michael; Spielman, Daniel (1996). "Códigos de expansión" (PDF) . Transacciones IEEE sobre teoría de la información . 42 (6): 1710-1722. doi : 10.1109 / 18.556667 .
- ^ Lichtenstein, David; Sipser, Michael (1 de abril de 1980). "GO es polinomial-espacio difícil". J. ACM . 27 (2): 393–401. doi : 10.1145 / 322186.322201 . ISSN 0004-5411 . S2CID 29498352 .
- ^ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam; Sipser, Michael (28 de enero de 2000). "Computación cuántica por evolución adiabática". arXiv : quant-ph / 0001106 .
- ^ Pavlus, John (1 de enero de 2012). "Máquinas del Infinito". Scientific American . 307 (3): 66–71. Código bibliográfico : 2012SciAm.307c..66P . doi : 10.1038 / scientificamerican0912-66 . PMID 22928263 .
- ^ Sipser, Michael (27 de junio de 2012). Introducción a la teoría de la computación (3 ed.). Aprendizaje Cengage. ISBN 978-1133187790.
enlaces externos
- Página de inicio personal en el MIT