פרס גדל

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
פרס גדל
תיאור פרס למאמר במדעי המחשב

פרס גֶדֶלאנגלית: The Gödel Prize) הוא פרס המוענק אחת לשנה, החל משנת 1993, עבור מאמר בולט באיכותו בתחום מדעי המחשב. הפרס מוענק על ידי האיגוד האירופי לתאוריה של מדעי המחשב (EATCS)[1] ו-ACM[2]. מעמד הענקת הפרס מתחלף מדי שנה בין הקולוקוויום הבינלאומי על אוטומט, שפות ותכנות (ICALP) (השייך ל-EACTS) לבין הסימפוזיון על תורת המחשוב (STOC) (השייך ל-ACM) לסירוגין. גובה הפרס עומד על 5,000 דולר אמריקאי. הפרס הוא השני בחשיבותו בתחום מדעי המחשב, לאחר פרס טיורינג[דרוש מקור][מפני ש...].

הפרס קרוי על שם הלוגיקן האוסטרי קורט גדל, לאור תרומותיו הרבות בתחום הלוגיקה המתמטית, ולאור הגדרת אחת הבעיות הפתוחות המרכזיות במדעי המחשב שנודעה לימים כבעיית P=NP[3].

מבין 66 הזוכים בפרס עד שנת 2019, 20 הם ישראלים.

ארבעה מהזוכים – שפי גולדווסר, יוהאן הסטאד, סנג'יב ארורה ומריו סגדי – זכו פעמיים בפרס.

הזוכים בפרס

שנה שמות הזוכים הסיבה לזכייה
1993 לסלו בבאי, שפי גולדווסר, סילביו מיקאלי, שלמה מורן, צ'ארלס ראקוף פיתוח המושג של מערכת הוכחה אינטראקטיבית
1994 יוהאן הסטאד על מציאת חסם תחתון אקספוננציאלי על גודלם של מעגלים בוליאניים קבועי-עומק לחישוב פונקציית זוגיות
1995 ניל אימרמן, רוברט סלפצ'ני על ההוכחה כי מחלקות סיבוכיות מקום אי-דטרמיניסטיות סגורות לפעולת המשלים (משפט אימרמן)
1996 מארק ג'רום, אליסטר סינקלייר על עבודתם בנושא שרשראות מרקוב וקירוב בעיית הפרמננטה
1997 ג'וזף הלפרן, יורם מוזס על הגדרת "ידע" במערכות מבוזרות
1998 סינוסוק טודה על הוכחת הקשר בין מחלקת הסיבוכיות PP וההיררכיה הפולינומית (משפט טודה)
1999 פיטר שור עבור פיתוח אלגוריתם קוונטי למציאת גורם ראשוני בזמן פולינומי (אלגוריתם שור)
2000 משה ורדי, פייר וולפר על בדיקות מודאליות בעזרת אוטומט סופי
2001 סנג'יב ארורה, אוריאל פייגה, שפי גולדווסר, קארסטן לאנד, לסלו לובאס, ראג'יב מוטוואני, שמואל ספרא, מדו סודן, מריו סגדי על משפט ה-PCP והשלכותיו באלגוריתמי קירוב
2002 ג'ארד סניזרגוס על הוכחת כריעות של בעיית השקילות, בשפות של אוטומט מחסנית דטרמיניסטי
2003 יואב פרוינד, רוברט שפיר עבור המצאת אלגוריתם AdaBoost
2004 מאוריס הרלי, מייק זאקס, ניר שביט, פוטיוס זהרוגלו על אפליקציות בטופולוגיה של חישוב מבוזר
2005 נגה אלון, יוסי מטיאס, מריו סגדי על תרומתם היסודית בתחום אלגוריתמים לזרמי מידע
2006 מנינדה אגרוול, נירג' קייל, ניטין סקסנה על אלגוריתם AKS לבדיקת ראשוניות של מספר בזמן פולינומי
2007 אלכסנדר רזבורוב, סטיבן רודיך על הוכחות טבעיות
2008 שאנגואה טאנג, דניאל ספילמן על שיטת ניתוח האלגוריתמים Smooth Analysis‏
2009 עומר ריינגולד, סליל ודאן, אבי ויגדרזון על מכפלות "זיג-זג" של גרפים
2010 סנג'יב ארורה, ג'וזף מיטשל על פיתוח אלגוריתמי קירוב יעילים עבור בעיית הסוכן הנוסע במרחב אוקלידי
2011 יוהאן הסטאד על תוצאות אי-קיום של אלגוריתמי קירוב (בעלי פרמטרים "טובים") עבור בעיות NP קשות
2012 אליאס קוטסופיאס, כריסטוס פאפאדימיטריו, טים ראפגרדן, אווה טרדוש, נעם ניסן, אמיר רונן על הנחת היסודות בתחום תורת המשחקים האלגוריתמית
2013 דן בונה, מת'יו פרנקלין, אנטואן ז'וקס על כלים קריפטוגרפיים המבוססים על מיפוי בי-ליניארי
2014 רונאלד פאגין, אמנון לוטם, מוני נאור על תוצאות פורצות דרך באלגוריתמים של קיבוץ מידע (אגרגציה)[4]
2015 דניאל שפילמן, שנגואה טנג
2016 סטפן ברוקס, פטר הורן
2017 סינתיה דבורק, פרנק מקשרי, קובי נסים, אדם סמית על המצאת פרטיות דיפרנציאלית
2018 עודד רגב על הצגת בעיית למידה עם שגיאות
2019 אירית דינור על הוכחה חדשה למשפט PCP
2020 רובין מוסר, גבור טרדוס על הוכחה קונסטרוקטיבית ללמת המקומיות של לובאס
2021 אנדריי בולאטוב, ג'ין-אי קאי, אקס-צ'אן, מרטין דייר, דייוויד ריצ'רבי על עבודתם על סיווג בעיית הספירה של בעיית סיפוק אילוצים
2022 צביקה ברקרסקי, קרייג ג'נטרי, וינוד וייקונטנתן על עבודתם על הצפנה הומומורפית מלאה

תהליך הזכייה בפרס

מועמדות וזכאות

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

כל חבר בקהילה המדעית רשאי להציע מאמר כמועמד לפרס. מאמר ייחשב כמועמד אם שני אנשים הציעו אותו כמועמד.

החלטה על זוכה

המאמר הזוכה נבחר על ידי ועדה בת שישה חברים. הרכב הוועדה מתחלף מדי שנה, כאשר ליו"ר ACM וליו"ר EATCS זכות לבחור 3 חברים לוועדה, כל-אחד.

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

ויקישיתוף מדיה וקבצים בנושא פרס גדל בוויקישיתוף

הערות שוליים

  1. ^ אתר EATCS.
  2. ^ אתר ACM-SIGACT.
  3. ^ גדל עסק בנושא זה לראשונה, כפי שהתגלה במכתב ששלח אל ג'ון פון ניומן. ראו אתר פרס גדל ב-ACM-SIGACT.
  4. ^ Ronald Fagin, Amnon Lotem, and Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences 66 (2003), pp. 614–656
Logo hamichlol 3.png
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0