Раз, Ран

Ран Раз

англ. Ran Raz

Род деятельности

информатик

Место работы

Принстонский университет
Институт Вейцмана

Награды и премии

Премия Эрдёша (2002)

Ран Раз (^{[Нет даты!]}) — израильский информатик, специалист по теории сложности вычислений. Известен работами по вероятностно проверяемым доказательствам (PCP) и интерактивным системам доказательств. Лауреат премии Эрдёша (2002).

Биография

Раз получил докторскую степень в Еврейском университете в Иерусалиме в 1992 году под руководством Ави Вигдерсона (тема диссертации: «Сложность коммуникации и нижние оценки схем»). С 2017 года является профессором Принстонского университета (ранее работал в Институте Вейцмана). В 2000—2001, 2002 и 2012 годах работал в Институте перспективных исследований.

Научная деятельность

Раз известен работами по вероятностно проверяемым доказательствам (PCP) и интерактивным системам доказательств, в частности Raz 1998 и Raz & Safra 1997. Его исследования в области теории сложности вычислений (сложность булевых и арифметических схем, коммуникационная сложность) связаны с доказательством нижних оценок сложности в различных вычислительных моделях. Он также изучал квантовые вычисления и случайность.

В 2018 году совместно с Авишаем Талем описал проблему Forrelation-Problem, которая разрешима квантовым компьютером в классе сложности BQP с разделением оракула, но неразрешима для классических компьютеров за полиномиальное время. Проблема заключается в том, чтобы определить, является ли одна из двух случайных последовательностей, сгенерированных двумя генераторами случайных чисел, преобразованием Фурье другой. Эта проблема была первоначально предложена Скоттом Ааронсоном в этом контексте. Модели с оракулом (чёрным ящиком) рассматриваются в теоретической информатике как предварительные этапы в процессе определения класса сложности проблемы.

В 1992 году он доказал совместно с Ави Вигдерсоном, что проблема совершенного паросочетания для монотонных вычислительных схем (то есть схем, содержащих только вентили И и ИЛИ, без НЕ) линейна по количеству узлов в графе. Таким образом, более быстрых решений проблемы не существует, если вентиль НЕ не разрешён.

Награды и признание

В 2004 году он получил одну из двух премий за лучшую статью на симпозиуме ACM Symposium on Theory of Computing (STOC) за Raz 2004 и премию за лучшую статью на конференции IEEE Conference on Computational Complexity (CCC) за Raz & Shpilka 2004. В 2008 году статья Moshkovitz & Raz 2008 получила премию за лучшую статью на симпозиуме IEEE Symposium on Foundations of Computer Science (FOCS).

В 2002 году Раз получил премию Эрдёша и в том же году — премию Морриса Л. Левинсона от Института Вейцмана. В 2002 году он был приглашённым докладчиком на Международном конгрессе математиков в Пекине (тема доклада: «$P\neq NP$, propositional proof complexity, and resolution lower bounds on the weak pigeonhole principle»).

Литература

• Raz, Ran; Tal, Avishay Oracle separation of BQP and PH // Proceedings of the 51st annual ACM SIGACT symposium on theory of computing. — 2019. — С. 13-23.

Ссылки

• Домашняя страница в Институте Вейцмана

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Раз, Ран», расположенная по адресу: — https://ru.ruwiki.ru/wiki/Раз,_Ран Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».