Shmuel Safra ( hebreo : שמואל ספרא ) es un informático israelí. Es profesor de Ciencias de la Computación en la Universidad de Tel Aviv , Israel . Nació en Jerusalén .
Shmuel Safra | |
---|---|
Nació | 1962 |
alma mater | Doctor. Instituto de Ciencias Weizmann 1990 |
Premios | Premio Gödel |
Carrera científica | |
Campos | Ciencias de la computación , teoría de la complejidad |
Instituciones | Universidad de tel aviv |
Asesor de doctorado | Amir Pnueli |
Las áreas de investigación de Safra incluyen la teoría de la complejidad y la teoría de los autómatas . Su trabajo en Teoría de la Complejidad incluye la clasificación de problemas de aproximación, mostrándolos NP-hard incluso para factores débiles de aproximación, y la teoría de demostraciones probabilísticamente verificables (PCP) y el teorema PCP , que da caracterizaciones más fuertes de la clase NP , a través de prueba de membresía que se puede verificar leyendo solo un número constante de sus bits.
Su trabajo sobre la teoría de autómatas investiga la determinación y complementación de autómatas finitos sobre cadenas infinitas, en particular, la complejidad de dicha traducción para autómatas Büchi , autómatas Streett y autómatas Rabin .
En 2001, Safra ganó el premio Gödel en informática teórica por sus trabajos "Pruebas interactivas y la dureza de las camarillas aproximadas" y "Comprobación probabilística de pruebas: una nueva caracterización de NP".