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 autómatas . Su trabajo en teoría de la complejidad incluye la clasificación de problemas de aproximación (mostrándolos como NP-hard incluso para factores de aproximación débiles) y la teoría de pruebas probabilísticamente comprobables (PCP) y el teorema PCP , que proporciona caracterizaciones más sólidas de la clase NP , a través de una prueba de pertenencia que puede verificarse leyendo solo un número constante de sus bits.
Su trabajo sobre la teoría de autómatas investiga la determinización y complementación de autómatas finitos sobre cuerdas 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 la dificultad de aproximar camarillas" y "Verificación probabilística de pruebas: una nueva caracterización de NP".