Просмотр кода страницы Регев, Одед

{{однофамильцы|Регев}}
{{Учёный
| научный руководитель = {{нп5|Йоси Азар||de|Yossi Azar}}
}}
'''Одед Регев''' ({{lang-he|עודד רגב}}; {{ВД-Преамбула}}) — израильско-американский учёный, [[Теоретическая информатика|теоретик информатики]] и [[математик]]. Лауреат [[Премия Гёделя|премии Гёделя]]. Профессор информатики в [[Курантовский институт математических наук|Курантовском институте]] при [[Нью-Йоркский университет|Нью-Йоркском университете]]<ref>[https://cs.nyu.edu/theory-group/faculty.html Faculty listing] {{Wayback|url=https://cs.nyu.edu/theory-group/faculty.html |date=20240301065136 }}, Courant Institute of Mathematical Sciences, accessed 2019-06-25.</ref>. Наиболее известен своими работами в области [[Криптография на решётках|решётчатой криптографии]], в частности постановкой задачи [[Обучение с ошибками|обучения с ошибками]] (LWE), [[криптоанализ]]ом схем {{нп5|GGH|||GGH signature scheme}} и [[NTRUSign]], а также разработкой нового [[квантовый алгоритм|квантового алгоритма]] по [[Факторизация|факторизации]] чисел, превосходящего по эффективности [[алгоритм Шора]]{{переход|#Алгоритм Регева}}.

== Биография ==
В 1995 году Одед Регев получил степень бакалавра наук. В 1997 году получил степень магистра наук и доктора философии. В 2001 году защитил докторскую диссертацию в [[Тель-Авивский университет|Тель-Авивском университете]] на тему «Планирование и балансировка нагрузки», его научным руководителем был {{нп5|Йоси Азар||de|Yossi Azar}}<ref>[http://www.cs.tau.ac.il/thesis/ School of Computer Science Thesis Repository] {{Wayback|url=http://www.cs.tau.ac.il/thesis/ |date=20190622134652 }}, Tel-Aviv University, accessed 2019-06-25.</ref><ref>https://www.aftau.org/2013-redesign/pages/tau/spotlights/blavatnik-school-of-computer-science#alumniSay. {{Dead link|date=February 2022}}</ref><ref>http://primage.tau.ac.il/libraries/theses/exeng/free/1509397_abe.pdf. {{Webarchive|url=https://web.archive.org/web/20190723222112/http://primage.tau.ac.il/libraries/theses/exeng/free/1509397_abe.pdf |date=2019-07-23 }}</ref>. До перехода в [[Курантовский институт математических наук|Курантовский институт]], в котором он работает сейчас, Одед преподавал в [[Тель-Авивский университет|Тель-Авивском университете]] и [[Высшая нормальная школа (Париж)|Высшей нормальной школе Парижа]]<ref>{{Cite web|url=https://www.simonsfoundation.org/people/oded-regev/|title=Oded Regev|date=2014-10-05|website=Simons Foundation|access-date=2023-12-26|archive-date=2024-02-24|archive-url=https://web.archive.org/web/20240224153143/https://www.simonsfoundation.org/people/oded-regev/|url-status=live}}</ref>.

== Научная работа ==
Регев проделал обширную работу в теории [[Решётка (геометрия)|решёток]] и [[Криптография|криптографии]]. Стал известен после постановки задачи [[Обучение с ошибками|обучения с ошибками]] ({{lang-en|Learning with errors, LWE}}), за которую получил [[Премия Гёделя|премию Гёделя]]<ref>{{Cite web |url=http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize |title=Источник |access-date=2023-12-26 |archive-date=2018-10-05 |archive-url=https://web.archive.org/web/20181005033058/http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize |url-status=live }}</ref>.

Работа Регева положила начало революции в криптографии, как в теории, так и на практике. С теоретической точки зрения LWE послужил простой и в то же время универсальной основой практически для любого типа криптографических объектов, которые только можно вообразить, а также для многих из них, которые до недавнего времени были немыслимы и которые до сих пор не имеют известных конструкций без LWE. С практической точки зрения LWE и его прямые потомки лежат в основе нескольких эффективных реальных криптосистем.

Другими влиятельными работами Регева являются [[криптоанализ]] схем {{нп5|GGH|||GGH signature scheme}} и [[NTRUSign]] в совместной работе с Фонгом К. Нгуеном, за которые они получили награду на Eurocrypt в 2006 году, а также постановка проблемы {{нп5|Кольцевое обучение с ошибками|кольцевого обучения с ошибками||Ring learning with errors}} для [[Постквантовая криптография|постквантовой криптографии]] в совместной работе с Крисом Пейкертом и Вадимом Любашевским и доказательство обратной [[Теорема Минковского о выпуклом теле|теоремы Минковского о выпуклом теле]] и исследование её приложений в совместных работах со своим учеником Ноем Стивенсом-Давидовицем и его бывшим постдоком Дэниелом Дадушем<ref>{{Cite web|url=https://www.iacr.org/cryptodb/data/bestpapers.php|title=IACR Publication Awards|website=www.iacr.org}}</ref><ref name="NguyenRegev2008">{{cite journal|last1=Nguyen|first1=Phong Q.|last2=Regev|first2=Oded|title=Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures|journal=Journal of Cryptology|volume=22|issue=2|year=2008|pages=139–160|issn=0933-2790|doi=10.1007/s00145-008-9031-0|s2cid=2164840|doi-access=free}}</ref><ref name="LyubashevskyPeikert2010">{{cite book|last1=Lyubashevsky|first1=Vadim|last2=Peikert|first2=Chris|last3=Regev|first3=Oded|title=Advances in Cryptology – EUROCRYPT 2010|chapter=On Ideal Lattices and Learning with Errors over Rings|series=Lecture Notes in Computer Science|volume=6110|year=2010|pages=1–23|issn=0302-9743|doi=10.1007/978-3-642-13190-5_1|isbn=978-3-642-13189-9}}</ref><ref>{{citation
 | author1-link = 
 | last1 = Regev | first1 = Oded
 | last2 = Stephens-Davidowitz | first2 = Noah
 | title = A reverse Minkowski theorem
 | series = Annual ACM SIGACT Symposium on Theory of Computing
 | year = 2017
 | pages = 941–953
 | place = Montreal, Quebec, Canada
| arxiv = 1611.05979
 }}</ref><ref name="DadushRegev2016">{{cite book|last1=Dadush|first1=Daniel|last2=Regev|first2=Oded|title=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)|chapter=Towards Strong Reverse Minkowski-Type Inequalities for Lattices|year=2016|pages=447–456|doi=10.1109/FOCS.2016.55|arxiv=1606.06913|isbn=978-1-5090-3933-3|s2cid=16828584}}</ref>.

Помимо работ по криптографии, Регев также внёс вклад во многие другие области теоретической информатики и математики, такие как [[квантовые вычисления]], [[коммуникационная сложность]], [[сложность аппроксимации]], {{нп5|онлайн-алгоритмы|||Online algorithm}}, [[комбинаторика]], [[теория вероятностей]] и [[снижение размерности]]. Недавно он также заинтересовался вопросами биологии, в частности [[сплайсинг РНК|сплайсингом РНК]]<ref>{{Cite web|url=https://cims.nyu.edu/~regev/.|title=Oded Regev|access-date=2023-12-26|archive-date=2024-01-04|archive-url=https://web.archive.org/web/20240104223751/https://cims.nyu.edu/~regev/|url-status=live}}</ref><ref>{{Cite web|url=https://scholar.google.com/citations?user=3-gk0ioAAAAJ&hl=en&oi=ao|title=Oded Regev|website=scholar.google.com|access-date=2023-12-26|archive-date=2023-10-19|archive-url=https://web.archive.org/web/20231019065901/https://scholar.google.com/citations?user=3-gk0ioAAAAJ&hl=en&oi=ao|url-status=live}}</ref>.

Регев — заместитель главного редактора журнала «Теория вычислений», а также соучредитель и организатор серии онлайн-семинаров TCS+<ref>[http://theoryofcomputing.org/editors.html List of editors] {{Wayback|url=http://theoryofcomputing.org/editors.html |date=20220618203537 }}, Theory of Computing, accessed 2019-06-25.</ref><ref>{{Cite web|url=https://sites.google.com/site/plustcs/|title=TCS+|website=sites.google.com|access-date=2023-12-26|archive-date=2023-03-22|archive-url=https://web.archive.org/web/20230322153728/https://sites.google.com/site/plustcs/|url-status=live}}</ref>.

=== Алгоритм Регева ===
В августе 2023 года Регев опубликовал новый [[квантовый алгоритм]] по [[Факторизация|факторизации]] чисел, превосходящий по эффективности [[алгоритм Шора]]<ref name="автоссылка1">{{Cite journal |last=Regev |first=Oded |date=2023 |title=An Efficient Quantum Factoring Algorithm |arxiv=2308.06572}}</ref><ref name="автоссылка2">{{Cite report |url=https://www.science.org/content/article/surprising-and-supercool-quantum-algorithm-offers-faster-way-hack-internet-encryption |title='Surprising and super cool.' Quantum algorithm offers faster way to hack internet encryption |date=2023-09-19 |doi=10.1126/science.adk9418 |language=en |access-date=2023-12-26 |archive-date=2023-12-19 |archive-url=https://web.archive.org/web/20231219050708/https://www.science.org/content/article/surprising-and-supercool-quantum-algorithm-offers-faster-way-hack-internet-encryption |url-status=live }}</ref><ref name="автоссылка3">{{Cite web |last=Brubaker |first=Ben |date=2023-10-17 |title=Thirty Years Later, a Speed Boost for Quantum Factoring |url=https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/ |access-date=2023-10-18 |website=Quanta Magazine |language=en |archive-date=2023-12-22 |archive-url=https://web.archive.org/web/20231222020946/https://www.quantamagazine.org/thirty-years-later-a-speed-boost-for-quantum-factoring-20231017/ |url-status=live }}</ref>.

Регев разработал свой новый алгоритм, дополнив алгоритм Шора методами из [[Многомерная криптография|раздела криптографии, занимающегося многомерной геометрией]]. Ему удалось обобщить алгоритм на произвольное количество измерений, а не только на два, в результате чего для факторизации чисел [[Квантовый компьютер|квантовому компьютеру]] требуется гораздо меньше логических шагов. Специалисты по [[квантовые вычисления|квантовыми вычислениями]] отмечают, что удивительно и неожиданно, что спустя 30 лет кто-то смог качественно улучшить алгоритм Шора<ref name="автоссылка1" /><ref name="автоссылка2" /><ref name="автоссылка3" />.

Алгоритм Регева использует <math>\sim O(n^{3/2})</math> [[Квантовый вентиль|квантовых вентилей]], что более эффективно, чем в алгоритме Шора, в котором используется <math>\sim O(n^{2})</math> квантовых вентилей, хотя для реализации алгоритма Регева требуется потребуется больше [[кубит]]ов [[квантовая память|квантовой памяти]] <math>\sim O(n^{3/2})</math>, в то время как а алгоритме Шора их используется <math>\sim O(n)\ </math>.

Позже был предложен вариант оптимизации алгоритма Регева, в котором было показано, что можно уменьшить пространство используемой квантовой памяти примерно до того же уровня, что и в алгоритме Шора<ref>{{Cite journal |last1=Ragavan |first1=Seyoon |last2=Vaikuntanathan |first2=Vinod |date=2023 |title=Optimizing Space in Regev's Factoring Algorithm |arxiv=2310.00899}}</ref>.

== Награды и премии ==
* Премия Криля (2005)<ref>http://www.wolffund.org.il/index.php?dir=site&page=winners&cs=565 {{Dead link|date=February 2022}}</ref>
* Премия Eurocrypt (2006)
* [[Премия Гёделя]] (2018)<ref>{{Cite web |url=http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize |title=2018 Gödel Prize |access-date=2018-04-12 |archive-date=2018-10-05 |archive-url=https://web.archive.org/web/20181005033058/http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize |deadlink=no }}</ref>
* {{нп5|Simons Investigator}} (2019)<ref>{{Cite web|url=https://www.simonsfoundation.org/grant/simons-investigators/|title=Simons Investigators|date=2018-07-10|website=Simons Foundation|access-date=2023-12-26|archive-date=2023-12-16|archive-url=https://web.archive.org/web/20231216045742/https://www.simonsfoundation.org/grant/simons-investigators/|url-status=live}}</ref>
* Серебряный профессор (2022)<ref>{{Cite web |url=https://as.nyu.edu/people/silverprofessors.html |title=The Silver Professors |access-date=2023-12-26 |archive-date=2023-12-22 |archive-url=https://web.archive.org/web/20231222202211/https://as.nyu.edu/people/silverprofessors.html |url-status=live }}</ref>

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://cims.nyu.edu/~regev/ Сайт Регева]
* {{YouTube|g7ih6rHdw3M|Computer Science - 2023's Biggest Breakthroughs{{ref-en}}}}.

{{вс}}
{{Лауреаты премии Гёделя}}

[[Категория:Учёные в области информатики Израиля]]
[[Категория:Математики Израиля]]
[[Категория:Криптографы Израиля]]
[[Категория:Сильверовские профессора]]
[[Категория:Преподаватели Нью-Йоркского университета]]
[[Категория:Выпускники Тель-Авивского университета]]
[[Категория:Лауреаты премии Гёделя]]
[[Категория:Simons Investigators]]
[[Категория:Математики США]]