Shmuel Safra ( he, שמואל ספרא) 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
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
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 Buchi can mean:
__NOTOC__
Items
*Bachi, special Japanese drumsticks
*Butsi, the Hispanised term for jin deui (pastry made from glutinous rice) in the Philippines
*Büchi automaton, finite state automata extended to infinite inputs
*Büchi arithmeti ...
,
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
*
Bull graph
In the mathematical field of graph theory, the bull graph is a planar undirected graph with 5 vertices and 5 edges, in the form of a triangle with two disjoint pendant edges.
It has chromatic number 3, chromatic index 3, radius 2, diameter 3 and ...
*
Set cover problem
*
Vertex cover problem
External links
Muli Safra's HomepageComputational Complexity Theory Presentations*
{{DEFAULTSORT:Safra, Shmuel
Gödel Prize laureates
Living people
Israeli computer scientists
Israeli Jews
People from Jerusalem
Tel Aviv University faculty
Theoretical computer scientists
Weizmann Institute of Science alumni
1962 births