Ran Raz

Ran Raz is an Israeli computer scientist who is particularly concerned with complexity theory.

Raz in 1992 received his doctorate at the Hebrew University in Avi Wigderson (Communication Complexity and Lower Bounds Circuit ). He is a professor at the Weizmann Institute. 2000/2001, 2002 and 2012, he was at the Institute for Advanced Study.

He is known for work on probabilistically checkable proofs (PCP) and interactive proof systems. One focus of his work in complexity theory ( Boolean and Arithmetic circuit complexity, communication complexity) was the proof of lower bounds for the complexity of various models of computation. He also dealt with quantum computers and randomness.

In 2002 he received the Erdős Prize and he received the Morris L. Levinson Prize from the Weizmann Institute. In 2002 he was invited speaker at the International Congress of Mathematicians in Beijing (, propositional proof complexity, and resolution lower bounds on the weak pigeonhole principle).

Writings

  • With 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, pp. 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
  • With Amir Shpilka Deterministic polynomial identity testing in non commutative models, Proc. CCC ( Conference on Computational Complexity ) 2004, 215-222
  • Dana Moshkovitz Two query PCP with sub -constant error, Proc. FOCS (IEEE Symp Foundations Computer Science) 2008, 314-323
  • With Shira Kritchman The surprise examination paradox and the second incompleteness theorem, Notices AMS, December 2011, Online
672633
de