Accueil🇫🇷Chercher

Ran Raz

Ran Raz est un informaticien israélien spécialiste de théorie de la complexité.

Ran Raz
Autres informations
A travaillé pour
Directeurs de thèse
Avi Wigderson, Michael Ben-Or (d)
Distinctions
Prix Erdős ()
Michael Bruno Memorial Award (d) ()

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 Raz (1998) et Raz et Safra (1997). 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] - [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 Raz (2004)[7] et le prix du meilleur article de la Conference on Computational Complexity (CCC) de l'IEEE pour Raz et Shpilka (2004)[8]. En 2008, la communication Moshkovitz et Raz (2008) 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)

Liens externes

Notes et références

  1. (en) « Ran Raz », sur le site du Mathematics Genealogy Project.
  2. (en) « Raz, Weinberg Deepen Faculty's Leadership in Critical Areas | Computer Science Department at Princeton University », sur www.cs.princeton.edu (consulté le )
  3. « Ran Raz à l'IAS ».
  4. Raz et Tal 2019.
  5. Kevin Hartnett, « Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve », Quanta Magazine, .
  6. Raz et Wigderson 1992.
  7. Proc. STOC 2004: « STOC 2004 Conference Awards », page x. . Un des deux articles primés.
  8. Proc. CCC 2004 « Awards », page x. .
  9. Proc. FOCS 2008 « Foreword », page xii, page xii. .
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.