Shmuel Safra

Shmuel (Muli) Safra (Hebrew: שמואל ספרא) is an Israeli computer scientist.He is a Professor of Computer Science at Tel Aviv University, Israel.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.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".
JerusalemWeizmann Institute of ScienceGödel PrizeComputer sciencecomplexity theoryTel Aviv UniversityThesisDoctoral advisorAmir PnueliHebrewIsraelautomata theoryapproximation problemsNP-hardprobabilistically checkable proofs (PCP)PCP theoremfinite automatainfinite stringsBüchi automataStreett automataRabin automatatheoretical computer scienceBull graphMathematics Genealogy ProjectGoldwasserMicaliRackoffHåstadImmermanSzelepcsényiJerrumSinclairHalpernWolperLovászMotwaniSzegedySénizerguesFreundSchapireHerlihyShavitZaharoglouMatiasAgrawalSaxenaRazborovRudichSpielmanReingoldVadhanWigdersonMitchellKoutsoupiasPapadimitriouRoughgardenÉ. TardosFranklinO'HearnMcSherryNissimG. TardosBrakerskiGentryVaikuntanathan