Prof. Muli Safra

Prof. Shmeul (Muli) Safra


Blavatnik School of Computer Science, Checkpoint Building (office 454)


Phone: +972 (0)3 640-5371


Research interests:

Shmuel Safra is a Professor of Computer Science at Tel Aviv University, Israel. Safra's research areas include complexity theory and automata theory. His work in complexity theory includes the classification of approximation problems—showing them to be 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 in terms of a membership proof that can be verified reading only a constant number of bits. His earlier work on automata theory investigates determinization and complementation of finite automata over infinite strings, in particular the complexity of such translations 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."


Tel Aviv University makes every effort to respect copyright. If you own copyright to the content contained
here and / or the use of such content is in your opinion infringing, Contact us as soon as possible >>