Shmuel Safra

Shmuel Safra

Infobox_Scientist
name = Shmuel Safra


image_width = 150px
caption = Shmuel Safra
birth_date =
birth_place =
death_date =
death_place =
residence =
citizenship =
nationality =
ethnicity =
field = Computer Science, Complexity Theory
work_institution = Tel Aviv University
alma_mater = Ph.D. Weizmann Institute of Science 1990
doctoral_advisor = Amir Pnueli
doctoral_students =
known_for =
author_abbreviation_bot =
author_abbreviation_zoo =
prizes = Gödel Prize
religion =
footnotes =

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%C3%BCchi 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".

See also

* List of important publications in Computational Complexity

* Vertex Cover Problem

* Set Cover Problem

External links

* [http://www.cs.tau.ac.il/~safra/ Muli Safra's Homepage]
* [http://computational.complexity.googlepages.com/home Computational Complexity Theory Presentations]
* [http://www.genealogy.ams.org/id.php?id=19291 Mathematics Genealogy Project]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Shmuel Safra — Nacimiento Jerusalén,  Israel Nacionalidad israelí Campo Complejidad computaci …   Wikipedia Español

  • Shmuel Safra — (hebräisch ‏שמואל מולי ספרא‎, genannt Muli Safra) (* in Jerusalem) ist ein israelischer Informatiker. Safra wurde 1990 am Weizmann Institut für Wissenschaften bei Amir Pnueli promoviert (Complexity of Automata on Infinite Objects). Als Post… …   Deutsch Wikipedia

  • Safra — ist der Familienname folgender Personen: Edmond Safra (1931–1999), brasilianischer Unternehmer Joseph Safra (* um 1939), brasilianischer Unternehmer Shmuel Safra (genannt Muli Safra), israelischer Informatiker Safra ist der Vorname folgender… …   Deutsch Wikipedia

  • PCP theorem — In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and… …   Wikipedia

  • Prix Gödel — Nommé en l honneur du logicien Kurt Gödel, le prix Gödel a été créé en 1992 par l European Association for Theoretical Computer Science (EATCS), l Association for Computing Machinery (ACM) et le groupe de l ACM sur l algorithmique et la théorie… …   Wikipédia en Français

  • PCP-Theorem — Das PCP Theorem ist ein Satz aus der theoretischen Informatik (Komplexitätstheorie). Es beruht auf dem Konzept des zufällig verifizierbaren Beweises eines mathematischen Satzes (probabilistic checkable proof, PCP), der wiederum auf das Konzept… …   Deutsch Wikipedia

  • List of Israelis — This is a list of prominent Israelis (including Arab citizens of Israel).Historical figuresPoliticians* Chaim Weizmann first President of Israel (1949 52) * David Ben Gurion first Prime Minister of Israel (1948 54, 1955 63) * Moshe Sharett prime… …   Wikipedia

  • Géraud Sénizergues — est professeur d informatique à l Université de Bordeaux et membre du Laboratoire bordelais de recherche en informatique. Récipiendaire du Prix Gödel en 2002 pour avoir démontré la décidabilité de l égalité des langages reconnus par des automates …   Wikipédia en Français

  • Johan Håstad — Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique. Il a reçu le Prix Gödel en 1994 et 2011 et le Doctoral Dissertation Award de l Association for Computing… …   Wikipédia en Français

  • László Lovász — (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes. Sommaire …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”