Ran Raz

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].

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.

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: « ${\displaystyle P\neq NP}$, propositional proof complexity, and resolution lower bounds on the weak pigeonhole principle »).

• Ran Raz et Avi Wigderson, « Monotone circuits for matching require linear depth », Journal of the ACM, vol. 39,‎ 1992, p. 736–744.
• Ran Raz et Avishay Tal, « Oracle separation of BQP and PH », Proceedings of the 51st annual ACM SIGACT symposium on theory of computing,‎ 2019, p. 13-23 (lire en ligne).
• Ran Raz et Shmuel Safra, « A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP », Symposium on Theory of Computing,‎ 1997, p. 475–484 (ISBN 978-0-89791-888-6, DOI 10.1145/258533.258641, CiteSeer^x 10.1.1.34.6957).
• Ran Raz, « A parallel repetition theorem », SIAM Journal on Computing, vol. 27, n^o 3,‎ 1998, p. 763–803 (DOI 10.1137/S0097539795280895).
• Ran Raz, « Multi-linear formulas for permanent and determinant are of super-polynomial size », Symposium on Theory of Computing,‎ 2004, p. 633–641 (ISBN 978-1-58113-852-8, DOI 10.1145/1007352.1007353).
• Ran Raz et Amir Shpilka, « Deterministic polynomial identity testing in non commutative models », Conference on Computational Complexity,‎ 2004, p. 215–222 (ISBN 978-0-7695-2120-6, DOI 10.1109/CCC.2004.1313845).
• Dana Moshkovitz et Ran Raz, « Two query PCP with sub-constant error », Symposium on Foundations of Computer Science,‎ 2008, p. 314–323 (ISBN 978-0-7695-3436-7, DOI 10.1109/FOCS.2008.60).

• Ressources relatives à la recherche :
  • (en) Digital Bibliography & Library Project
  • (en) Mathematics Genealogy Project
• Page d'accueil au Weizmann Institute

• Portail de l'informatique théorique