Shmuel Safra
Shmuel Safra | |
|---|---|
| Born | 1960 |
| Alma mater | Ph.D. Weizmann Institute of Science |
| Awards | Gödel Prize |
| Scientific career | |
| Fields | Computer science, complexity theory |
| Institutions | Tel Aviv University |
| Thesis | Complexity Of Automata On Infinite Objects (1990) |
| Doctoral advisor | Amir Pnueli |
Shmuel (Muli) Safra (
.Safra's research areas include
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
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
- Set cover problem
- Vertex cover problem
External links
- Muli Safra's Homepage
- Computational Complexity Theory Presentations
- Shmuel Safra at the Mathematics Genealogy Project
| International | |
|---|---|
| National | |
| Academics | |
