נוגה אלון
חתן פרס וולף במתמטיקה 2024
נוגה אלון
שייכות בעת הענקת הפרס:
אוניברסיטת פרינסטון, ארה"ב
נימוק למתן הפרס:
"על תרומותיו הבסיסיות לקומבינטוריקה ולתיאוריה של מדעי המחשב".
שותפים לפרס:
נוגה אלון
עדי שמיר
"על תרומותיהם החלוציות לקריפטוגרפיה מתמטית, לקומבינטוריקה ולתיאוריה של מדעי המחשב".
נוגה אלון Noga Alon (נולד בישראל, 1956) הוא פרופסור למתמטיקה באוניברסיטת פרינסטון ופרופסור אמריטוס למתמטיקה ומדעי המחשב באוניברסיטת תל אביב, מחשובי החוקרים בעולם בתחום הקומבינטוריקה. מחקריו ופיתוחיו שינו את פני התחום, יצרו מושגים חדשים ושיטות מקוריות, ותרמו רבות לפיתוח המחקר התיאורטי ויישומיהם במתמטיקה בדידה, בתורת האינפורמציה, בתורת הגרפים, ובשימושיהם בתאוריה של מדעי המחשב. הוא אחד המתמטיקאים הפוריים בעולם, פרסם מאות מאמרים והעמיד תלמידי מחקר רבים במתמטיקה ובמדעי המחשב. ספרו "השיטה ההסתברותית" (בשיתוף עם ג'ואל ספנסר) הופיע ב 4 מהדורות. הרביעית (2016) מכילה 50 אחוז יותר חומר מהראשונה (1992), וכל המהדורות זכו להצלחה רבה בקרב החוקרים במתמטיקה בדידה, עם אלפי ציטוטים.
אלון גילה עניין עמוק במתמטיקה ופתרון חידות מתמטיות מגיל צעיר, הוא נמשך לאובייקטיביות שבה ולחתירה לאמת אבסולוטית; אל הקסם של המתמטיקה המתבטא בקשרים בלתי צפויים בין תחומים שונים, בהוכחות קצרות ואלגנטיות, בוודאות המוחלטת הנובעת מנכונותה של הוכחה ובאתגר האינטלקטואלי במציאתה. את אהבתו למתמטיקה מימש בעידודם של הוריו ומורו למתמטיקה בתקופת התיכון, השתתף וזכה בתחרויות רבות.
אלון סיים בהצטיינות יתרה את לימודי התואר הראשון במתמטיקה בטכניון, והמשיך ללימודי תואר שני בתורת הגרפים ופיתח נוסחה לחישוב מקורב של מספר העותקים המרבי של גרף כלשהו בגרף בעל מספר נתון של קשתות. בעבודת הדוקטור באוניברסיטה העברית בירושלים (1983), המשיך אלון לעסוק בבעיות קיצון קומבינטוריות שלהן שימושים בשטחים רבים כמו הנדסה, מדעי המחשב ותקשורת מחשבים. לאחר הדוקטורט יצא אלון להשתלם במכון הטכנולוגי של מסצ'וסטס, MIT, בארה"ב. במחקריו המשיך לעסוק בעיקר בקומבינטוריקה, ושיתף פעולה עם המתמטיקאי ההונגרי הנודע פאול ארדש, אשר השפיע מאוד על כיווני המחקר שלו והניבו במשך השנים כמה מאמרים משותפים. אלון היה שותף למחקרים רבים במעבדות המחקר החשובות בעולם, ביניהם, הרווארד, המכון ללימודים מתקדמים בפרינסטון, מרכז המחקר IBM Almaden , מעבדות בל, בלקור ומחקר במייקרוסופט (ברדמונד ובישראל). ב-1985 הצטרף לאוניברסיטת תל אביב, שם כיהן כראש בית הספר למתמטיקה. ב-2018 עבר לאוניברסיטת פרינסטון שם הוא ממשיך לעבוד עד היום. אלון הנחה עשרות סטודנטים לדוקטורט, הוא מכהן במערכות של יותר מתריסר כתבי עת בינלאומיים. פרופסור אלון נשא מאות הרצאות מוזמנות והרצאות מליאה בכנסים ברחבי העולם, היה ראש הוועדה המדעית של הקונגרס העולמי למתמטיקאים (מדריד, 2006) וחבר בוועדות פרסים יוקרתיים בעולם. הוא פרסם יותר משש מאות מאמרי מחקר וספר אחד.
קומבינטוריקה היא המתמטיקה של מבנים סופיים, ויש לה חשיבות עליונה בשטחים רבים במתמטיקה ובמדעי המחשב. רוב רובם של האלגוריתמים המשמשים בתכנות מחשבים, בתקשורת מחשבים ואפילו בטיפול במידע ביולוגי מבוססים על שיטות קומבינטוריות. פרופ' אלון עוסק במתמטיקה בדידה ובמדעי המחשב תוך התמקדות בקומבינטוריקה ובתורת הגרפים ובשימושיהם בתיאוריה של מדעי המחשב. עבודותיו הרבות בתחום שינו את פני הקומבינטוריקה המודרנית והכניסו מושגים, מבנים ושיטות חשובות לתחום. הוא הוכיח את ה- Combinatorial Nullstellensatz, טכניקה אלגברית רבת עוצמה שהניבה יישומים משמעותיים ביותר בתורת הגרפים וקומבינטוריקה, כולל הרחבה של משפט ארבעת הצבעים, והכללות של משפט קושי-דאוונפורט בתורת המספרים האדיטיבית.
פרופ' אלון הוא המדען המוביל בשיטה ההסתברותית במתמטיקה בדידה. ספרו שכתב עם ג'ואל ספנסר הוא ללא עוררין הטקסט המוביל בתחום מרכזי זה. בשיטה ההסתברותית משתמשים באקראיות – ברנדומיזציה – ככלי עזר לחקור גם בעיות שאין בהן מרכיב הסתברותי, ופרופ' אלון מצא שימושים מורכבים ומפתיעים לשיטה זו. למשל, בעבודה עם מטיאס ועם סגדי מצאו החוקרים דרך לטיפול יעיל בכמויות אדירות של מידע שאין אפשרות לאכסן אותו .הצד השני של המטבע בשיטה ההסתברותית הוא הדה-רנדומיזציה: התורה המנסה לתת בניות מפורשות שיחליפו שיטות הסתברותיות במתמטיקה ובמדעי המחשב. פרופ' אלון תרם תרומות חשובות לבניות מפורשות ולתחום הדה-רנדומיזציה; בין השאר הוא פיתח שיטות לבניית מרחבי מדגם קטנים התומכים במשתנים כמעט בלתי-תלויים. דוגמאות שמצא לפתרון בעיות שונות מפתיעות ביופיין ובעומקן.
אלון פיתח את "השיטה הפולינומיאלית" – כלי אלגברי רב עוצמה, בעל שימושים רבים בקומבינטוריקה, בתורת הגרפים, בתורת המספרים האדיטיבית ובתורת האינפורמציה. לשיטה זו המבוססת על הבנת מבנים קומבינטוריים באמצעות מרחבים של פולינומים המתאימים להם, מצא אלון שימושים מפתיעים בבעיות צביעה של גרפים, בבעיות קיצוניות הנוגעות לגרפים ולהיפר-גרפים ובבעיות בתורת המספרים החיבורית. אלון השתמש בכלי זה לפתרון בעיה שהעלה קלוד שאנון, אבי תורת האינפורמציה, והטרידה את המדענים במשך יותר מחמישים שנה. בניגוד להשערתו של שאנון הראה אלון שהקיבולת של צירוף שני ערוצים יכולה להיות גדולה בהרבה מסכום הקיבולות של כל ערוץ בנפרד. בעבודה משותפת עם קלייטמן, פתר אלון את הבעיה של הדוויגר ודברונר בגיאומטריה קומבינטורית שעמדה פתוחה כחמישים שנה, מה שהוכיח הכללה מרחיקת לכת של משפט הלי. פרופ' אלון פיצח בעיות חשובות שעמדו פתוחות עשרות שנים גם בתורת הגרפים ובתורת רמזי.
שיטת הקידוד בצבעים שפיתח יחד עם יוסטר וזוויק, מצאה יישומים בכמה תחומים אחרים, כולל התיאוריה של עקיבות פרמטרים קבועים (Fixed Parameter Tractability) וביואינפורמטיקה. עבודתו המשותפת עם מטיאס וסזגדי יזמה את המחקר של אלגוריתמי סטרימינג הבודקים אילו מאפיינים סטטיסטיים של נתונים של סטרימנינג ניתן לדגום ולהעריך תוך כדי תנועה. מחקרו זה הווה את הבסיס לתחום פורץ הדרך של אלגוריתמי סטרימינג ואלגוריתמי שרטוטים ויש לו יישומים תיאורטיים ויישומיים מעשיים רבים.
מחקריו של אלון תרמו משמעותית להבנת תכונות ספקטרליות ותכונות הרחבה של גרפים ולשימושים של גרפים מרחיבים במתמטיקה ובמדעי המחשב. אלון חלוץ ביישום שיטות ספקטרליות בחקר בעיות אלגוריתמיות והקשר שהוא מצא, בשיתוף עם ויטאלי מילמן, בין תכונות הפרדה לתכונות ספקטרליות של גרפים עוררו מחקר רב והן מצוטטות בכל העבודה הנרחבת שבאה לאחר מכן בתחום.
יחד עם שותפיו פיתח אלון גרסה אלגוריתמית ללמת הרגולריות של סמרדי Szemerédi , גילה את הקשר שלה לאי-שוויון קלאסי של גרותנדיק, והשתמש בה כדי ליישב בעצם את כל הבעיות הפתוחות העיקריות בתיאוריה של בדיקת מאפיינים עבור גרפים צפופים. עבודה זו פתחה מחקר נרחב ומילאה תפקיד חשוב בפיתוח שלאחר מכן של התיאוריה של רצפי גרפים מתכנסים על ידי לובאסז ושותפיו.
פרס וולף מוענק לנוגה אלון על השפעתו העמוקה על מתמטיקה בדידה ותחומים קשורים נוספים. תרומותיו המכוננות כוללות פיתוח טכניקות גאוניות בקומבינטוריקה, תורת הגרפים ותיאוריה של מדעי המחשב, ופתרון בעיות ארוכות שנים בתחומים אלה וכן בתורת המספרים האנליטית, גיאומטריה קומבינטורית ותורת המידע.
