Hispanopedia Wiki
Articulo de referencia

Stathis Zachos

Stathis K. Zachos ( griego : Στάθης (Ευστάθιος) Ζάχος ; nacido en 1947 en Atenas) es un matemático, lógico e informático teórico . Biografía Zachos obtuvo su doctorado en matemá...

Hispanopedia WikiContenido en espanolLectura gratuita

Stathis K. Zachos ( griego : Στάθης (Ευστάθιος) Ζάχος ; nacido en 1947 en Atenas) es un matemático, lógico e informático teórico .

Biografía

Zachos obtuvo su doctorado en matemáticas (e informática) en el ETHZ (Instituto Federal Suizo de Tecnología de Zúrich) en 1978. Ha sido profesor de informática en la Universidad de California, Santa Bárbara , en el Brooklyn College de la Universidad de la Ciudad de Nueva York y en la Universidad Técnica Nacional de Atenas , además de profesor adjunto en el ETHZ . También ha trabajado como investigador en el Instituto Tecnológico de Massachusetts (MIT) , en Brown-Boveri .

Stathis ha publicado artículos de investigación en varias áreas de la informática. Su trabajo sobre clases de complejidad aleatorias , [ 1 ] [ 2 ] protocolos Arthur-Merlin , [ 3 ] y sistemas de prueba interactivos [ 4 ] ha sido muy influyente en la demostración de teoremas importantes y se cita en los principales libros de texto de complejidad computacional . [ 5 ] [ 6 ] [ 7 ] Una de sus contribuciones importantes, utilizando sistemas de prueba interactivos y cuantificadores probabilísticos, es que el problema del isomorfismo de grafos no es probable que sea NP-completo (junto con R. Boppana, J. Hastad). [ 8 ] El isomorfismo de grafos es uno de los pocos problemas célebres en NP que aún no se ha demostrado que sea NP-completo o en P. El trabajo más influyente de Zachos fue la introducción y demostración de propiedades de la clase Parity-P (con Christos Papadimitriou ). [ 9 ] También introdujo cuantificadores probabilísticos y alternancias de cuantificadores probabilísticos para describir uniformemente varias clases de complejidad, así como sistemas de prueba interactivos y juegos probabilísticos. [ 10 ]

Sus intereses actuales incluyen las clases de complejidad probabilística y funcional , las álgebras combinatorias como fundamento de la teoría de la computación , las interconexiones entre las técnicas criptográficas y la complejidad computacional , así como los algoritmos para problemas de grafos . Ha coorganizado conferencias internacionales como STOC '87 (y el comité de programación de STOC '01), ICALP , CiE ( Computability in Europe ), PLS, ASL ( Association for Symbolic Logic ), European Summer Meeting, ACAC (Athens Colloquium on Algorithms and Complexity) y NYCAC (New York Colloquium on Algorithms and Complexity).

Es hermano del físico teórico Cosmas Zachos .

Véase también

Referencias

  1. ↑ Zachos, Stathis (1982). "Robustez de las clases de complejidad computacional probabilística bajo perturbaciones definicionales". Information and Control . 54 (3): 143– 154. doi : 10.1016/s0019-9958(82)80019-3 .
  2. ↑ Zachos, Stathis; Hans Heller (1986). "Una caracterización decisiva del BPP" . Information and Control . 69 ( 1–3 ): 125–135 . doi : 10.1016/s0019-9958(86)80044-4 .
  3. ↑ Zachos, Stathis; Martin Fürer (1987). «Cuantificadores probabilísticos frente a adversarios desconfiados». Fundamentos de la tecnología del software y la informática teórica . Notas de clase en informática. Vol. 287. págs. 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). "Sobre la completitud y la solidez en los sistemas de prueba interactivos". Advances in Computing Research: Randomness and Computation . 5 : 25–32 . CiteSeerX 10.1.1.39.9412 . 
  5. ↑ Papadimitriou, Christos H. (1994). Complejidad computacional . Addison Wesley.
  6. ^ Hemaspaandra, carril A.; Mitsunori Ogihara (2001). El compañero de la teoría de la complejidad . Saltador. ISBN 978-3540674191.
  7. ↑ Du, Ding-Zhu; Ker-I Ko (2000). Teoría de la Complejidad Computacional . Wiley-Interscience.
  8. ↑ Boppana, Ravi B.; Hastad, Johan; Zachos, Stathis (6 de mayo de 1987). "¿Tiene co-NP pruebas interactivas cortas?". Information Processing Letters . 25 (2): 127– 132. doi : 10.1016/0020-0190(87)90232-8 .
  9. ↑ Papadimitriou, Christos H.; Stathis Zachos (1982). «Dos observaciones sobre el poder del conteo». Informática teórica . Notas de clase en informática. Vol. 145. págs. 269–276 . doi : 10.1007/BFb0009651 (inactivo el 12 de julio de 2025). ISBN   978-3-540-11973-9.{{cite book}}: |journal=ignorado ( ayuda ) CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
  10. ↑ Zachos, Stathis (1988). "Cuantificadores probabilísticos y juegos". Journal of Computer and System Sciences . 36 (3): 433– 451. doi : 10.1016/0022-0000(88)90037-2 .