Stathis Zachos - Stathis Zachos

Stathis K. Zachos (řecký: Στάθης (Ευστάθιος) Ζάχος; narozen 1947 v Athény ) je matematik, logik a teoretický počítačový vědec.

Životopis

Zachos dostal svůj PhD z ETHZ (Švýcarský federální technologický institut v Curychu) z matematiky (a informatiky), 1978. Profesorské pozice zastával v Počítačová věda na UCSB, CUNY a NTUA a mimořádný profesor na ETHZ. Pracoval jako výzkumný pracovník ve společnosti MIT, Brown-Boveri.

Stathis publikoval výzkumné práce v několika oblastech Počítačová věda. Jeho práce na Randomized Třídy složitosti,[1][2] Hry Arthur – Merlin,[3] a Interaktivní kontrolní systémy[4] byl velmi vlivný při dokazování důležitých vět a je citován v hlavních učebnicích výpočetní složitost.[5][6][7] Jedním z jeho důležitých příspěvků, využívajících systémy interaktivních důkazů a pravděpodobnostní kvantifikátory, je to, že Graf izomorfismus Problém pravděpodobně nebude NP-kompletní (společně s R. Boppanou, J. Hastadem).[8] Graf Izomorfismus je jedním z mála oslavovaných problémů v NP, u nichž se dosud neprojevilo, že by byly NP-Complete, nebo v nejvlivnější práci P. Zachose představující a dokazující vlastnosti třídy Parita-P (s Christos Papadimitriou ).[9] Představil také Pravděpodobnostní kvantifikátory a Alternativy pravděpodobnostních kvantifikátorů, aby jednotně popsal různé třídy složitosti, stejně jako systémy interaktivních důkazů a pravděpodobnostní hry.[10]

Mezi jeho současné zájmy patří Pravděpodobnostní a Třídy funkční složitosti, Kombinované algebry jako základ pro Teorie výpočtů, propojení Kryptografické techniky a Výpočetní složitost stejně jako Algoritmy pro Problémy s grafy. Spoluorganizoval mezinárodní konference: STOC '87 (a programovací výbor STOC '01), ICALP, CiE (Vyčíslitelnost v Evropě ), PLS, ASL (Sdružení pro symbolickou logiku ) European Summer Meeting, ACAC (Athens Colloquium on Algorithms and Complexity) a NYCAC (New York Colloquium on Algorithms and Complexity).

Je bratrem teoretického fyzika Kosmas Zachos.

Viz také

Reference

  1. ^ Zachos, Stathis (1982). „Robustnost pravděpodobnostních tříd výpočetní složitosti při definičních poruchách“. Informace a kontrola. 54 (3): 143–154. doi:10.1016 / s0019-9958 (82) 80019-3.
  2. ^ Zachos, Stathis; Hans Heller (1986). „Rozhodující charakterizace BPP“. Informace a kontrola. 69 (1–3): 125–135. doi:10.1016 / s0019-9958 (86) 80044-4.
  3. ^ Zachos, Stathis; Martin Fürer (1987). Pravděpodobnostní kvantifikátory vs. nedůvěřivé protivníky. Základy softwarové technologie a teoretické informatiky. Přednášky z informatiky. 287. str. 443–455. doi:10.1007/3-540-18625-5_67. ISBN  978-3-540-18625-0.
  4. ^ Fürer, Martin; Oded Goldreich; Yishay Mansour; Michael Sipser; Stathis Zachos (1989). "O úplnosti a spolehlivosti v interaktivních zkušebních systémech". Pokroky ve výpočetním výzkumu: náhodnost a výpočet. 5: 25–32. CiteSeerX  10.1.1.39.9412.
  5. ^ Papadimitriou, Christos H. (1994). Výpočetní složitost. Addison Wesley.
  6. ^ Hemaspaandra, Lane A .; Mitsunori Ogihara (2001). Společník teorie složitosti. Springer. ISBN  978-3540674191.
  7. ^ Du, Ding-Zhu; Ker-I Ko (2000). Teorie výpočetní složitosti. Wiley-Interscience.
  8. ^ Boppana, Ravi B .; Hastad, Johan; Zachos, Stathis (6. května 1987). „Má co-NP krátké interaktivní důkazy?“. Dopisy o zpracování informací. 25 (2): 127–132. doi:10.1016/0020-0190(87)90232-8.
  9. ^ Papadimitriou, Christos H .; Stathis Zachos (1982). "Dvě poznámky k síle počítání". In Proceedings of the 6th GI-Conference on Theoretical Computer Science. Přednášky z informatiky. 145: 269–276. doi:10.1007 / BFb0009651. ISBN  978-3-540-11973-9.
  10. ^ Zachos, Stathis (1988). "Pravděpodobnostní kvantifikátory a hry". Journal of Computer and System Sciences. 36 (3): 433–451. doi:10.1016/0022-0000(88)90037-2.

externí odkazy