Ran Raz
Modèle:Infobox Biographie2 Ran Raz est un informaticien israélien spécialiste de théorie de la complexité.
Biographie
Raz a obtenu son doctorat à l'Université hébraïque de Jérusalem en 1992 avec Avi Wigderson (Communication Complexity and Circuit Lower Bounds[1]. Il est professeur à l'Université de Princeton depuis 2017 (auparavant à l'Institut Weizmann[2]). En 2000-2001, 2002 et 2012, il était à l'Institute for Advanced Study[3].
Travaux
Il est connu pour ses travaux sur les preuves vérifiables de manière probabiliste (PCP) et les systèmes de preuves interactives, notamment Modèle:Harvsp et Modèle:Harvsp. Ses travaux en théorie de la complexité (complexité des circuits booléens et arithmétiques, complexité des communications) concernent la preuve de bornes inférieures de complexité dans divers modèles de calcul. Il a également étudié l'informatique quantique et le hasard.
En 2018, il a décrit, avec Avishay Tal, un problème appelé le Forrelation-Problem qui est résoluble par calculateur quantique dans la classe de complexité BQP avec séparation d'oracle mais ne l'est pas pour les ordinateurs classiques en temps polynomiale. Ce problème consiste à décider, étant donné deux suites aléatoires engendrées par deux générateurs aléatoires, si l'une est la transformée de Fourier de l'autre. Ce problème a été initialement proposée par Scott Aaronson dans ce cadre[4]Modèle:,[5]. Les modèles à oracle (boîte noire) sont considérés, en informatique théorique, comme des étapes préliminaires dans la démarche de détermination de la classe de complexité d'un problème.
En 1992, il a prouvé avec Avi Wigderson[6] que le problème du couplage parfait pour les circuits de calcul monotones (c'est-à-dire ceux avec uniquement des portes ET et OU, sans NON) est linéaire en le nombre de nœuds dans le graphe. Il n'y a donc pas de solutions plus rapides du problème si la porte NOT n'est pas autorisée.
Distinctions
En 2004, il a reçu l'un des deux prix du meilleur article de l'ACM Symposium on Theory of Computing (STOC) pour Modèle:Harvsp[7] et le prix du meilleur article de la Conference on Computational Complexity (CCC) de l'IEEE pour Modèle:Harvsp[8]. En 2008, la communication Modèle:Harvsp a reçu le prix du meilleur article au Symposium on Foundations of Computer Science (FOCS) de l'IEEE[9]
En 2002, Raz a reçu le prix Erdős et il a reçu la même année le prix Morris L. Levinson de l'Institut Weizmann. En 2002, il a été conférencier invité au Congrès international des mathématiciens à Pékin ( titre de sa conférence: « , propositional proof complexity, and resolution lower bounds on the weak pigeonhole principle »).
Publications (sélection)
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
- Modèle:Article.
Liens externes
- Page d'accueil au Weizmann Institute
Notes et références
Modèle:Références Modèle:Portail
- ↑ Modèle:MathGenealogy.
- ↑ Modèle:Lien web
- ↑ « Ran Raz à l'IAS ».
- ↑ Modèle:Harvsp.
- ↑ Modèle:Lien web.
- ↑ Modèle:Harvsp.
- ↑ Proc. STOC 2004: « STOC 2004 Conference Awards », page x. [1]. Un des deux articles primés.
- ↑ Proc. CCC 2004 « Awards », page x. [2].
- ↑ Proc. FOCS 2008 « Foreword », page xii, page xii. [3].