Shmuel Safra
Shmuel Safra | |
---|---|
Born | 1960 |
Alma mater | Ph.D. Weizmann Institute of Science |
Awards | Gödel Prize |
Scientific career | |
Fields | Computer science, complexity theory |
Institutions | Tel Aviv University |
Thesis | Complexity Of Automata On Infinite Objects (1990) |
Doctoral advisor | Amir Pnueli |
Shmuel (Muli) Safra (Hebrew: שמואל ספרא) is an Israeli computer scientist. He is a Professor of Computer Science at Tel Aviv University, Israel. He was born in Jerusalem.
Safra's research areas include complexity theory and automata theory. His work in complexity theory includes the classification of approximation problems—showing them NP-hard even for weak factors of approximation—and the theory of probabilistically checkable proofs (PCP) and the PCP theorem, which gives stronger characterizations of the class NP, via a membership proof that can be verified reading only a constant number of its bits.
His work on automata theory investigates determinization and complementation of finite automata over infinite strings, in particular, the complexity of such translation for Büchi automata, Streett automata and Rabin automata.
In 2001, Safra won the Gödel Prize in theoretical computer science for his papers "Interactive Proofs and the Hardness of Approximating Cliques" and "Probabilistic Checking of Proofs: A New Characterization of NP".
See also
External links
- Articles with short description
- Short description matches Wikidata
- Articles with hCards
- Articles containing Hebrew-language text
- Articles with VIAF identifiers
- Articles with J9U identifiers
- Articles with ACM-DL identifiers
- Articles with DBLP identifiers
- Articles with MATHSN identifiers
- Articles with MGP identifiers
- Articles with ZBMATH identifiers
- Gödel Prize laureates
- Living people
- Israeli computer scientists
- Israeli Jews
- People from Jerusalem
- Academic staff of Tel Aviv University
- Theoretical computer scientists
- Weizmann Institute of Science alumni
- 1962 births