Steven Rudich

Steven Rudich

Steven Rudich (* 4. Oktober 1961) ist ein US-amerikanischer Informatiker, der sich mit Komplexitätstheorie, Kryptographie und Kombinatorik beschäftigt.

Rudich promovierte 1989 an der University of California, Berkeley bei Manuel Blum (Limits on the Provable Consequences of One-Way Functions) und ist seit Anfang der 1990er Jahre Professor für Informatik an der Carnegie Mellon University.

2007 erhielt er mit Alexander Razborov den Gödel-Preis für Arbeit Natural Proof, die zeigte, das Schaltkreiskomplexitätsmethoden zur Bestimmung einer Untergrenze der Komplexität eines Problems wahrscheinlich nicht geeignet sind, das P=NP-Problem zu lösen.[1]. Dabei isolieren sie eine gemeinsame Eigenschaft dieser Schaltkreiskomplexitäts-Verfahren, die sie Natural Proof nennen. Sie zeigten, das ein Natural Proof Beweis für das P=NP Problem zur Folge hätte, dass keine Pseudozufallsgeneratoren existieren, was aber allgemein angenommen wird. Weiter zeigten sie, dass es keine Natural Proof Beweise dafür gibt, dass einige bekannte kryptographische Probleme NP-schwer sind (wie die Faktorisierung ganzer Zahlen oder das Problem des diskreten Logarithmus). Die Arbeit von Razborov und Rudich war ein wichtiger Fortschritt im P=NP Problem, einem der Clay Probleme, der zeigte, das man in neuen Richtungen nach der Lösung suchen musste.

Er ist Herausgeber des Journal of Cryptography.

Rudich ist Amateur-Zauberer.

Weblinks

Einzelnachweise

  1. Razborov, Rudich Natural Proof, Journal of Computer and System Sciences, Bd. 55, 1997, S. 24-35 und Proc. 26. Int. ACM Symposium on the Theory of Computing (STOC), 1994, S.204, Online hier Postcript Datei

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • Steven Rudich — (born Oct 4 1961) is a professor in the Carnegie Mellon School of Computer Science. In 1994, He and Alexander Razborov proved that a large class of combinatorial arguments, dubbed natural proofs were unlikely to answer many of the important… …   Wikipedia

  • Steven Rudich — (n. 4 de octubre, 1961) es un profesor estadounidense de la Escuela de Ciencias de la Computación de la Universidad Carnegie Mellon. En 1994 junto con Alexander Razborov demostró que una gran clase de argumentos combinatoriales, denominados… …   Wikipedia Español

  • Steven Ricks — Steve(n) L. Ricks (* 1969) ist ein US amerikanischer Komponist und Musikpädagoge. Ricks studierte nach einer Ausbildung als Posaunist an der Brigham Young University, der University of Illinois at Urbana Champaign und der University of Utah. Mit… …   Deutsch Wikipedia

  • Alexander Razborov — Naissance 16 février 1963 Domicile États Unis Nationalité …   Wikipédia en Français

  • 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

  • Премия Гёделя — (англ. Gödel Prize)  премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT (Special Interest Group on Algorithms and Computation Theory) и EATCS (European Association for… …   Википедия

  • Natural proof — In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense natural , it can be shown (assuming a widely believed conjecture… …   Wikipedia

  • Liste de personnes par nombre d'Erdős — Voici une liste non exhaustive de personnes ayant un nombre d Erdős de 0, 1 ou 2. Sommaire 1 #0 2 #1 3 #2 4 Référence …   Wikipédia en Français

  • Manuel Blum — Born April 26, 1938 (1938 04 26) (age 73) Caracas, Venezuela Residence Pittsburgh …   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

Share the article and excerpts

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