עודד רגב (מדען מחשב)

עודד רגב
	אין תמונה חופשית
לידה	1978 (בן 46 בערך)
מקום לימודים	אוניברסיטת תל אביב
מנחה לדוקטורט	יוסי עזר
מוסדות	אוניברסיטת ניו יורק
תלמידי דוקטורט	ריקי רוזן, קלים יפרמנקו, Alexander Golovnev, אברהם בן-ארויה
פרסים והוקרה	פרס גדל (2018)

עודד רגב (נולד ב-1980 או 1979) הוא מדען מחשב ומתמטיקאי ישראלי-אמריקאי, פרופסור למדעי המחשב במכון קוראנט של אוניברסיטת ניו יורק. ידוע בעיקר בזכות עבודתו בהצפנה מבוססת סריג, ובמיוחד בשל תרומתו ללמידה עם שגיאות.

בשנת 2023 פרסם מאמר בשם 'אלגוריתם קוואנטי יעיל לפירוק לגורמים' שמייעל את אלגוריתם שור $\sim O(n^{3/2})$ שערים קוואנטים בלבד לעומת אלגוריתם שור המשתמש ב $\sim O(n^{2})$ .

ביוגרפיה

עודד רגב קיבל את שלושת תאריו באוניברסיטת תל אביב: תואר ראשון ב-1995, תואר שני ב-1997 ותואר דוקטור ב-2001, בגיל 21, על עבודה בהנחייתו של יוסי עזר, שכותרתה "תזמון ואיזון עומסים".^[1] מילא תפקידי סגל באוניברסיטת תל אביב ובאקול נורמל סופרייר לפני שהצטרף למכון קוראנט.

בשנת 2005 הוענק לו פרס קריל.^[2]

עבודתו

רגב ידוע בעיקר בזכות תרומתו ללמידה עם שגיאות (LWE), שעליה זכה בפרס גדל לשנת 2018.^[3] כאמור:

”עבודתו של רגב הובילה מהפכה בקריפטוגרפיה, הן בתיאוריה והן בפרקטיקה. מהצד התיאורטי, LWE שימש בסיס פשוט ועם זאת צדדי להפליא עבור כמעט כל סוג של אובייקט קריפטוגרפי שניתן להעלות על הדעת - יחד עם רבים שלא ניתן היה להעלות על הדעת עד לאחרונה, ושעדיין אין להם מבנים ידועים ללא LWE. לבסוף, LWE וכל מה שנגזר ממנה נמצאים בלב של כמה מערכות קריפטו יעילות בעולם האמיתי.”

העבודות המשפיעות ביותר של רגב על סריג כוללות את ניתוח הצפנה של סכימות החתימה GGH ו־NTRU בעבודה משותפת עם Phong Q. Nguyen, שעליה זכו בפרס המאמר הטוב ביותר ב-Eurocrypt 2006; הצגת בעיית לימוד הטבעת עם שגיאות בעבודה משותפת עם כריס פייקרט וואדים ליובאשבסקי; והוכחת ניגוד למשפט מינקובסקי ובחינת יישומיו בעבודות משותפות עם תלמידו נח סטפנס-דווידוביץ והפוסט-דוקטורנט לשעבר דניאל דדוש.^[4]^[5] ^[6]^[7]

בנוסף לעבודתו על סריג, רגב עוסק גם במספר רב של תחומים נוספים במדעי המחשב התאורטיים ובמתמטיקה. והכוללים בין היתר מחשוב קוונטי, מורכבות תקשורת, קשיות קירוב, אלגוריתמים מקוונים, קומבינטוריקה, הסתברות והפחתת מימד. לאחרונה הוא גם החל להתעניין בנושאים בביולוגיה, ובמיוחד שחבור RNA . ^[8]

רגב הוא בנוסף עורך שותף ראשי של כתב העת Theory of Computing , ^[9] מייסד ומארגן של סדרת הסמינרים המקוונת TCS+. ^[10]

באוגוסט 2023 פרסם מאמר^[11]^[12] המתאר אלגוריתם לפירוק לגורמים מספרים שלמים עם $\sim O(n^{3/2})$ שערים קוונטיים שיהיה יעיל יותר מהאלגוריתם של שור המשתמש ב $\sim O(n^{2})$ , אבל ידרוש יותר קיוביטים $\sim O(n^{3/2})$ של זיכרון לעומת זה של שור $\sim O(n)\$ . הוצעה שיטה חלופית ^[13] שיכולה לצמצם את מספר הקיוביטים לכמעט אותו הכמות.

קישורים חיצוניים

עודד רגב, באתר של מכון קוראנט (באנגלית)
עודד רגב, באתר פרויקט הגנאלוגיה במתמטיקה
עודד רגב, באתר dblp
עודד רגב, באתר גוגל סקולר
עודד רגב, באתר IEEE

הערות שוליים

^ Regev, Oded. "Scheduling and Load Balancing" (PDF). Tel Aviv University. נבדק ב-2024-01-16.
^ עודד רגב, באתר של קרן וולף
^ Chita, Efi. "2018 Gödel Prize". European Association for Theoretical Computer Science (EATCS). נבדק ב-2024-01-16.
^ Nguyen, Phong Q.; Regev, Oded (2008). "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures". Journal of Cryptology. 22 (2): 139–160. doi:10.1007/s00145-008-9031-0. ISSN 0933-2790.
^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "On Ideal Lattices and Learning with Errors over Rings". Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9. ISSN 0302-9743.
^ Regev, Oded; Stephens-Davidowitz, Noah (2017), A reverse Minkowski theorem, Annual ACM SIGACT Symposium on Theory of Computing, Montreal, Quebec, Canada, pp. 941–953, arXiv:1611.05979
^ Dadush, Daniel; Regev, Oded (2016). "Towards Strong Reverse Minkowski-Type Inequalities for Lattices". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 447–456. doi:10.1109/FOCS.2016.55. ISBN 978-1-5090-3933-3.
^ "Oded Regev". scholar.google.com.
^ "Editors". Theory of Computing. נבדק ב-2024-01-16.
^ "TCS+". sites.google.com.
^ Regev. "An Efficient Quantum Factoring Algorithm". {{cite arxiv}}: נדרש |arxiv= (עזרה)
^ Brubaker, Ben (2023-10-17). "Thirty Years Later, a Speed Boost for Quantum Factoring". Quanta Magazine (באנגלית). נבדק ב-2023-10-18.
^ Ragavan. "Optimizing Space in Regev's Factoring Algorithm". {{cite arxiv}}: נדרש |arxiv= (עזרה)

[Oded_Regev_PhD_thesis-1] Regev, Oded. "Scheduling and Load Balancing" (PDF). Tel Aviv University. נבדק ב-2024-01-16.

[2] עודד רגב, באתר של קרן וולף

[Chita_2018_Gödel_Prize-3] Chita, Efi. "2018 Gödel Prize". European Association for Theoretical Computer Science (EATCS). נבדק ב-2024-01-16.

[NguyenRegev2008-4] Nguyen, Phong Q.; Regev, Oded (2008). "Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures". Journal of Cryptology. 22 (2): 139–160. doi:10.1007/s00145-008-9031-0. ISSN 0933-2790.

[LyubashevskyPeikert2010-5] Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "On Ideal Lattices and Learning with Errors over Rings". Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23. doi:10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9. ISSN 0302-9743.

[6] Regev, Oded; Stephens-Davidowitz, Noah (2017), A reverse Minkowski theorem, Annual ACM SIGACT Symposium on Theory of Computing, Montreal, Quebec, Canada, pp. 941–953, arXiv:1611.05979

[DadushRegev2016-7] Dadush, Daniel; Regev, Oded (2016). "Towards Strong Reverse Minkowski-Type Inequalities for Lattices". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 447–456. doi:10.1109/FOCS.2016.55. ISBN 978-1-5090-3933-3.

[8] "Oded Regev". scholar.google.com.

[9] "Editors". Theory of Computing. נבדק ב-2024-01-16.

[10] "TCS+". sites.google.com.

[11] Regev. "An Efficient Quantum Factoring Algorithm". {{cite arxiv}}: נדרש |arxiv= (עזרה)

[12] Brubaker, Ben (2023-10-17). "Thirty Years Later, a Speed Boost for Quantum Factoring". Quanta Magazine (באנגלית). נבדק ב-2023-10-18.

[13] Ragavan. "Optimizing Space in Regev's Factoring Algorithm". {{cite arxiv}}: נדרש |arxiv= (עזרה)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]