Irit Dinur

Irit Dinur

Irit Dinur (hebräisch ‏אירית דינור‎) ist eine israelische Informatikerin.

Dinur studierte Informatik an der Universität Tel Aviv, wo sie bei Shmuel Safra promoviert wurde. Danach war sie einige Jahre am Institute for Advanced Study, bei NEC Research und ein Jahr als Miller Fellow an der University of California, Berkeley. Sie war Professorin für Informatik an der Hebräischen Universität und ist Professorin am Weizmann Institut.

Sie wurde 2005 bekannt durch einen neuen Beweis des PCP-Theorems, der eine starke Vereinfachung gegenüber vorhergehenden Beweisen darstellte.[1] Das Theorem wurde ursprünglich in den 1990er Jahren durch Sanjeev Arora, Safra und andere bewiesen.[2]

2010 hielt sie einen Plenarvortrag auf dem ICM in Hyderabad (Probabilistic checkable proofs and codes).

Schriften

  • The PCP Theorem by gap amplification, Technical Report 2005 und Journal of the ACM, Band 54, 2007, S.1, Online, pdf

Weblinks

Einzelnachweise

  1. ↑ Jaikumar Radhakrishnan, Madhu Sudan: On Dinur´s Proof of the PCP theorem. In: Bulletin AMS. Band 44, 2007, S. 19–61
  2. ↑ O´Donnel History of the PCP Theorem, pdf
PND: kein individualisierter Datensatz vorhanden (Stand: 13. Februar 2011) | Nicht individualisierter Eintrag zum Namen Irit Dinur im Katalog der DNB

Wikimedia Foundation.

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

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Dinur — (hebräisch ‏דינור‎) ist der Familienname von: Ben Zion Dinur geb. Dinaburg (1884–1973), israelischer Historiker und Politiker Irit Dinur, israelische Informatikerin …   Deutsch Wikipedia

  • 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

  • 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

  • PCP (complexity) — In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems. Introduction and definition In complexity theory, a PCP system can be viewed as an interactive proof system in which the… …   Wikipedia

  • Liste von Mathematikerinnen — Die Liste von Mathematikerinnen führt auch theoretische Informatikerinnen und theoretische Physikerinnen mit deutlich mathematischer Ausrichtung auf. Aufgenommen wurden unter anderem die Preisträgerinnen der Noether Lecture und des Ruth Lyttle… …   Deutsch Wikipedia

  • 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

  • List of Hebrew language authors — List of Hebrew language authors:A*Yossi Abolafia *Dorit Abusch *Shimon Adaf *Suzane Adam *Tamar Adar *Uri Adelman *Malka Adler *Meir Agassi *Shmuel Yosef Agnon (winner of the Nobel prize for literature in 1966) *Leah Aini *Miriam Akavia *Gila… …   Wikipedia

  • Vertex cover — In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical… …   Wikipedia

  • Feedback vertex set — In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph.… …   Wikipedia

  • Feedback arc set — In graph theory, a directed graph may contain directed cycles, a one way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to… …   Wikipedia

Share the article and excerpts

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