پاسین منورانگسی: הוכחת מה שמחשבים אינם יכולים לעשות
ביולי 2011 אירחה עיר הנופש התאيلנדית פאטايا את אולימפיאדת האינפורמציה הבינלאומית ה-23, הפעם הראשונה שתאيلנד אירחה את האירוע אי פעם, וראש הממשלה אภისიט ڤیجیاجیڤა פתח את המשחקים כאחת מפעולותיו הרשמיות האחרונות. בין חברי הנבחרת המארחת היה תלמיד מבנגקוק כריสتیան كولिज שהגיע למקום ה-14 מתוך 303 מתחרים עם 524 נקודות וקצר מדליית זהב שנייה ברציפות. הוא אמר לכתבים כי הוא מרוצה מהמקום ה-14, ש-524 נקודות היו יותר ממה שציפה, ושהוא מקווה שאירוח האולימפיאדה יעורר עניין רב יותר במחשבים בקרב בני נוער תאيلנדים. חמש עשרה שנים לאחר מכן, پاسین منورانگسی (Pasin Manurangsi) הוא אחד החוקרים שתפקידם לומר לשאר מדעי המחשב אילו בעיות הן חסרות תקווה.
קשת האולימפיאדה
ההיסטוריה התחרותית של منورانگسی נקראת כמו ניסוי מבוקר בשיפור. באולימפיאדת האינפורמציה הבינלאומית בבולגריה ב-2009 הוא צבר 516 נקודות וסיים במקום ה-67 מתוך 301, כשהוא זוכה במדליית כסף. ב-2010, בקנדה, הוא צבר 704 נקודות וסיים במקום ה-12 מתוך 297, כשהוא זוכה בזהב. ב-2011, על אדמת המולדת, הוא זכה בזהב שוב כאשר תაيلנד זכתה במדליית הזהב הקבוצתית בתחרות שאירחה בפעם הראשונה. שלוש הופעות, שתי מדליות זהב ואחת כסף, וקפיצה של חמישים וחמישה מקומות בדירוג העולמי בין ניסיונו הראשון לשני: המסלול של מי שהתייחס להפסד כמסמך מפרט ולא כפסק דין.
MIT, ובעיית ההתקרבות המספקת
منورانگسی השלים את תוארי הבكال׳ור והמוסמך שלו במכון הטכנולוגי של ماسაჩusets, שם עבודת המאסטר שלו, בהנחיית דانا موشكوبيッツ, עסקה באלגוריתמי קירוב למשחקי היטל. בחירת נושא זו קבעה את כיוון כל מה שבא בעקבותיה. קירוב הוא הפשרה הפרגматиית של התחום: כאשר לא ניתן לפתור בעיה במדויק בזמן סביר, אתה מסתפק בתשובה המובטחת להיות בטווח של פקטור כלשהו מהתשובה הטובה ביותר. השאלה המעניינת, זו שمنورانگسی המשיך לחזור אליה, היא עד כמה טובה הבטחה זו יכולה להיות לפני שהיא מתנגשת בקיר מתמטי.
ברקלי: הארץ שבין P ל-NP
הוא השלים את הדוקטורט שלו באוניברסיטת קליפורنیا, ברקלי במאי 2019, בהנחייתם המשותפת של لوكا تريبیسان וპრასאד راغاڤندرا, עם ניఖיל סריבাস্তבה בוועדה. התזה נקראה Approximation and Hardness: Beyond P and NP, והשאפתנות שלה ניכרת בכותרת. תורת הסיבוכיות הקלאסית ממיינת בעיות לניתנות לפתרון (P) ולקשות באופן ידוע (NP-complete). עבודת הדוקטורט של منورانگسی יצאה במכוון לצוד בשטחים שקטגוריות אלו אינן מכסות: בעיות שאינן ב-P וגם אינן ידועות כ-NP-קשות, בעיות פרמטריות כגון k-dominating set, k-clique, k-biclique, directed Steiner network ובעיות סריג, וכן – באופן המנוגד ביותר לאינטואיציה – בעיות שיושבות בנוחות בתוך P, כמו الزوج הקרוב ביותר ומכنep פנימי מקסימלי, אך מתנגדות לקירוב מהיר בכל זאת. התקציר טוען שהעבודה פותרת שתי שאלות פתוחות ותיקות בסיבוכיות פרמטרית ומספקת את גורמי אי-הקירוב הטובים ביותר הידועים עבור מספר בעיות. זוהי תזה על שרטוט גבולות, לא על חצייתם.
Twenty questions, eight minutes on the clock, and a percentile measured against everyone who has taken it. No sign-up.
Take the IQ test →קיר תת-הגרף הצפוף ביותר k-Subgraph
התוצאה היחידה שעשתה לו שמה נוגעת לתת-הגרף הצפוף ביותר (Densest k-Subgraph): בהינתן רשת, מצא את k הצמתים הארוזים בצפיפות הרבה ביותר בחיבורים. منورانگسی הוכיח שחת תחת השערת זמן מעריכי, שום אלגוריתם בזמן פולינומי אינו יכול להשיג יחס קירוב הטוב מ-n בחזקת 1/(log log n) המועלה לקבוע – ושחת תחת הנחת Gap-ETH החזקה יותר המחסום מתהדק ל-n^f(n) עבור כל פונקציה f השואפת לאפס, וזהו קושי פולינומי כמעט לחלוטין. באופן מכריע, לבנייה יש מה שהתחום מכנה שלמות מושלמת: היא מבדילה בין גרפים המכילים באמת k-clique לבין גרפים שבהם כל k-subgraph הוא דליל. המאמר זכה בפרס دانی لوین למאמר הסטודנטים הטובים ביותר ב-STOC 2017, ועידת התיאוריה המובילה של התחום.
גוגל, פרטיות וחלוקה הוגנת
מאז יולי 2019 منورانگسی הוא מדען מחקר ב-Google Research, שם תחומי העיסוק הרשומים שלו הם אלגוריתמים ותיאוריה, אינטליגנציה מכונתית, ומניעת שימוש לרעה, ושם צבר יותר ממאה פרסומים. מרכז הכובד זז מחוסר קירוב טהור לעבר פרטיות דיפרנציאלית, תורת הלמידה ובחירה חברתית חישובית – חלוקה הוגנת, חציית קונצנזוס, צבירת דירוג פרטית, הפקת נתונים סינתטיים. תוצאה אחת לאחרונה מראה שחציית קונצנזוס עד O(√(n log n)) טובין תמיד קיימת עבור n סוכנים עם תועלות מונוטוניות, מה שמשפר גבול קודם. הפרסים המשיכו להגיע: המאמר הטוב ביותר ב-WAOA 2021, מאמר הסטודנטים הטוב ביותר ב-ALT 2021, מאמר טוב ביותר וציון לשבח למאמר טוב ביותר ב-FORC 2026, בתוספת הכרה מצטיינת בוועדת התוכנית ב-IJCAI ב-2021 וב-2023 ומעמד סוקר מוביל ב-NeurIPS 2023.
מסע החזרה
מאז 2022 הוא חבר בצוותי האימון של אולימפיאדת האינפורמציה של תაيلנד ומחנות האולימפיאדה המתמטית שלה, ושימש כחבר משלחת אורח עבור תაيلנד ב-IOI 2024. מאז 2023 הוא גם סגל נלווה באוניברסיטת CMKL, ומלמד אלגוריתמים, מבני נתונים ואלגוריתמים שומרי פרטיות. צינור הציוד שיצר אותו הוא כעת כזה שהוא עוזר להפעיל.
מדוע پاسین מכונה גאון
האיכות הקוגניטיבית המדוברת כאן ספציפית באופן יוצא דופן, והיא אינה מהירות גולמית. הצלחה אולימפית מתגמלת פתרון בעיות מהיר ומדויק תחת שעון; קשיחות של קירוב מתגמלת כמעט את ההפך – הסבלנות לבנות רדוקציה מורכבת המוכחת ששלמות שלמה של אלגוריתמים נידונה לכישלון. منورانگسی נדיר בכך שעשה את שניהם ברמה גבוהה, והתזה של ברקלי היא הראיה: היא תוחמת טריטוריה שרוב החוקרים מתחמקים ממנה בדיוק מפני שתוצאות שליליות קשה יותר לפרסם וקשה יותר לעשות נכון. מעידה לוגית אחת ברדוקציה מבטלת את הכל.
מקרה הנגד ההוגן הוא משמעותי. שום דבר ברשומה המקורית – דף הבית שלו, פרופיל Google Research, עבודת הדוקטורט, או הסיקור העיתונאי התאيلנדי בן הזמן – אינו משתמש במילה "גאון" לגביו. ההוקרות שלו הן פרסי עמיתים מוועדות כנסים, המזהות את המאמר הטוב ביותר בחדר, ולא מוח לדורות. מדעי המחשב התיאורטיים הם גם שיתופיים ללא פשרות; למעלה ממאה המאמרים שלו הם תוצר של כתיבה משותפת, סמינרים וקבוצה בברקלי המונהגת על ידי שניים מתיאורטיקני הסיבוכיות החזקים ביותר בתחום. שיא ה-IOI שלו, אף שהוא מצוין, כולל סיום במקום ה-67. מה שניתן לומר ללא ניפוח הוא צר יותר ומעניין יותר: הוא איש מקצוע מהדרגה הראשונה באחת הפינות התובעניות ביותר מבחינה טכנית של מתמטיקה, ותוצאת הגדרתו סגרה שאלה שהייתה פתוחה במשך שנים. זה לא אותו דבר כמו גאון, והוא מעולם לא טען שזה כך.
תחזית
לקריירה של منورانگسی יש צורה יוצאת דופן עבור תיאורטיקן: הוכחות אי האפשרות הגיעו ראשונות, עבודת הפרטיות היישומית שניות. המעבר לפרטיות דיפרנציאלית וחלוקה הוגנת מרמז על מישהו שלאחר שקבע היכן הקירות נמצאים, מעדיף כעת לבנות בתוכם. אימון האולימפיאדה התאيلנדי עשוי להתגלות כמורשת העמידה יותר – מדינה שאירחה את ה-IOI פעם אחת, וכעת מגדלת את האנשים שמנצחים בו.