Shmuel Safra

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

• Gráfico de toro
• Problema con la cubierta del conjunto
• Problema de cobertura de vértices

• Página de inicio de Muli Safra
• Presentaciones sobre la teoría de la complejidad computacional
• Shmuel Safra en el Proyecto de Genealogía Matemática