Shmuel Safra
Encyclopedia
Shmuel Safra is a Professor of Computer Science
at Tel Aviv University
, Israel
. 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 (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.
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 automaton
, Streett automaton and Rabin automaton.
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".
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
at Tel Aviv University
Tel Aviv University
Tel Aviv University is a public university located in Ramat Aviv, Tel Aviv, Israel. With nearly 30,000 students, TAU is Israel's largest university.-History:...
, Israel
Israel
The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...
. Born in Jerusalem.
Safra's research areas include Complexity Theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and Automata Theory
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
. 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)
PCP (complexity)
In computational complexity theory, a probabilistically checkable proof is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject...
and the PCP theorem
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
, which gives stronger characterizations of the class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, 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
Finite state machine
A finite-state machine or finite-state automaton , or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states...
over infinite strings, in particular, the complexity of such translation for Büchi automaton
Büchi automaton
In computer science and automata theory, a Büchi automaton is a type of ω-automaton, which extends a finite automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton that visits one of the final states infinitely often. Büchi automata recognize the...
, Streett automaton and Rabin automaton.
In 2001, Safra won the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
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".
See also
- List of important publications in Computational Complexity
- Vertex Cover Problem
- Set Cover Problem