פרס גדל

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

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

מבין 82 הזוכים בפרס עד שנת 2023, 21 הם ישראלים.

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

== הזוכים בפרס ==

{| class="wikitable" align="center"
|-
! שנה
! width="350px" | שמות הזוכים
! הסיבה לזכייה
|-
| 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 || רונאלד פאגין, אמנון לוטם, מוני נאור || על תוצאות פורצות דרך באלגוריתמים של קיבוץ מידע (אגרגציה)
|-
|2015 || דניאל שפילמן, שנגואה טנג ||
|-
|2016 || סטפן ברוקס, פטר הורן ||
|-
| 2017 || סינתיה דבורק, פרנק מקשרי, קובי נסים, אדם סמית|| על המצאת פרטיות דיפרנציאלית
|-
|2018 || עודד רגב || על הצגת בעיית למידה עם שגיאות
|-
|2019 || אירית דינור || על הוכחה חדשה למשפט PCP
|-
|2020 || רובין מוסר, גבור טרדוס || על הוכחה קונסטרוקטיבית ללמת המקומיות של לובאס
|-
|2021 || אנדריי בולאטוב, ג'ין-אי קאי, אקס-צ'אן, מרטין דייר, דייוויד ריצ'רבי || על עבודתם על סיווג בעיית הספירה של בעיית סיפוק אילוצים
|-
|2022 || צביקה ברקרסקי, קרייג ג'נטרי, וינוד וייקונטנתן || על עבודתם על הצפנה הומומורפית מלאה
|-
|2023 || סמואל פיוריני, סרג' מסאר, סבסטיאן פוקוטה, הנס ראג' טיוארי, רונלד דה וולף ותומס רוטבוס || להראות שלכל ניסוח מורחב לבעיית הסוכן הנוסע יש גדילה מעריכית
|}

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

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

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

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

* [https://sigact.org/prizes/gödel.html אתר פרס גדל] ב-ACM-SIGACT
* [http://www.eatcs.org/index.php/goedel-prize אתר פרס גדל] ב-EATCS

== הערות שוליים ==

*
גדל