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.. Il est professeur à l'Université de Princeton depuis 2017 (auparavant à l'Institut Weizmann). En 2000-2001, 2002 et 2012, il était à l'Institute for Advanced Study« Ran Raz à l'IAS »..
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 et . 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é par Scott Aaronson dans ce cadre... 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. 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 Proc. STOC 2004: « STOC 2004 Conference Awards », page x. . Un des deux articles primés. et le prix du meilleur article de la Conference on Computational Complexity (CCC) de l'IEEE pour Proc. CCC 2004 « Awards », page x. .. En 2008, la communication a reçu le prix du meilleur article au Symposium on Foundations of Computer Science (FOCS) de l'IEEEProc. FOCS 2008 « Foreword », page xii, page xii. .
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)
. . . . . . .
Liens externes
Page d'accueil au Weizmann Institute
Notes et références
Catégorie:Naissance en décembre 1966 Catégorie:Informaticien Catégorie:Lauréat du prix Erdős