Shmuel Safra - Shmuel Safra
Shmuel Safra | |
---|---|
narozený | 1962 |
Alma mater | Ph.D. Weizmann Institute of Science 1990 |
Ocenění | Gödelova cena |
Vědecká kariéra | |
Pole | Počítačová věda, teorie složitosti |
Instituce | Tel Avivská univerzita |
Doktorský poradce | Amir Pnueli |
Shmuel Safra (hebrejština: שמואל ספרא) Je izraelský počítačový vědec. Je profesorem Počítačová věda na Tel Avivská univerzita, Izrael. Narodil se v Jeruzalém.
Mezi oblasti výzkumu společnosti Safra patří teorie složitosti a teorie automatů. Jeho práce v Teorii složitosti zahrnuje klasifikaci problémů aproximace - jejich předvádění NP-tvrdé i pro slabé faktory aproximace - a teorii pravděpodobnostně ověřitelné důkazy (PCP) a Věta o PCP, což dává silnější charakterizaci třídy NP prostřednictvím dokladu o členství, který lze ověřit čtením pouze konstantního počtu jeho bitů.
Jeho práce na teorii automatů zkoumá determinizaci a doplnění konečné automaty přes nekonečné řetězce, zejména složitost takového překladu pro Büchi automaty, Streett automaty a Rabinovy automaty.
V roce 2001 Safra vyhrál Gödelova cena v teoretické informatice za své práce „Interaktivní důkazy a tvrdost aproximace kliky“ a „Pravděpodobnostní kontrola důkazů: nová charakteristika NP“.