Shmuel Safra

Shmuel Safra is an Israeli computer scientist and professor at Tel Aviv University who won the Gödel Prize in 2001.

born 1960The PCP theoremHardness of approximation problemsAutomata over infinite strings

Occupation: computer scientist, university teacher
Education: Weizmann Institute of Science

Shmuel Safra was born in 1960 in Jerusalem

Shmuel Safra, also known as Muli, was born in Jerusalem in 1960.

He completed his doctorate at the Weizmann Institute of Science in 1990, under the supervision of Amir Pnueli. He then did postdoctoral work at Stanford University and at an IBM research center.

Safra is a professor of computer science at Tel Aviv University. His research covers complexity theory and automata theory. In complexity theory he worked on probabilistically checkable proofs, the PCP theorem and the hardness of approximation problems.

In automata theory he studied determinization and complementation of finite automata over infinite strings, including Büchi, Streett and Rabin automata. In 2001 he received the Gödel Prize for his work on the PCP theorem and its consequences for approximation.