- Shmuel Safra
name = Shmuel Safra
image_width = 150px
caption = Shmuel Safra
Computer Science, Complexity Theory
Tel Aviv University
alma_mater = Ph.D.
Weizmann Institute of Science 1990
Shmuel Safra is a Professor of
Computer Scienceat Tel Aviv University, Israel. 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%C3%BCchi automaton, Streett automatonand Rabin automaton.
In 2001, Safra won the
Gödel Prizein theoretical computer science for his papers "Interactive Proofs and the Hardness of Approximating Cliques" and "Probabilistic Checking of Proofs: A New Characterization of NP".
* List of important publications in Computational Complexity
* Vertex Cover Problem
* Set Cover Problem
* [http://www.cs.tau.ac.il/~safra/ Muli Safra's Homepage]
* [http://computational.complexity.googlepages.com/home Computational Complexity Theory Presentations]
* [http://www.genealogy.ams.org/id.php?id=19291 Mathematics Genealogy Project]
Wikimedia Foundation. 2010.