Shmuel Safra

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Shmuel Safra
Nacimiento
Jerusalén, Flag of Israel.svg Israel
Nacionalidad israelí
Campo Complejidad computacional
Teoría de autómatas
Instituciones Universidad de Tel Aviv
Alma máter Ph.D. Instituto Weizmann de Ciencias 1990
Supervisor doctoral Amir Pnueli
Premios
destacados
Premio Gödel (2001)

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

Enlaces externos[editar]