جائزة غودل

الموسوعة الحرة
كورت غودل
كورت غودل

جائزة غودل هي جائزة سنوية تُمنح للأبحاث المتميزة في مجال علوم الحاسوب النظرية ، وتُقدم بالاشتراك بين الجمعية الأوروبية لعلوم الحاسوب النظرية (EATCS) ومجموعة الاهتمام الخاصة بالخوارزميات ونظرية الحوسبة التابعة لجمعية آلات الحوسبة ( ACM SIGACT ). سُميت الجائزة تكريمًا لكورت غودل . ويكمن ارتباط غودل بعلوم الحاسوب النظرية في كونه أول من طرح مسألة " P مقابل NP "، وذلك في رسالة عام 1956 إلى جون فون نيومان، حيث تساءل غودل عما إذا كان من الممكن حل مسألة معينة من مسائل NP-complete في زمن تربيعي أم خطي . [ 1 ]

تُمنح جائزة غودل منذ عام 1993. وتُمنح بالتناوب في مؤتمر ICALP (في السنوات الزوجية) ومؤتمر STOC (في السنوات الفردية). يُعدّ STOC ندوة ACM حول نظرية الحوسبة ، وهو أحد أهم المؤتمرات في أمريكا الشمالية في مجال علوم الحاسوب النظرية، بينما يُعدّ ICALP الندوة الدولية حول الأوتوماتا واللغات والبرمجة ، وهو أحد أهم المؤتمرات الأوروبية في هذا المجال. للتأهل للجائزة، يجب أن يكون البحث منشورًا في مجلة محكمة خلال السنوات الأربع عشرة الماضية (كانت سابقًا سبع سنوات). وتشمل الجائزة مكافأة مالية قدرها 5000 دولار أمريكي. [ 2 ]

يتم اختيار الفائز بالجائزة من قبل لجنة مؤلفة من ستة أعضاء. يعيّن رئيس الجمعية الأوروبية لعلوم وتكنولوجيا الحاسوب (EATCS) ورئيس الجمعية الدولية لعلوم وتكنولوجيا الحاسوب (SIGACT) ثلاثة أعضاء لكل منهما في اللجنة، وتكون مدة عضويتهم ثلاث سنوات بالتناوب. ويتناوب على رئاسة اللجنة ممثلون عن كل من الجمعية الأوروبية لعلوم وتكنولوجيا الحاسوب (EATCS) والجمعية الدولية لعلوم وتكنولوجيا الحاسوب (SIGACT).

وعلى النقيض من جائزة غودل، التي تُمنح للأوراق البحثية المتميزة، تُمنح جائزة كنوت للأفراد لتأثيرهم الشامل في هذا المجال.

المستفيدون

سنةالاسم (الأسماء)ملحوظاتسنة النشر
1993لازلو باباي ، وشافي جولدفاسر ، وسيلفيو ميكالي ، وشلومو موران ، وتشارلز راكوفلتطوير أنظمة إثبات تفاعلية1988، [ الورقة 1 ] 1989 [ الورقة 2 ]
1994يوهان هاستادللحصول على حد أدنى أسي لحجم الدوائر المنطقية ذات العمق الثابت (لدالة التكافؤ ).1989 [ الورقة 3 ]
1995نيل إيمرمان وروبرت زيليبسينيفيما يتعلق بنظرية إيمرمان-سيليبسيني حول تعقيد الفضاء غير الحتمي1988، [ الورقة 4 ] 1988 [ الورقة 5 ]
1996مارك جيروم وأليستر سنكليرللعمل على سلاسل ماركوف وتقريب الثابت للمصفوفة1989، [ الورقة 6 ] 1989 [ الورقة 7 ]
1997جوزيف هالبرن ويورام موسىلتحديد مفهوم رسمي لـ "المعرفة" في البيئات الموزعة1990 [ الورقة 8 ]
1998سينوسوكي تودابالنسبة لنظرية تودا ، التي أظهرت وجود صلة بين عد الحلول ( PP ) وتناوب الكميات ( PH ).1991 [ الورقة 9 ]
1999بيتر شورخوارزمية شور لتحليل الأعداد إلى عواملها الأولية في وقت متعدد الحدود على حاسوب كمومي1997 [ الورقة 10 ]
2000موشيه فاردي وبيير وولبرللعمل على المنطق الزمني باستخدام الأوتوماتا المحدودة1994 [ الورقة 11 ]
2001سانجيف أرورا ، أوريل فيجي ، شافي جولدفاسر ، كارستن لوند ، لازلو لوفاس ، راجيف موتواني ، شموئيل صفرا ، مادو سودان ، وماريو سيجيديفيما يتعلق بنظرية PCP وتطبيقاتها على صعوبة التقريب1996، [ الورقة 12 ] 1998، [ الورقة 13 ] 1998 [ الورقة 14 ]
2002جيرود سينيزيرغلإثبات أن تكافؤ آلات الدفع الحتمية قابل للتقرير2001 [ الورقة 15 ]
2003يوآف فرويند وروبرت شابيرلخوارزمية AdaBoost في التعلم الآلي1997 [ الورقة 16 ]
2004موريس هيرليهي ، ومايكل ساكس ، ونير شافيت ، وفوتيوس زهاروغلولتطبيقات الطوبولوجيا في نظرية الحوسبة الموزعة1999، [ الورقة 17 ] 2000 [ الورقة 18 ]
2005نوجا ألون ويوسي ماتياس وماريو زيجيديوذلك لمساهمتهم الأساسية في خوارزميات البث المباشر1999 [ الورقة 19 ]
2006مانيندرا أغراوال ، نيراج كيال ، نيتين ساكسينالاختبار أولية AKS2004 [ الورقة 20 ]
2007ألكسندر رازبوروف ، ستيفن روديتشللبراهين الطبيعية1997 [ الورقة 21 ]
2008دانيال سبيلمان ، شانغ هوا تنغلتحليل الخوارزميات بسلاسة2004 [ الورقة 22 ]
2009عمر رينجولد ، سليل فادهان ، آفي ويجدرسونبالنسبة للضرب المتعرج للرسوم البيانية والاتصال غير الموجه في فضاء لوغاريتمي2002، [ الورقة 23 ] 2008 [ الورقة 24 ]
2010سانجيف أرورا ، جوزيف إس بي ميتشللاكتشافهم المتزامن لخوارزمية تقريبية متعددة الحدود لمسألة البائع المتجول الإقليدية1998، [ الورقة 25 ] 1999 [ الورقة 26 ]
2011يوهان هاستادلإثبات نتائج عدم التقريب الأمثل لمختلف المسائل التوافقية2001 [ الورقة 27 ]
2012إلياس كوتسوبياس ، وكريستوس باباديميتريو ، ونعوم نيسان ، وأمير رونين ، وتيم روغاردن ، وإيفا تاردوسلوضع أسس نظرية الألعاب الخوارزمية [ 3 ]2009، [ الورقة 28 ] 2002، [ الورقة 29 ] 2001 [ الورقة 30 ]
2013دان بونيه ، ماثيو ك. فرانكلين ، وأنطوان جولتبادل مفاتيح ديفي-هيلمان متعدد الأطراف ونظام بونيه-فرانكلين في علم التشفير [ 4 ]2003، [ الورقة 31 ]

2004 [ الورقة 32 ]

2014رونالد فاجن ، أمنون لوتيم ، وموني ناعورلخوارزميات التجميع الأمثل للبرمجيات الوسيطة [ 5 ]2003، [ الورقة 33 ]
2015دانيال سبيلمان ، شانغ هوا تنغلسلسلة أوراقهم البحثية حول حلول لابلاس شبه الخطية [ 6 ]

2011 [ الورقة 34 ] 2013 [ الورقة 35 ] 2014 [ الورقة 36 ]

2016ستيفن بروكس وبيتر دبليو أوهيرنلاختراعهم منطق الفصل المتزامن2007، [ الورقة 37 ] 2007 [ الورقة 38 ]
2017 [ 2 ]سينثيا دورك ، وفرانك ماكشيري ، وكوبي نسيم ، وآدم د. سميثلاختراع الخصوصية التفاضلية2006 [ الورقة رقم 39 ]
2018 [ 7 ]أوديد ريجيفلتقديم مشكلة التعلم مع الأخطاء2009 [ الورقة رقم 40 ]
2019 [ 8 ]إيريت دينورلإثباتها الجديد لنظرية PCP عن طريق تضخيم الفجوة2007 [ الورقة 41 ]
2020 [ 9 ]روبن موزر وغابور تاردوسلإثباتهم البنّاء لفرضية لوفاس المحلية2010 [ الورقة 42 ]
2021 [ 10 ]أندريه بولاتوف، جين-يي كاي ، شي تشن ، مارتن داير ، وديفيد ريتشربيلعملهم على تصنيف تعقيد العد لمسائل إرضاء القيود2013 [ الورقة 43 ] 2013 [ الورقة 44 ] 2017 [ الورقة 45 ]
2022 [ 11 ]زفيكا براكيرسكي وكريج جينتري وفينود فايكونتاناثانوذلك لمساهماتهم التحويلية في علم التشفير من خلال بناء مخططات تشفير متماثلة الشكل بالكامل (FHE) فعالة2014، [ الورقة 46 ] 2014 [ الورقة 47 ]
2023 [ 12 ]صامويل فيوريني ، وسيرج مسار ، وسيباستيان بوكوتا ، وهانز راج تيواري ، ورونالد دي وولف ، وتوماس روثفوسلإثبات أن أي صيغة موسعة لمتعدد السطوح TSP أو متعدد السطوح المطابق لها حجم أسي2015، [ الورقة 48 ] 2017 [ الورقة 49 ]
2024 [ 13 ]ريان ويليامزلعمله على الحدود الدنيا للدوائر الكهربائية ونموذج "الخوارزميات للوصول إلى الحدود الدنيا".2011 [ الورقة رقم 50 ]
2025 [ 14 ]إيشان تشاتوبادياي وديفيد زوكرمانلعملهم في بناء " مستخرج صريح ثنائي المصدر مع الحد الأدنى من الإنتروبيا متعددة اللوغاريتمات، مما يحل مشكلة مركزية في نظرية الحوسبة ظلت مفتوحة لما يقرب من ثلاثة عقود".2016 [ الورقة رقم 51 ]
2026 [ 15 ]إلياس دياكونيكولا، غوتام كاماث، دانييل كين ، جيري لي، أنكور مويترا، وأليستير ستيوارتمن أجل خوارزميات فعالة لتعلم التوزيعات عالية الأبعاد في وجود عمليات تشويه معادية2019 [ الورقة رقم 52 ]

الأوراق الفائزة

  1. ↑ باباي، لازلو؛ موران، شلومو (1988)، "ألعاب آرثر-ميرلين: نظام إثبات عشوائي، وتسلسل هرمي لفئة التعقيد" (ملف PDF) ، مجلة علوم الحاسوب والأنظمة ، 36 (2): 254-276 ، doi : 10.1016/0022-0000(88)90028-1 ، ISSN 0022-0000 
  2. ↑ غولدواسير، س.؛ ميكالي، س.؛ راكوف، س. (1989)، "تعقيد المعرفة لأنظمة الإثبات التفاعلية" (ملف PDF) ، مجلة SIAM للحوسبة ، 18 (1): 186-208 ، CiteSeerX 10.1.1.397.4002 ، doi : 10.1137/0218012 ، ISSN 1095-7111  
  3. ↑ هاستاد، يوهان (1989)، "حدود دنيا شبه مثالية للدوائر ذات العمق الصغير" (ملف PDF) ، في ميكالي، سيلفيو (محرر)، العشوائية والحوسبة ، سلسلة أبحاث الحوسبة المتقدمة، المجلد 5، دار نشر JAI، الصفحات 6-20 ، ISBN   978-0-89232-896-3تمت أرشفة هذا الملف من النسخة الأصلية (PDF) بتاريخ 22 فبراير 2012.
  4. ↑ إيمرمان، نيل (1988)، "الفضاء غير الحتمي مغلق تحت التتميم" (ملف PDF) ، مجلة SIAM للحوسبة ، 17 (5): 935-938 ، CiteSeerX 10.1.1.54.5941 ، doi : 10.1137/0217058 ، ISSN 1095-7111  
  5. ^ Szelepcsényi، R. (1988)، “طريقة التعداد القسري للأوتوماتا غير الحتمية” (PDF) ، Acta Informatica ، 26 (3): 279–284 ، دوى : 10.1007/BF00299636 ، hdl : 10338.dmlcz/120489 ، S2CID 10838178 
  6. ↑ سينكلير، أ.؛ جيروم، م. (1989)، "العد التقريبي، والتوليد المنتظم، وسلاسل ماركوف سريعة الخلط"، المعلومات والحوسبة ، 82 (1): 93-133 ، doi : 10.1016/0890-5401(89)90067-9 ، ISSN 0890-5401 
  7. ↑ جيروم، م.؛ سنكلير، أليستير (1989)، "تقريب الثابت"، مجلة SIAM للحوسبة ، 18 (6): 1149-1178 ، CiteSeerX 10.1.1.431.4190 ، doi : 10.1137/0218077 ، ISSN 1095-7111  
  8. ↑ هالبرن، جوزيف ؛ موسى، يورام (1990)، "المعرفة والمعرفة المشتركة في بيئة موزعة" (ملف PDF) ، مجلة ACM ، 37 (3): 549-587 ، arXiv : cs/0006009 ، doi : 10.1145/79147.79161 ، S2CID 52151232 
  9. ↑ تودا، سينوسوكي (1991)، "مسألة البرمجة متعددة الحدود صعبة مثل التسلسل الهرمي ذي الوقت متعدد الحدود" (ملف PDF) ، مجلة SIAM للحوسبة ، 20 (5): 865-877 ، CiteSeerX 10.1.1.121.1246 ، doi : 10.1137/0220053 ، ISSN 1095-7111 ، مؤرشف من الأصل (ملف PDF) بتاريخ 2016-03-03 ، تم استرجاعه بتاريخ 2010-06-08  
  10. ↑ شور، بيتر و. (1997)، "خوارزميات زمنية متعددة الحدود لتحليل الأعداد الأولية واللوغاريتمات المنفصلة على حاسوب كمومي"، مجلة SIAM للحوسبة ، 26 (5): 1484-1509 ، arXiv : quant-ph/9508027 ، doi : 10.1137/S0097539795293172 ، ISSN 1095-7111 ، S2CID 2337707  
  11. ↑ فاردي، موشيه ي.؛ وولبر، بيير (1994)، "الاستدلال حول الحسابات اللانهائية" (ملف PDF) ، المعلومات والحوسبة ، 115 (1): 1-37 ، doi : 10.1006/inco.1994.1092 ، hdl : 2268/116648 ، ISSN 0890-5401 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 25 أغسطس 2011 
  12. ↑ فيج، أورييل؛ غولدواسير، شافي؛ لوفاس، لازلو؛ صفرا، شموئيل؛ سيجيدي، ماريو (1996)، "البراهين التفاعلية وصعوبة تقريب الزمر" (ملف PDF) ، مجلة ACM ، 43 (2): 268-292 ، doi : 10.1145/226643.226652 ، ISSN 0004-5411 
  13. ↑ أرورا، سانجيف؛ صفرا، شموئيل (1998)، "التحقق الاحتمالي من البراهين: توصيف جديد لـ NP" (ملف PDF) ، مجلة ACM ، 45 (1): 70-122 ، doi : 10.1145/273865.273901 ، ISSN 0004-5411 ، S2CID 751563 ، مؤرشف من النسخة الأصلية (PDF) بتاريخ 10-06-2011  
  14. ↑ أرورا، سانجيف؛ لوند، كارستن؛ موتاني، راجيف؛ سودان، مادهو؛ سيجيدي، ماريو (1998)، "التحقق من البرهان وصعوبة مسائل التقريب" (ملف PDF) ، مجلة ACM ، 45 (3): 501-555 ، CiteSeerX 10.1.1.145.4652 ، doi : 10.1145/278298.278306 ، ISSN 0004-5411 ، S2CID 8561542 ، مؤرشف من النسخة الأصلية (PDF) بتاريخ 10 يونيو 2011   
  15. ↑ سينيزيرغ، جيرود (2001)، "L(A) = L(B)؟ نتائج قابلية الحسم من الأنظمة الرسمية الكاملة"، مجلة علوم الحاسوب النظرية ، 251 (1): 1-166 ، doi : 10.1016/S0304-3975(00)00285-1 ، ISSN 0304-3975 
  16. ↑ فروند، ي.؛ شابير، ر. إي. (1997)، "تعميم قائم على نظرية القرار للتعلم عبر الإنترنت وتطبيق على التعزيز" (ملف PDF) ، مجلة علوم الحاسوب والنظم ، 55 (1): 119-139 ، doi : 10.1006/jcss.1997.1504 ، ISSN 1090-2724 
  17. ↑ هيرليهي، موريس ؛ شافيت، نير (1999)، "البنية الطوبولوجية للحوسبة غير المتزامنة" (ملف PDF) ، مجلة ACM ، 46 (6): 858-923 ، CiteSeerX 10.1.1.78.1455 ، doi : 10.1145/331524.331529 ، S2CID 5797174  محاضرة جائزة غودل
  18. ↑ ساكس، مايكل ؛ زهاروغلو، فوتيوس (2000)، "استحالة الاتفاق على مجموعة k بدون انتظار : طوبولوجيا المعرفة العامة"، مجلة SIAM للحوسبة ، 29 (5): 1449-1483 ، doi : 10.1137/S0097539796307698
  19. ↑ ألون، نوغا ؛ ماتياس، يوسي؛ سيجيدي، ماريو (1999)، "التعقيد المكاني لتقريب لحظات التردد" (ملف PDF) ، مجلة علوم الحاسوب والأنظمة ، 58 (1): 137-147 ، doi : 10.1006/jcss.1997.1545. تم تقديمها لأول مرة في ندوة نظرية الحوسبة (STOC) في عام 1996.
  20. ↑ أغراوال، م.؛ كايال، ن.؛ ساكسينا، ن. (2004)، "الأعداد الأولية تنتمي إلى P"، حوليات الرياضيات ، 160 (2): 781-793 ، doi : 10.4007/annals.2004.160.781 ، ISSN 0003-486X 
  21. ↑ رازبوروف، ألكسندر أ.؛ روديتش، ستيفن (1997)، "البراهين الطبيعية"، مجلة علوم الحاسوب والأنظمة ، 55 (1): 24-35 ، doi : 10.1006/jcss.1997.1494 ، ISSN 0022-0000 ، ECCC TR94-010  
  22. ↑ سبيلمان، دانيال أ.؛ تينغ، شانغ هوا (2004)، "تحليل مُبسّط للخوارزميات: لماذا تستغرق خوارزمية سيمبلكس عادةً وقتًا متعدد الحدود"، مجلة ACM ، 51 (3): 385-463 ، arXiv : math/0212413 ، doi : 10.1145/990308.990310 ، ISSN 0004-5411 
  23. ↑ رينغولد، عمر؛ فادان، ساليل؛ ويغدرسون، آفي (2002)، "موجات الإنتروبيا، وحاصل ضرب الرسم البياني المتعرج، وموسعات جديدة ذات درجة ثابتة"، حوليات الرياضيات ، 155 (1): 157-187 ، CiteSeerX 10.1.1.236.8669 ، doi : 10.2307/3062153 ، ISSN 0003-486X ، JSTOR 3062153 ، MR 1888797 ، S2CID 120739405     
  24. ↑ رينغولد، عمر (2008)، "الاتصال غير الموجه في فضاء لوغاريتمي" ، مجلة ACM ، 55 (4): 1-24 ، doi : 10.1145/1391289.1391291 ، ISSN 0004-5411 ، S2CID 207168478  
  25. ↑ أرورا، سانجيف (1998)، "مخططات تقريبية متعددة الحدود لمسألة البائع المتجول الإقليدية وغيرها من المسائل الهندسية"، مجلة ACM ، 45 (5): 753-782 ، CiteSeerX 10.1.1.23.6765 ، doi : 10.1145/290179.290180 ، ISSN 0004-5411 ، S2CID 3023351   
  26. ↑ ميتشل، جوزيف إس بي (1999)، "تقسيمات المقصلة تقارب التقسيمات المضلعة: مخطط تقريبي بسيط متعدد الحدود لمسألة البائع المتجول الهندسية، ومسألة الشجرة الممتدة الدنيا k، والمسائل ذات الصلة"، مجلة SIAM للحوسبة ، 28 (4): 1298-1309 ، doi : 10.1137/S0097539796309764 ، ISSN 1095-7111 
  27. ↑ هاستاد، يوهان (2001)، "بعض نتائج عدم التقريب الأمثل" (ملف PDF) ، مجلة ACM ، 48 (4): 798-859 ، CiteSeerX 10.1.1.638.2808 ، doi : 10.1145/502090.502098 ، ISSN 0004-5411 ، S2CID 5120748   
  28. ^ إلياس كوتسوبياس. باباديمتريو، كريستوس (2009). “التوازنات الأسوأ”. مراجعة علوم الكمبيوتر . 3 (2): 65-69 . دوى : 10.1016/j.cosrev.2009.04.003 .
  29. ↑ رافغاردن، تيم؛ تاردوس، إيفا (2002). "ما مدى سوء التوجيه الأناني؟". مجلة ACM . 49 (2): 236-259 . CiteSeerX 10.1.1.147.1081 . doi : 10.1145/506147.506153 . S2CID 207638789 .  
  30. ↑ نيسان، نوام؛ رونين، أمير (2001). "تصميم الآليات الخوارزمية". الألعاب والسلوك الاقتصادي . 35 ( 1-2 ): 166-196 . CiteSeerX 10.1.1.21.1731 . doi : 10.1006/game.1999.0790 . 
  31. ↑ بونيه، دان؛ فرانكلين، ماثيو (2003). "التشفير القائم على الهوية من اقتران ويل". مجلة SIAM للحوسبة . 32 (3): 586-615 . CiteSeerX 10.1.1.66.1131 . doi : 10.1137/S0097539701398521 . MR 2001745 .  
  32. ↑ جوكس، أنطوان (2004). " بروتوكول جولة واحدة لخوارزمية ديفي-هيلمان الثلاثية" . مجلة علم التشفير . 17 (4): 263-276 . doi : 10.1007/s00145-004-0312-y . MR 2090557. S2CID 3350730 .  
  33. ↑ فاجين، رونالد؛ لوتيم، أمنون؛ ناور، موني (2003). "خوارزميات التجميع الأمثل للبرمجيات الوسيطة". مجلة علوم الحاسوب والنظم . 66 (4): 614-656 . arXiv : cs/0204046 . doi : 10.1016/S0022-0000(03)00026-6 .
  34. ↑ سبيلمان، دانيال أ.؛ تينغ، شانغ هوا (2011). "التخفيف الطيفي للرسوم البيانية". مجلة SIAM للحوسبة . 40 (4): 981-1025 . arXiv : 0808.4134 . doi : 10.1137/08074489X . ISSN 0097-5397 . S2CID 9646279 .  
  35. ↑ سبيلمان، دانيال أ.؛ تينغ، شانغ هوا (2013). "خوارزمية تجميع محلية للرسوم البيانية الضخمة وتطبيقها على تقسيم الرسوم البيانية في وقت شبه خطي". مجلة SIAM للحوسبة . 42 (1): 1-26 . arXiv : 0809.3232 . doi : 10.1137/080744888 . ISSN 0097-5397 . S2CID 9151077 .  
  36. ↑ سبيلمان، دانيال أ.؛ تينغ، شانغ هوا (2014). "خوارزميات شبه خطية للمعالجة المسبقة وحل الأنظمة الخطية المتناظرة ذات الهيمنة القطرية". مجلة SIAM لتحليل المصفوفات وتطبيقاتها . 35 (3): 835-885 . arXiv : cs/0607105 . doi : 10.1137/090771430 . ISSN 0895-4798 . S2CID 1750944 .  
  37. ↑ بروكس، ستيفن (2007). "دلالات منطق الفصل المتزامن" (ملف PDF) . علوم الحاسوب النظرية . 375 ( 1-3 ): 227-270 . doi : 10.1016/j.tcs.2006.12.034 .
  38. ↑ أوهيرن، بيتر (2007). "الموارد، والتزامن، والاستدلال المحلي" (ملف PDF) . علوم الحاسوب النظرية . 375 ( 1-3 ): 271-307 . doi : 10.1016/j.tcs.2006.12.035 .
  39. ↑ دورك، سينثيا؛ ماكشيري، فرانك؛ نسيم، كوبي؛ سميث، آدم (2006). هاليفي، شاي؛ رابين، تال (محررون). معايرة الضوضاء للحساسية في تحليل البيانات الخاصة . نظرية التشفير (TCC). سلسلة محاضرات في علوم الحاسوب. المجلد 3876. سبرينغر-فيرلاغ. الصفحات 265-284 . doi : 10.1007/11681878_14 . ISBN   978-3-540-32731-8.
  40. ↑ ريغيف، أوديد (2009). "حول الشبكات، والتعلم مع الأخطاء، والرموز الخطية العشوائية، والتشفير". مجلة ACM . 56 (6): 1-40 . CiteSeerX 10.1.1.215.3543 . doi : 10.1145/1568318.1568324 . S2CID 207156623 .  
  41. ^ دينور، إيريت (2007). "نظرية PCP عن طريق تضخيم الفجوة" . مجلة ACM . 54 (3): 12-و. دوى : 10.1145/1236457.1236459 . S2CID 53244523 . 
  42. ↑ "برهان بنائي لفرضية لوفاس المحلية العامة". مجلة ACM . 57 (2). 2010. doi : 10.1145/1667053 . ISSN 0004-5411 . 
  43. ↑ بولاتوف، أندريه أ. (2013). "تعقيد مسألة إرضاء قيود العد". مجلة ACM . 60 (5). رابطة آلات الحوسبة: 1-41 . doi : 10.1145/2528400 . ISSN 0004-5411 . S2CID 8964233 .  
  44. ↑ داير، مارتن؛ ريتشربي، ديفيد (2013). "ثنائية فعالة لمسألة إرضاء قيود العد". مجلة SIAM للحوسبة . 42 (3). جمعية الرياضيات الصناعية والتطبيقية (SIAM): 1245-1274 . arXiv : 1003.3879 . doi : 10.1137/100811258 . ISSN 0097-5397 . S2CID 1247279 .  
  45. ↑ كاي، جين-يي؛ تشين، شي (22-06-2017). "تعقيد عدّ مسائل إرضاء القيود ذات الأوزان المركبة". مجلة ACM . 64 (3). رابطة آلات الحوسبة: 1-39 . arXiv : 1111.2384 . doi : 10.1145/2822891 . ISSN 0004-5411 . S2CID 1053684 .  
  46. ^ براكرسكي، زفيكا؛ فايكونتاناثان ، فينود (يناير 2014). "تشفير متماثل فعال بالكامل من (قياسي) $\mathsf{LWE}$" . مجلة SIAM للحوسبة . 43 (2): 831-871 . دوى : 10.1137 / 120868669 . اتش دي ال : 1721.1/115488 . ISSN 0097-5397 . S2CID 8831240 .  
  47. ↑ براكرسكي، زفيكا؛ جينتري، كريج؛ فايكونتاناثان، فينود (2012). "التشفير المتماثل الكامل (المُدرّج) بدون تمهيد" . وقائع المؤتمر الثالث للابتكارات في علوم الحاسوب النظرية . نيويورك، نيويورك، الولايات المتحدة الأمريكية: مطبعة ACM. الصفحات 309-325 . doi : 10.1145/2090236.2090262 . ISBN  9781450311151. S2CID 2602543 . 
  48. ^ فيوريني، صموئيل. مسار، سيرج؛ بوكوتا، سيباستيان. تيواري، هانز راج؛ دي وولف، رونالد (2015). "الحدود الدنيا الأسية للبوليتوبس في التحسين التوافقي" . مجلة ACM . 62 (2): 17: 1-17:23. أرخايف : 1111.0837 . دوى : 10.1145/2716307 . S2CID 7372000 . 
  49. ↑ روثفوس، توماس (2017). "متعدد السطوح المطابق ذو تعقيد امتداد أسي" . مجلة ACM . 64 (6): 41:1–41:19. arXiv : 1311.2369 . doi : 10.1145/3127497 . S2CID 47045361 . 
  50. ↑ ويليامز، رايان (يونيو 2011). "الحدود الدنيا لدائرة ACC غير المنتظمة" . المؤتمر السنوي السادس والعشرون لمعهد مهندسي الكهرباء والإلكترونيات ( IEEE) حول التعقيد الحسابي، 2011. معهد مهندسي الكهرباء والإلكترونيات. الصفحات 115-125 . doi : 10.1109/ccc.2011.36 . ISBN  978-1-4577-0179-5.
  51. ↑ تشاتوبادياي، إيشان؛ زوكرمان، ديفيد (يونيو 2016). "مستخلصات صريحة ثنائية المصدر ووظائف مرنة" . وقائع الندوة السنوية الثامنة والأربعين لجمعية ACM حول نظرية الحوسبة . ACM. الصفحات 670-683 . doi : 10.1145/2897518.2897528 . ISBN  978-1-4503-4132-5.
  52. ↑ دياكونيكولاس، إلياس؛ كاماث، غوتام؛ كين، دانيال؛ لي، جيري؛ مويترا، أنكور؛ ستيوارت، أليستير (2019). "مُقدِّرات قوية في الأبعاد العالية دون تعقيدات حسابية". مجلة SIAM للحوسبة . 48 (2): 742-864 . arXiv : 1604.06443 . doi : 10.1137/17M1126680 .

انظر أيضاً

ملحوظات

  1. ↑ "رسالة غودل" . 2009-02-12.
  2. 1 2 "جائزة غودل لعام 2017" . الرابطة الأوروبية لعلوم الحاسوب النظرية . EATCS . ​​تم الاطلاع عليه بتاريخ 29 مارس 2017 .
  3. ↑ "ثلاث أوراق بحثية استُشهد بها لوضع أسس النمو في نظرية الألعاب الخوارزمية" . 16 مايو 2012. مؤرشف من الأصل في 18 يوليو 2013. تم الاطلاع عليه في 16 مايو 2012 .
  4. ↑ مجموعة ACM تقدم جائزة غودل للتقدم في علم التشفير: تكريم ثلاثة علماء حاسوب لابتكارات تعمل على تحسين الأمن. مؤرشف في 2013-06-01 في Wayback Machine ، جمعية آلات الحوسبة ، 29 مايو 2013.
  5. ↑ حقق المستفيدون نتائج رائدة في تجميع البيانات من مصادر متعددة ، رابطة آلات الحوسبة ، 30 أبريل 2014.
  6. ↑ إعلان جائزة غودل لعام 2015 مؤرشف بتاريخ 2017-12-09 في Wayback Machine بواسطة جمعية آلات الحوسبة .
  7. ↑ "بيان جائزة غودل لعام 2018" .
  8. ↑ "بيان جائزة غودل لعام 2019" .
  9. ↑ "بيان جائزة غودل لعام 2020" .
  10. ↑ "بيان جائزة غودل لعام 2021" .
  11. ↑ "بيان جائزة غودل لعام 2022" . EATCS .
  12. ↑ "بيان جائزة غودل لعام 2023" . EATCS .
  13. ↑ "بيان جائزة غودل لعام 2024" . EATCS .
  14. ↑ "بيان جائزة غودل لعام 2025" .
  15. ↑ "جائزة غودل لعام 2026" .

مراجع