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

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

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

ביוגרפיה

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

בשנת 2005 הוענק לו פרס קריל.תבנית:הערה

עבודתו

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

תבנית:ציטוטון

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

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

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

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

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

• עודד רגב, באתר של מכון קוראנט תבנית:אנגלית