Shmuel Safra - Shmuel Safra

Shmuel Safra ( hebraisk : שמואל ספרא ) er en israelsk datamaskinforsker. Han er professor i informatikk ved Tel Aviv University , Israel . Han ble født i Jerusalem .

Safras forskningsområder inkluderer kompleksitetsteori og automatateori . Hans arbeid i kompleksitetsteori inkluderer klassifisering av tilnærmingsproblemer - viser dem NP-hardt selv for svake tilnærmingsfaktorer - og teorien om sannsynlig kontrollerbare bevis (PCP) og PCP-teoremet , som gir sterkere karakteriseringer av klassen NP , via en medlemskapsbevis som kan bekreftes, mens du bare leser et konstant antall av bitene.

Hans arbeid med automatteori undersøker bestemmelse og komplementering av endelige automater over uendelige strenger, spesielt kompleksiteten i slik oversettelse for Büchi automata , Streett automata og Rabin automata .

I 2001 vant Safra Gödel-prisen i teoretisk informatikk for sine artikler "Interactive Proofs and the Hardness of Approximating Cliques" og "Probabilistic Checking of Proofs: A New Characterization of NP".

Se også

• Hodepunktproblem
• Sett dekningsproblem

Eksterne linker

• Muli Safras hjemmeside
• Computational Complexity Theory Presentations
• Shmuel Safra ved Mathematics Genealogy Project