Steven Rudich

Steven Rudich
une illustration sous licence libre serait bienvenue
Biographie
Naissance
Voir et modifier les données sur Wikidata (62 ans)
Nationalité
américaineVoir et modifier les données sur Wikidata
Formation
Activité
InformaticienVoir et modifier les données sur Wikidata
Autres informations
A travaillé pour
Directeur de thèse
Manuel BlumVoir et modifier les données sur Wikidata
Distinction
Prix Gödel ()Voir et modifier les données sur Wikidata

modifier - modifier le code - modifier WikidataDocumentation du modèle

Steven Rudich, né le , est un informaticien théoricien américain qui travaille en théorie de la complexité, cryptographie et combinatoire.

Rudich obtient en 1989 un Ph. D. à l'université de Californie à Berkeley sous la direction de Manuel Blum (« Limits on the Provable Consequences of One-Way Functions »[1]). Il est depuis le début des années 1990 professeur d'informatique à l'université Carnegie-Mellon.

Prix Gödel

En 2007 il reçoit, avec Alexandre Razborov, le prix Gödel[2]. pour leur article Natural Proof, où il est démontré que les méthodes de minoration employées en complexité des circuits ne sont probablement pas adaptés pour résoudre le problème P = NP[3],[4]. Pour cela, ils mettent en évidence des propriétés communes à toutes les preuves de minoration de complexité des circuits, et ils appellent les démonstrations avec ces propriétés des preuves naturelles. Ils montrent qu'une preuve naturelle du problème P=NP impliquerait qu'il n'existe pas de générateurs pseudo-aléatoires, existence qui portant est généralement admise. Ils démontrent enfin qu'il n'existe pas de preuve natural proof pour établir que certains problèmes cryptographiques connus (comme la factorisation d'entiers naturels ou le problème du logarithme discret) sont NP-difficiles. Rudich est aussi coauteur d'un article qui prouve que les problèmes NP-complets le reste même sous une réduction de classe AC0 ou NC0[5].

Andrew's Leap

Rudich organise depuis 1991 un programme d'enseignement en été qui s'adresse à des élèves des high schools. Les cours traitent de divers aspects d'informatique théorique le matin, et sont complétés par des activités facultatives l'après-midi: robotique, programmation, mathématiques. L'admission est sur sélection par examen appelé interest test. Ce programme d'été, d'une durée de sept semaines, appelé auparavant Andrew's Leap, s'appelle maintenant Leap@CMU.

Prestidigitateur

Rudich est également prestidigitateur amateur[6].

Notes et références

  1. ↑ (en) « Steven Rudich », sur le site du Mathematics Genealogy Project.
  2. ↑ (en) « EATCS: Gödel Prize - 2007 »
  3. ↑ Alexandre Razborov et Steven Rudich, « Natural Proof », Journal of Computer and System Sciences, vol. 55,‎ , p. 24-35.
  4. ↑ Alexandre Razborov et Steven Rudich, « Natural Proof », Proc. 26th Int. ACM Symposium on the Theory of Computing (STOC),‎ , p. 204-213 (lire en ligne).
  5. ↑ Manindra Agrawal, Eric Allender et Steven Rudich, « Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem », Journal of Computer and System Sciences, vol. 57, no 2,‎ , p. 127–143 (DOI 10.1006/jcss.1998.1583).
  6. ↑ Steven Rudich Magician Scholar.
  • (de)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en allemand « Steven Rudich » (voir la liste des auteurs) et en anglais « Steven Rudich » (voir la liste des auteurs).

Liens externes

  • Page personnelle Carnegie Mellon.
  • Ressources relatives à la rechercheVoir et modifier les données sur Wikidata :
    • Digital Bibliography & Library Project
    • Google Scholar
    • Mathematics Genealogy Project
  • Notices d'autoritéVoir et modifier les données sur Wikidata :
    • VIAF
    • ISNI
    • BnF (données)
    • IdRef
    • LCCN
    • GND
    • Pays-Bas
    • Israël
    • NUKAT
    • WorldCat
v · m
Lauréats du prix Gödel
  • icône décorative Portail de l'informatique théorique