Shmuel Safra
# Shmuel Safra

Shmuel Safra (n. en Jerusalén) es un profesor israelí de ciencias de la computación de la Universidad de Tel Aviv.

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".

