Quantcast
SS
Israel
72 views this week
Shmuel Safra

Shmuel Safra

Israeli computer scientist
The basics
Quick Facts
Occupations Computer scientist Educator
Countries Israel
A.K.A. Muli Safra
Gender male
Birth Jerusalem
The details
Biography

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

The contents of this page are sourced from Wikipedia article. The contents are available under the CC BY-SA 4.0 license.
comments so far.
Comments
arrow-left arrow-right arrow-up arrow-down instagram whatsapp myspace quora soundcloud spotify tumblr vk website youtube stumbleupon comments comments pandora gplay iheart tunein pandora gplay iheart tunein itunes