Steven Rudich

Steven Rudich (4 octobre 1961 - 29 octobre 2024^[1]) est un informaticien théoricien américain, professeur d'informatique à l'université Carnegie-Mellon, spécialiste de théorie de la complexité, cryptographie et combinatoire.

Steven Rudich

Biographie

Naissance	4 octobre 1961
Décès	29 octobre 2024 (à 63 ans)
Nationalité	américaine
Formation	Northfield Mount Hermon School (en) Université Wesleyenne Université de Californie à Berkeley
Activité	Informaticien

Autres informations

A travaillé pour	Université Carnegie-Mellon
Directeur de thèse	Manuel Blum
Distinction	Prix Gödel (2007)

modifier - modifier le code - modifier Wikidata

Biographie

Steven Rudich est le fils d'universitaires américains spécialistes de littérature française. Son père Norman Rudich est professeur à l'université Wesleyenne^[1].

Il 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 »^[2]). Au début des années 1990, il devient professeur d'informatique à l'université Carnegie-Mellon.

Il est atteint de la maladie de Stargardt, qui le rend aveugle, ainsi que de la maladie de Huntington^[1].

Prix Gödel

En 2007 il reçoit, avec Alexandre Razborov, le prix Gödel^[3]. 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^[4],[5]. 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 AC⁰ ou NC^0[6].

Andrew's Leap

Steven Rudich fonde en 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^{[7],[source secondaire souhaitée]}.

Prestidigitateur

Steven Rudich est également prestidigitateur amateur^[8].