Shmuel ( Muli ) 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 .
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-difíciles incluso para factores de aproximación débiles) y la teoría de pruebas comprobables probabilísticamente (PCP) y el teorema de PCP , que proporciona caracterizaciones más sólidas de la clase NP , a través de una prueba de membresía que se puede verificar leyendo solo un número constante de sus bits.
Su trabajo sobre teoría de autómatas investiga la determinización y complementación de autómatas finitos sobre cadenas infinitas , en particular, la complejidad de dicha traducción para los autómatas de Büchi , los autómatas de Streett y los autómatas de Rabin .
En 2001, Safra ganó el Premio Gödel en informática teórica por sus artículos "Pruebas interactivas y dureza de camarillas aproximadas" y "Comprobación probabilística de pruebas: una nueva caracterización de NP".