Shmuel Safra
Shmuel Safra | |
|---|---|
| Geboren | 1960 |
| Alma Mater | Ph.D. Weizmann Institute of Science 1990 |
| Auszeichnungen | Gödel -Preis |
| Wissenschaftliche Karriere | |
| Felder | Informatik, Komplexitätstheorie |
| Institutionen | Tel Aviv University |
| Doktorand | Amir Pnueli |
Shmuel Safra (hebräisch: שמואל ספרא) ist ein israelischer Informatiker.Er ist Professor von Informatik bei Tel Aviv University, Israel. Er wurde geboren in Jerusalem.
Zu den Forschungsbereichen von SAFRA gehören Komplexitätstheorie und Automatenheorie.Seine Arbeit in der Komplexitätstheorie umfasst die Klassifizierung von Annäherungsprobleme- sie verhandeln Np-harte auch für schwache Annäherungsfaktoren - und die Theorie von Probabilistisch überprüfbare Beweise (PCP) und die PCP -Theorem, was stärkere Charakterisierungen der Klasse verleiht Np, über einen Mitgliedschaftsnachweis, der überprüft werden kann, nur eine konstante Anzahl seiner Bits zu lesen.
Seine Arbeit an der Automatentheorie untersucht die Determinisierung und Ergänzung von Finite Automaten Über Unendliche Saiteninsbesondere die Komplexität einer solchen Übersetzung für BÜCHI AUTOMATA, STRETT AUTOMATA und Rabin Automata.
Im Jahr 2001 gewann Safra die Gödel -Preis In theoretischer Informatik für seine Papiere "interaktive Beweise und die Härte der approximierenden Cliquen" und "probabilistische Überprüfung von Beweisen: eine neue Charakterisierung von NP".