Stathis K. Zachos ( griego : Στάθης (Ευστάθιος) Ζάχος ; nacido en 1947 en Atenas ) es un matemático , lógico e informático teórico .
Zachos recibió su doctorado del ETHZ (Instituto Federal Suizo de Tecnología de Zúrich) en Matemáticas (y Ciencias de la Computación), 1978. Ha ocupado los puestos de profesor de Ciencias de la Computación en UCSB , CUNY y NTUA y profesor adjunto en ETHZ . Ha trabajado como investigador en el MIT , Brown-Boveri .
Stathis ha publicado trabajos de investigación en varias áreas de la informática . Su trabajo sobre Clases de complejidad aleatoria , [1] [2] Juegos de 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, usando Sistemas de Prueba Interactivos y Cuantificadores Probabilísticos, es que el Problema de Isomorfismo de Grafos probablemente no 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 las 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 Clases de Complejidad Probabilística y Funcional , Álgebras Combinatorias como base para la Teoría de Computaciones , las interconexiones de Técnicas Criptográficas y Complejidad Computacional , así como Algoritmos para Problemas de Gráficos . Ha coorganizado Conferencias Internacionales: STOC '87 (y comité de programación de STOC '01), ICALP , CiE ( Computabilidad en Europa ), PLS, ASL ( Association for Symbolic Logic) European Summer Meeting, ACAC (Coloquio de Atenas sobre Algoritmos y Complejidad) y NYCAC (Coloquio de Nueva York sobre Algoritmos y Complejidad).