caption doctoral_advisor work_institution birth_place field prizes article_title name alma_mater
shmuel safra amir pnueli tel aviv university jerusalem computer science , complexity theory gödel prize shmuel safra
 shmuel safra ph.d. weizmann institute of science 1990
shmuel safra

shmuel safra -lrb- -rrb- 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 even for weak factors of approximation -- and the theory of probabilistically checkable proofs -lrb- pcp -rrb- 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 , 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 '' .
