Ran Raz (Hebrew: רָן רָז) is an Israeli computer scientist who works in the field of computational complexity theory. He was a professor in the Department of Mathematics and Computer Science at the Weizmann Institute before becoming a professor of computer science at Princeton University.
Raz earned his Ph.D. from the Hebrew University of Jerusalem in 1992 with advisors Avi Wigderson and Michael Ben-Or.
Raz is well known for his research on interactive proof systems. His two most-cited papers are "Raz (1998)" on multi-prover interactive proofs and "Raz & Safra (1997)" on probabilistically checkable proofs.
Raz received the Erdős Prize in 2002. In 2004, he won the Best Paper Award at the ACM Symposium on Theory of Computing for "Raz (2004)," and the Best Paper Award at the IEEE Conference on Computational Complexity for "Raz & Shpilka (2004)." In 2008, the paper "Moshkovitz & Raz (2008)" received the Best Paper Award at the IEEE Symposium on Foundations of Computer Science (FOCS).
Selected publications
- Raz, Ran; Safra, Shmuel (1997), "A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP," Proceedings of the STOC 1997 conference, pp. 475–484, CiteSeerX 10.1.1.34.6957, doi: 10.1145/258533.258641, ISBN 978-0-89791-888-6, S2CID 15457604.
- Raz, Ran (1998), "A parallel repetition theorem," SIAM Journal on Computing, 27 (3): 763–803, CiteSeerX 10.1.1.35.6859, doi: 10.1137/S0097539795280895.
- Raz, Ran (2004), "Multi-linear formulas for permanent and determinant are of super-polynomial size," Proceedings of the STOC 2004 conference, pp. 633–641, CiteSeerX 10.1.1.2.9694, doi: 10.1145/1007352.1007353, ISBN 978-1-58113-852-8, S2CID 1297877.
- Raz, Ran; Shpilka, Amir (2004), "Deterministic polynomial identity testing in non commutative models," Proceedings of the CCC 2004 conference, pp. 215–222, CiteSeerX 10.1.1.104.293, doi: 10.1109/CCC.2004.1313845, ISBN 978-0-7695-2120-6.
- Moshkovitz, Dana; Raz, Ran (2008), "Two query PCP with sub-constant error," Proceedings of the FOCS 2008 conference, pp. 314–323, CiteSeerX 10.1.1.140.2111, doi: 10.1109/FOCS.2008.60, ISBN 978-0-7695-3436-7.