Ran Raz

from Wikipedia, the free encyclopedia
Ran Raz 2011

Ran Raz is an Israeli computer scientist who specializes in complexity theory.

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

He is known for his work on Probabilistically Checkable Proofs (PCP) and Interactive Evidence Systems . A focus of his work in complexity theory (Boolean and arithmetic circuit complexity, communication complexity) was the proof of the lower bounds for the complexity in various calculation models. He also looked at quantum computers and randomness.

In 2018 he found with Avishai Tal a problem that can be solved for quantum computers (complexity class BQP ), in a certain sense (oracle separation) but not for classical computers ( polynomial time hierarchy PH), the forrelation problem. With two random sequences - generated by two random generators - you have to decide whether one is the Fourier transform of the other.

In 2002 he was awarded the Erdős Prize and the Weizmann Institute's Morris L. Levinson Prize. 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).

Fonts

  • 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, 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
  • with 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

Web links

Individual evidence

  1. ^ Mathematics Genealogy Project
  2. ↑ IAS
  3. ^ Raz, Tal: Oracle separation of BQP and PH, 2018, online
  4. ↑ Kevin Hartnett, Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve, Quanta Magazine , June 21, 2018
personal data
SURNAME Raz, Ran
BRIEF DESCRIPTION Israeli computer scientist
DATE OF BIRTH 20th century