Shmuel Safra
Shmuel Safra (n. en Jerusalén) es un profesor israelí de ciencias de la computación de la Universidad de Tel Aviv.
| Shmuel Safra | ||
|---|---|---|
| Información personal | ||
| Nacimiento |
Siglo XX Jerusalén,  Israel | |
| Nacionalidad | israelí | |
| Educación | ||
| Educado en | Ph.D. Instituto Weizmann de Ciencias 1990 | |
| Supervisor doctoral | Amir Pnueli | |
| Información profesional | ||
| Área |
Complejidad computacional Teoría de autómatas | |
| Empleador | Universidad de Tel Aviv | |
| Estudiantes doctorales | Irit Dinur | |
| Distinciones | Premio Gödel (2001) | |
Su investigación incluye las áreas de complejidad computacional y teoría de autómatas. Su trabajo en complejidad computacional incluye la clasificación de problemas de aproximación y la teoría de PCP, incluyendo el teorema PCP, que da una fuerte caracterización de la clase NP, a través de un oráculo que puede ser verificado leyendo sólo un número constante de bits.
En su trabajo en teoría de autómatas investiga el determinismo y complementos de autómatas finitos sobre cadenas de caracteres infinitos.
En 2001, Safra ganó el Premio Gödel en ciencias de la computación teórica por sus artículos "Interactive Proofs and the Hardness of Approximating Cliques" y "Probabilistic Checking of Proofs: A New Characterization of NP".