אבי ויגדרזון: המתמטיקאי שהפך את האקראיות לקריאה
ב-1956 בחיפה, במשפחה שנבנתה מההריסות של השואה, גדל נער שישקע בעשורים הבאים בטיעון שמחשבים, הוכחות ומקרה הם למעשה נושא אחד הלובש עטיפות שונות. אבי ויגדרזון לא המציא מכונה או משפט כמו שהמציא דרך ראייה: שהשאלות הקשות ביותר במתמטיקה והשאלות הקשות ביותר במחשוב הן, בבסיסן, אותה שאלה הנשאלת פעמיים.
מחיפה לפרינסטון
ויגדרזון למד בבית הספר הריאלי העברי בחיפה לפני שלמד בטכניון, שם פגש את עדנה, שתהיה לאשתו. הוא עבר לאוניברסיטת פרינסטון ללימודי הדוקטורט, אותם סיים ב-1983 בהנחיית ריצ'רד ליפטון עם דיסרטציה בשם "מחקרים בסיבוכיות חישובית" — כותרת שהצניעה את מה שהפך למסע קריירה שלם להבנה מה חישוב יכול ולא יכול לעשות. לאחר תקופות באוניברסיטת קליפורניה ברקלי, במעבדת אלמדן של IBM ובמכון המחקר למדעים מתמטיים, שב לביתו לפרופסורה באוניברסיטה העברית בירושלים ב-1986, קיבל קביעות שנה לאחר מכן וקתדרה מלאה ב-1991. ב-1999 החל לחלק את זמנו עם ולבסוף עבר באופן מלא למכון ללימודים מתקדמים בפרינסטון — המוסד שהכיל בעבר איינשטיין וגדל — שם הוא מחזיק כיום בקתדרת הרברט ה. מאס ומנהל את תוכנית מדעי המחשב והמתמטיקה הבדידה שעזר להקים.
שאלת האקראיות
הרעיון שעובר כמעט בכל מה שויגדרזון נגע בו הוא אקראיות: האם מחשב באמת צריך גישה לאקראיות אמיתית כדי לפתור בעיות ביעילות, או ניתן לייצר אקראיות — "לגרום לה להיות לא אקראית" — מתוך מבנה טהור? עם נואם ניסן וראסל אימפגליאצו, הוא עזר לבנות את המנגנון התיאורטי המראה שתחת הנחות סבירות, אקראיות באלגוריתמים ניתן לסמולט באופן דטרמיניסטי. זה נשמע כמו טכניקליות. זה קרוב יותר לתוצאה פילוסופית: שבלתי צפיות, בחישוב, עשויה להיות אשליה שנוצרת על ידי המורכבות עצמה ולא מרכיב יסודי.
המכפלה הזיג-זג
ב-2002, בעבודה עם אומר ריינגולד וסליל ואדהן, ויגדרזון הציג את המכפלה הזיג-זג, דרך לשילוב גרפים שמייצרת "גרפי מרחבים" — רשתות מחוברות בצורה גבוהה שמתנהגות, לצורכי חישוב, כמעט כמו גרפים אקראיים, אך נבנות לחלוטין באופן מפורש. הבנייה קישרה שלושה תחומים שדיברו באופן נדיר במונחים אלה: תורת הסיבוכיות, תורת הגרפים הקומבינטורית ותורת החבורות. היא זכתה בפרס גדל ב-2009 ונתנה לחוקרים מאוחרים יותר, כולל ריינגולד בפני עצמו, את הכלים להראות שבעיה בסיסית של חיבור גרפים ניתן לפתור עם כמות מפתיעה קטנה של זיכרון מחשב — תוצאה שנבנתה ישירות על בנייתו של ויגדרזון.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →הוכחות שאינן חושפות כלום
ויגדרזון עבד גם עם סילביו מיקלי ועודד גולדרייך על הוכחות אפס-ידע — דרך פורמלית שבה צד אחד יכול לשכנע את הצד השני שטענה היא אמת מבלי לחשוף כלום על הסיבה. הרעיון, שהיה פעם סקרנות אקדמית, משובץ כעת במערכות קריפטוגרפיות אמיתיות, מקרה נדיר של תורת הסיבוכיות היסודית שעברה ישירות לביטחון יישומי. זה אופייני לעבודתו של ויגדרזון ששאלה שהוצגה בזכות האלגנטיות המושגית שלה התבררה, עשורים לאחר מכן, שיש לה שיניים מעשיות.
הכרה בשיא
אותות ההוקרה של ויגדרזון עוקבים אחר עלייתו של התחום עצמו מתת-תחום של מתמטיקה לתחום בפני עצמו. הוא זכה בפרס רולף נבנלינה ב-1994, בפרס גדל ב-2009, בפרס קנות' ב-2019, ונבחר לאקדמיה האמריקאית לאמנויות ולמדעים ולאקדמיה הלאומית למדעים. ב-2021 הוא חלק את פרס אייבל — המקבילה הקרובה ביותר במתמטיקה לפרס נובל — עם לאסלו לובאז', "על תרומותיהם היסודיות לתורת המחשוב התיאורטית ולמתמטיקה הבדידה, ועל תפקידם המוביל בעיצובם לתחומים מרכזיים במתמטיקה המודרנית." רוברט דייקראף, מנהל המכון ללימודים מתקדמים, מיקם אותו "במסורת של גדל ופון נוימן, בשיאה של תורת החישוב." שלוש שנים לאחר מכן, ב-2024, הוא קיבל את פרס טיורינג של ACM — הכבוד הגבוה ביותר במחשוב — "על שינוי הבנתנו את תפקידה של האקראיות בחישוב." מעטים חוקרים אספו את שני הפרסים; עוד פחות עשו זאת עבור עבודה המשתרעת על שני התחומים גם יחד.
מדוע קוראים לאבי גאון
המילה מצמידה את ויגדרזון מסיבה ספציפית: יכולת יוצאת דופן למצוא את המבנה המאחד היחיד המוסתר מתחת לבעיות שנראות, על פני השטח, בלתי קשורות — אקראיות באלגוריתמים, חיבוריות של גרפים, תקפות של הוכחות קריפטוגרפיות, הגבול בין מה שקל לחשב ומה שקשה לחשב. עמיתים מתארים זאת פחות כמהירות חישוב גולמית ויותר כסוג של אינסטינקט אדריכלי, היכולת לראות שבנייה שנבנתה למטרה אחת (גרף מרחב) פותרת בעיה בתחום שונה לגמרי (אלגוריתמים יעילי זיכרון) שנים לפני שאחרים מבחינים בקשר. הערתו של פיטר סארנק שויגדרזון ולובאז' "היו במרכז רבים מהפריצות הדרך שעיצבו" שני תחומים פורחים היא עדות מפי שווה, לא שפה קידומית. הטיעון ההגיוני הנגדי: ויגדרזון עצמו מתנגד באופן מוחלט למסגרת הגאון הבודד, ומציין שמאמריו כללו יותר ממאה שותפים לכתיבה, ושלשון ועדת פרס אייבל מכבדת אותו על שינוי זהותו של תחום כמו על פתרון בעיות בודדות. זהו לא גאונות של הבזק האינסטינקט הבודד אלא של המקשר בין פינות שונות של מתמטיקה ומדעי המחשב שדיברו זה עם זה במשך ארבעים שנה — סוג של גאונות איטית, 누적ית, וכנראה נדירה יותר.
חיים לצד העבודה
ויגדרזון תיאר את תורת החישוב כ"ביתו האקדמי והחברתי בארבעים השנים האחרונות," ביטוי שתופס עד כמה התחום והאדם משולבים. הוא ועדנה גידלו משפחה שנשארה קרובה לעולם הרעיונות: בנם יובל ויגדרזון הפך בעצמו לפרופסור למתמטיקה, במכון המדע והטכנולוגיה של אוסטריה. ב-2025, קרן קרנגי קראה לוויגדרזון לכבוד המהגרים הגדולים, הכרה שמקבצת את סיפורו האישי — ילד של ניצולי שואה חצה אוקיינוס וגבול בין תחומים — באותה מסגרת עם זו המדעית שלו.
מורשת
חותמו של ויגדרזון בתחומו הוא כעת פחר רשימת משפטים מאשר תחום מאורגן מחדש סביב השאלות שהוא התעקש שחשובות — מה אקראיות קונה למחשב, ומה מבנה יכול להחליף אותה. במכון ללימודים מתקדמים, התוכנית שהוא מנהל ממשיכה לאמן את החוקרים שירשו את הארגון מחדש הזה, והציטוטים של פרס אייבל וטיורינג, שהוענקו בתוך שלוש שנים זו מזו, מסמנים הכרה כפולה נדירה של גוף עבודה אחד משני המתמטיקה ומדעי המחשב.