Ran Raz

Ran Raz 2011

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

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

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

Schriften

• mit Shmuel Safra A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proc. STOC (ACM Symp. Theoretical Computer Science) 1997, S. 475–484
• A parallel repetition theorem, SIAM Journal on Computing 27, 1998, 763–803
• Multi-linear formulas for permanent and determinant are of super-polynomial size, Proc. STOC 2004, 633–641
• mit Amir Shpilka Deterministic polynomial identity testing in non commutative models, Proc. CCC (Conference on Computational Complexity) 2004, 215–222
• mit Dana Moshkovitz Two query PCP with sub-constant error, Proc. FOCS (IEEE Symp. Foundations Computer Science) 2008, 314–323
• mit Shira Kritchman The surprise examination paradox and the second incompleteness theorem, Notices AMS, Dezember 2011, Online

Weblinks

• Homepage