PROFILPELAJAR.COM

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

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

בשנת 2023 הצליח רגב ליעל את אלגוריתם שור לפירוק מספרים ראשוניים ופיתח אלגוריתם קוונטי שמפרק מספר בעל $n$ ביטים באמצעות $O(n^{3/2})$ שערים קוואנטיים בלבד לעומת אלגוריתם שור המשתמש ב $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
^ 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