然·拉茨

然·拉茨 (英語：Ran Raz, 希伯來語：רָן רָז) 是一位專長於計算複雜性理論的計算機科學家。他現在是以色列魏茨曼科學研究學院數學與計算機科學學部的教授。

然·拉茨最著名的工作是交互式證明系統。他的引用數最多的兩篇論文是：一篇Raz (1998)是關於多證明者交互證明；另一篇Raz & Safra (1997)是關於概率可驗證證明.^[1]

然·拉茨曾於2002年獲得保羅·埃爾德什獎(Erdős Prize)。他也曾多次獲得理論計算機領域頂級會議的最佳論文獎項。他的工作Raz (2004)^[2]獲得2004年STOC的最佳論文獎。他的工作 Raz & Shpilka (2004)獲得2004年IEEE CCC的最佳論文獎^[3]。他的工作Moshkovitz & Raz (2008)獲得2008年IEEE FOCS^[4]的最佳論文獎。

著名論文

• Raz, Ran; Safra, Shmuel, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proc. STOC 1997: 475–484, 1997, ISBN 0-89791-888-6, doi:10.1145/258533.258641.
• Raz, Ran, A parallel repetition theorem, SIAM Journal on Computing, 1998, 27 (3): 763–803, doi:10.1137/S0097539795280895.
• Raz, Ran, Multi-linear formulas for permanent and determinant are of super-polynomial size, Proc. STOC 2004: 633–641, 2004, ISBN 1-58113-852-0, doi:10.1145/1007352.1007353.
• Raz, Ran; Shpilka, Amir, Deterministic polynomial identity testing in non commutative models, Proc. CCC 2004: 215–222, 2004, ISBN 0-7695-2120-7, doi:10.1109/CCC.2004.1313845.
• Moshkovitz, Dana; Raz, Ran, Two query PCP with sub-constant error, Proc. FOCS 2008: 314–323, 2008, ISBN 978-0-7695-3436-7, doi:10.1109/FOCS.2008.60.