Ran Raz

Ran Raz ist ein israelischer Informatiker, der sich insbesondere mit Komplexitätstheorie befasst.

Ran Raz 2011

Raz wurde 1992 an der Hebräischen Universität bei Avi Wigderson promoviert (Communication Complexity and Circuit Lower Bounds).[1] Er ist Professor am Weizmann-Institut. 2000/2001, 2002 und 2012 war er am Institute for Advanced Study.[2]

Er ist bekannt für Arbeiten zu Probabilistically Checkable Proofs (PCP) und interaktiven Beweissystemen. Ein Schwerpunkt seiner Arbeit in Komplexitätstheorie (boolesche und arithmetische Schaltkreiskomplexität, Kommunikationskomplexität) war der Beweis unterer Schranken für die Komplexität in verschiedenen Berechnungsmodellen. Er befasste sich auch mit Quantencomputern und Zufälligkeit.

2018 fand er mit Avishay Tal ein Problem, das für Quantencomputer lösbar ist in der Komplexitätsklasse BQP, in einem gewissen Sinn (Orakel-Separiertheit) aber nicht für klassische Computer (Polynomialzeithierarchie PH), das Forrelation-Problem. Es besteht darin, bei zwei Zufallsfolgen – erzeugt von zwei Zufallsgeneratoren – zu entscheiden, ob die eine die Fouriertransformation der anderen ist und wurde ursprünglich von Scott Aaronson für diesen Problemkreis vorgeschlagen.[3][4] Orakel (Black Box) Modelle werden in der theoretischen Informatik als Vorstufen für die Lösung des eigentlichen Problems der Stellung einzelner Komplexitätsklassen zueinander untersucht.

1992 bewies er mit Avi Wigderson,[5] dass das Perfect-Matching-Problem für Berechnung mit monotonen Schaltkreisen (also solchen nur mit AND und OR-Gatter, ohne NOT) linear in der Anzahl der Knoten des Graphen ist. Es gibt also bei Nicht-Zulassung der NOT-Gatter prinzipiell keine „schnellen“ Lösungen des Problems.

2002 erhielt er den Erdős-Preis und er erhielt den Morris L. Levinson Prize des Weizmann-Instituts. 2002 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Peking (${\displaystyle P\neq NP}$, propositional proof complexity, and resolution lower bounds on the weak pigeonhole principle).