Ran Raz

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, Kommunikations-Komplexität) war der Beweis unterer Schranken für die Komplexität in verschiedenen Berechnungsmodellen. Er befasste sich auch mit Quantencomputern und Zufälligkeit.

2002 erhielt er den Erdős-Preis und er erhielt den Morris L. Levinson Prize des Weizmann Instituts.

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