Shmuel Safra
Get Shmuel Safra essential facts below. View Videos or join the Shmuel Safra discussion. Add Shmuel Safra to your topic list for future reference or share this resource on social media.
Shmuel Safra
Shmuel Safra
Alma materPh.D. Weizmann Institute of Science 1990
AwardsGödel Prize
Scientific career
FieldsComputer science, complexity theory
InstitutionsTel Aviv University
Doctoral advisorAmir Pnueli

Shmuel 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

  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.



Music Scenes