Michael Sipser - Michael Sipser
Michael Sipser | |
---|---|
![]() | |
narozený | Michael Fredric Sipser 17. září 1954 |
Národnost | americký |
Alma mater | |
Ocenění |
|
Vědecká kariéra | |
Pole | |
Instituce | MIT |
Teze | Nedeterminismus a velikost obousměrných konečných automatů (1980) |
Doktorský poradce | Manuel Blum |
Doktorandi | |
webová stránka | matematika |
Michael Fredric Sipser (narozený 17. září 1954) je Američan teoretický počítačový vědec kdo včas přispěl do teorie výpočetní složitosti. On je profesor z Aplikovaná matematika a byl děkanem vědy na Massachusetts Institute of Technology.
Životopis
Sipser se narodil a vyrůstal v Brooklynu v New Yorku a ve 12 letech se přestěhoval do Oswega v New Yorku. Získal bakalářský titul z matematiky od Cornell University v roce 1974 a doktorát z inženýrství na Kalifornská univerzita v Berkeley v roce 1980 pod vedením Manuel Blum.[1][2]
Připojil se k MIT Laboratoř pro informatiku jako výzkumný pracovník v roce 1979 a poté pracoval jako výzkumný pracovník v IBM Research v San Jose. V roce 1980 nastoupil na fakultu MIT. Akademický rok 1985-1986 strávil na fakultě University of California v Berkeley a poté se vrátil na MIT. Od roku 2004 do roku 2014 působil jako vedoucí katedry matematiky MIT. Byl jmenován prozatímním děkanem MIT School of Science v roce 2013 a děkan v roce 2014.[3] Působil jako děkan až do roku 2020, kdy ho následoval Nergis Mavalvala.[4] Je členem Americké akademie umění a věd.[5] V roce 2015 byl zvolen členem kolegia Americká matematická společnost „za příspěvky k teorii složitosti a za vedení a služby matematické komunitě.“[6]Byl zvolen jako Člen ACM v roce 2017.[7]
Vědecká kariéra
Sipser se specializuje na algoritmy a teorie složitosti, konkrétně efektivní kódy pro opravu chyb, interaktivní kontrolní systémy, náhodnost, kvantový výpočet a stanovení inherentní výpočetní obtížnosti problémů. Zavedl metodu pravděpodobnostního omezení pro prokázání superpolynomiálních dolních mezí složitost obvodu v papírovém spojení s Merrickem Furstem a James B. Saxe.[8] Jejich výsledek byl později vylepšen tak, aby byl exponenciálně nižší Andrew Yao a Johan Håstad.[9]
Brzy derandomizace větu, Sipser to ukázal BPP je obsažen v polynomiální hierarchie,[10] následně vylepšili Peter Gács a Clemens Lautemann, aby vytvořili to, co je nyní známé jako Sipser-Gàcs-Lautemannova věta. Sipser také navázal spojení mezi expandérové grafy a derandomizace.[11] On a jeho doktorand Daniel Spielman představen expandér kódy, aplikace grafů expandéru.[12] Spolu s postgraduálním studentem Davidem Lichtensteinem to Sipser dokázal Jít je PSPACE tvrdý.[13]
V teorii kvantových výpočtů představil adiabatický algoritmus společně s Edward Farhi, Jeffrey Goldstone a Samuel Gutmann.[14]
Sipser se již dlouho zajímal o Problém P versus NP. V roce 1975 vsadil unci zlata Leonard Adleman že problém bude vyřešen důkazem, že P ≠ NP do konce 20. století. Sipser poslal Adlemana Americká mince zlatého orla v roce 2000, protože problém zůstal (a zůstává) nevyřešen.[15]
Pozoruhodné knihy
Sipser je autorem Úvod do teorie výpočtu,[16] učebnice pro teoretická informatika.
Osobní život
Sipser žije v Cambridge ve státě Massachusetts se svou manželkou Inou a má dvě děti: dceru Rachel, která vystudovala New York University, a mladšího syna Aarona, který je vysokoškolským studentem na MIT.[1]
Reference
- ^ A b Trafton, Anne, „Michael Sipser jmenován děkanem School of Science: Sipser působí jako prozatímní děkan od odchodu Marca Kastnera“, MIT News Office, 5. června 2014
- ^ Michael Sipser na Matematický genealogický projekt
- ^ Matematika MIT | Adresář lidí Archivováno 2008-12-18 na Wayback Machine
- ^ "School of Science | MIT History". Citováno 2020-08-25.
- ^ "Členství". Americká akademie umění a věd. Citováno 23. září 2014.
- ^ 2016 Třída členů AMS, Americká matematická společnost, vyvoláno 2015-11-16.
- ^ ACM oceňuje členy 2017 za transformační příspěvky a pokrok v technologii v digitálním věku, Asociace pro výpočetní techniku, 11. prosince 2017, vyvoláno 2017-11-13
- ^ Furst, Merrick; Saxe, James B.; Sipser, Michael (1984). "Parita, obvody a hierarchie polynomiálního času". Teorie matematických systémů. 17 (1): 13–27. doi:10.1007 / BF01744431. PAN 0738749. S2CID 14677270.
- ^ "Research Vignette: Hard Problems All The Way Up | Simons Institute for the Theory of Computing". simons.berkeley.edu. Citováno 2015-09-17.
- ^ Sipser, Michael (1983). "Složitost teoretický přístup k náhodnosti". Sborník příspěvků z 15. sympozia ACM o teorii práce s počítačem.
- ^ Sipser, Michael (1986). "Expandéry, náhodnost nebo čas versus prostor". Sborník z konference o struktuře ve složitosti. Přednášky z informatiky. 223: 325–329. doi:10.1007/3-540-16486-3_108. ISBN 978-3-540-16486-9.
- ^ Sipser, Michael; Spielman, Daniel (1996). „Kódy expandéru“ (PDF). Transakce IEEE na teorii informací. 42 (6): 1710–1722. doi:10.1109/18.556667.
- ^ Lichtenstein, David; Sipser, Michael (01.04.1980). „GO je polynomiální prostor tvrdý“. J. ACM. 27 (2): 393–401. doi:10.1145/322186.322201. ISSN 0004-5411. S2CID 29498352.
- ^ Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam; Sipser, Michael (2000-01-28). "Kvantový výpočet adiabatickou evolucí". arXiv:quant-ph / 0001106.
- ^ Pavlus, John (01.01.2012). „Stroje nekonečna“. Scientific American. 307 (3): 66–71. Bibcode:2012SciAm.307c..66P. doi:10.1038 / scientificamerican0912-66. PMID 22928263.
- ^ Sipser, Michael (2012-06-27). Úvod do teorie výpočtu (3. vyd.). Cengage Learning. ISBN 978-1133187790.