פרס גדל

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

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

מבין 56 הזוכים בפרס עד שנת 2014, 17 הם ישראלים (כ־30 אחוז).

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

הזוכים בפרס

שנה	שמות הזוכים	הסיבה לזכייה
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	רונאלד פאגין, אמנון לוטם, מוני נאור	על תוצאות פורצות דרך באלגוריתמים של קיבוץ מידע (אגרגציה)

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

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

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

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

החלטה על זוכה

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

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

שגיאות פרמטריות בתבנית:ויקישיתוף בשורה
פרמטרי חובה [ שם ] חסרים

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

• אתר פרס גדל ב-ACM-SIGACT.
• אתר פרס גדל ב-EATCS.