CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Gödel Prize - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"325219c9-8197-437e-8a40-a0c963fab7d1","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Gödel_Prize","wgTitle":"Gödel Prize","wgCurRevisionId":1239821267,"wgRevisionId":1239821267,"wgArticleId":643342,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["All articles with dead external links","Articles with dead external links from December 2017","Articles with permanently dead external links","Webarchive template wayback links","Articles with short description","Short description is different from Wikidata","Theoretical computer science","Computer science awards","Awards established in 1993","Annual events"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Gödel_Prize", "wgRelevantArticleId":643342,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":30000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1417143","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform", "platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.tablesorter.styles":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.tablesorter","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp", "ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cjquery.tablesorter.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/c/c1/1925_kurt_g%C3%B6del.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1554"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/c/c1/1925_kurt_g%C3%B6del.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="1036"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="829"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Gödel Prize - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/G%C3%B6del_Prize"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=G%C3%B6del_Prize&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/G%C3%B6del_Prize"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Gödel_Prize rootpage-Gödel_Prize skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=G%C3%B6del+Prize" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=G%C3%B6del+Prize" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=G%C3%B6del+Prize" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=G%C3%B6del+Prize" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Recipients" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Recipients"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Recipients</span> </div> </a> <ul id="toc-Recipients-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Winning_papers" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Winning_papers"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Winning papers</span> </div> </a> <ul id="toc-Winning_papers-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Gödel Prize</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 20 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-20" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">20 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D8%AC%D8%A7%D8%A6%D8%B2%D8%A9_%D8%AC%D9%88%D8%AF%D9%84" title="جائزة جودل – Arabic" lang="ar" hreflang="ar" data-title="جائزة جودل" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/Premi_G%C3%B6del" title="Premi Gödel – Catalan" lang="ca" hreflang="ca" data-title="Premi Gödel" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/G%C3%B6delova_cena" title="Gödelova cena – Czech" lang="cs" hreflang="cs" data-title="Gödelova cena" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/G%C3%B6del-Preis" title="Gödel-Preis – German" lang="de" hreflang="de" data-title="Gödel-Preis" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Premio_G%C3%B6del" title="Premio Gödel – Spanish" lang="es" hreflang="es" data-title="Premio Gödel" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AC%D8%A7%DB%8C%D8%B2%D9%87_%DA%AF%D9%88%D8%AF%D9%84" title="جایزه گودل – Persian" lang="fa" hreflang="fa" data-title="جایزه گودل" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Prix_G%C3%B6del" title="Prix Gödel – French" lang="fr" hreflang="fr" data-title="Prix Gödel" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-gl mw-list-item"><a href="https://gl.wikipedia.org/wiki/Premio_G%C3%B6del" title="Premio Gödel – Galician" lang="gl" hreflang="gl" data-title="Premio Gödel" data-language-autonym="Galego" data-language-local-name="Galician" class="interlanguage-link-target"><span>Galego</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B4%B4%EB%8D%B8%EC%83%81" title="괴델상 – Korean" lang="ko" hreflang="ko" data-title="괴델상" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Premio_G%C3%B6del" title="Premio Gödel – Italian" lang="it" hreflang="it" data-title="Premio Gödel" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A4%D7%A8%D7%A1_%D7%92%D7%93%D7%9C" title="פרס גדל – Hebrew" lang="he" hreflang="he" data-title="פרס גדל" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ka mw-list-item"><a href="https://ka.wikipedia.org/wiki/%E1%83%92%E1%83%98%E1%83%9D%E1%83%93%E1%83%94%E1%83%9A%E1%83%98%E1%83%A1_%E1%83%9E%E1%83%A0%E1%83%94%E1%83%9B%E1%83%98%E1%83%90" title="გიოდელის პრემია – Georgian" lang="ka" hreflang="ka" data-title="გიოდელის პრემია" data-language-autonym="ქართული" data-language-local-name="Georgian" class="interlanguage-link-target"><span>ქართული</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%87%E3%83%AB%E8%B3%9E" title="ゲーデル賞 – Japanese" lang="ja" hreflang="ja" data-title="ゲーデル賞" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Nagroda_G%C3%B6dla" title="Nagroda Gödla – Polish" lang="pl" hreflang="pl" data-title="Nagroda Gödla" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Pr%C3%AAmio_G%C3%B6del" title="Prêmio Gödel – Portuguese" lang="pt" hreflang="pt" data-title="Prêmio Gödel" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BC%D0%B8%D1%8F_%D0%93%D1%91%D0%B4%D0%B5%D0%BB%D1%8F" title="Премия Гёделя – Russian" lang="ru" hreflang="ru" data-title="Премия Гёделя" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sk mw-list-item"><a href="https://sk.wikipedia.org/wiki/G%C3%B6delova_cena" title="Gödelova cena – Slovak" lang="sk" hreflang="sk" data-title="Gödelova cena" data-language-autonym="Slovenčina" data-language-local-name="Slovak" class="interlanguage-link-target"><span>Slovenčina</span></a></li><li class="interlanguage-link interwiki-tr mw-list-item"><a href="https://tr.wikipedia.org/wiki/G%C3%B6del_%C3%96d%C3%BCl%C3%BC" title="Gödel Ödülü – Turkish" lang="tr" hreflang="tr" data-title="Gödel Ödülü" data-language-autonym="Türkçe" data-language-local-name="Turkish" class="interlanguage-link-target"><span>Türkçe</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BC%D1%96%D1%8F_%D0%93%D0%B5%D0%B4%D0%B5%D0%BB%D1%8F" title="Премія Геделя – Ukrainian" lang="uk" hreflang="uk" data-title="Премія Геделя" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%93%A5%E5%BE%B7%E5%B0%94%E5%A5%96" title="哥德尔奖 – Chinese" lang="zh" hreflang="zh" data-title="哥德尔奖" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1417143#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/G%C3%B6del_Prize" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:G%C3%B6del_Prize" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/G%C3%B6del_Prize"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=G%C3%B6del_Prize&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=G%C3%B6del_Prize&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/G%C3%B6del_Prize"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=G%C3%B6del_Prize&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=G%C3%B6del_Prize&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/G%C3%B6del_Prize" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/G%C3%B6del_Prize" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=G%C3%B6del_Prize&oldid=1239821267" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=G%C3%B6del_Prize&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=G%C3%B6del_Prize&id=1239821267&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FG%25C3%25B6del_Prize"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FG%25C3%25B6del_Prize"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=G%C3%B6del_Prize&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=G%C3%B6del_Prize&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Laureates_of_the_G%C3%B6del_Prize" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q1417143" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Computer science award</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with the <a href="/wiki/G%C3%B6del_Lecture" title="Gödel Lecture">Gödel Lecture</a>.</div> <figure class="mw-default-size mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:1925_kurt_g%C3%B6del.png" class="mw-file-description"><img alt="Kurt Gödel" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c1/1925_kurt_g%C3%B6del.png/220px-1925_kurt_g%C3%B6del.png" decoding="async" width="220" height="285" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c1/1925_kurt_g%C3%B6del.png/330px-1925_kurt_g%C3%B6del.png 1.5x, //upload.wikimedia.org/wikipedia/commons/c/c1/1925_kurt_g%C3%B6del.png 2x" data-file-width="397" data-file-height="514" /></a><figcaption> Kurt Gödel</figcaption></figure> <p>The <b>Gödel Prize</b> is an annual prize for outstanding papers in the area of <a href="/wiki/Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>, given jointly by the <a href="/wiki/European_Association_for_Theoretical_Computer_Science" title="European Association for Theoretical Computer Science">European Association for Theoretical Computer Science</a> (EATCS) and the <a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a> Special Interest Group on Algorithms and Computational Theory (<a href="/wiki/ACM_SIGACT" title="ACM SIGACT">ACM SIGACT</a>). The award is named in honor of <a href="/wiki/Kurt_G%C3%B6del" title="Kurt Gödel">Kurt Gödel</a>. Gödel's connection to theoretical computer science is that he was the first to mention the "<a href="/wiki/P_versus_NP" class="mw-redirect" title="P versus NP">P versus NP</a>" question, in a 1956 letter to <a href="/wiki/John_von_Neumann" title="John von Neumann">John von Neumann</a> in which Gödel asked whether a certain <a href="/wiki/NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> problem could be solved in <a href="/wiki/Quadratic_time" class="mw-redirect" title="Quadratic time">quadratic</a> or <a href="/wiki/Linear_time" class="mw-redirect" title="Linear time">linear time</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>The Gödel Prize has been awarded since 1993. The prize is awarded alternately at ICALP (even years) and STOC (odd years). STOC is the ACM <a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a>, one of the main <a href="/wiki/North_American" class="mw-redirect" title="North American">North American</a> conferences in theoretical computer science, whereas ICALP is the <a href="/wiki/International_Colloquium_on_Automata,_Languages_and_Programming" title="International Colloquium on Automata, Languages and Programming">International Colloquium on Automata, Languages and Programming</a>, one of the main <a href="/wiki/Europe" title="Europe">European</a> conferences in the field. To be eligible for the prize, a paper must be published in a refereed journal within the last 14 (formerly 7) years. The prize includes a reward of US$5000.<sup id="cite_ref-Godël2017_2-0" class="reference"><a href="#cite_note-Godël2017-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>The winner of the Prize is selected by a committee of six members. The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms. The committee is chaired alternately by representatives of EATCS and SIGACT. </p><p>In contrast with the Gödel Prize, which recognizes outstanding papers, the <a href="/wiki/Knuth_Prize" title="Knuth Prize">Knuth Prize</a> is awarded to individuals for their overall impact in the field. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Recipients">Recipients</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del_Prize&action=edit&section=1" title="Edit section: Recipients"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <table class="wikitable sortable"> <tbody><tr> <th>Year </th> <th width="40%" class="unsortable">Name(s) </th> <th width="45%" class="unsortable">Notes </th> <th>Publication year </th></tr> <tr valign="top"> <td>1993</td> <td><a href="/wiki/L%C3%A1szl%C3%B3_Babai" title="László Babai">László Babai</a>, <a href="/wiki/Shafi_Goldwasser" title="Shafi Goldwasser">Shafi Goldwasser</a>, <a href="/wiki/Silvio_Micali" title="Silvio Micali">Silvio Micali</a>, <a href="/wiki/Shlomo_Moran" title="Shlomo Moran">Shlomo Moran</a>, and <a href="/wiki/Charles_Rackoff" title="Charles Rackoff">Charles Rackoff</a></td> <td>for the development of <a href="/wiki/Interactive_proof_system" title="Interactive proof system">interactive proof systems</a></td> <td>1988,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>paper 1<span class="cite-bracket">]</span></a></sup> 1989<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>paper 2<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>1994</td> <td><a href="/wiki/Johan_H%C3%A5stad" title="Johan Håstad">Johan Håstad</a></td> <td>for an exponential <a href="/wiki/Lower_bound" class="mw-redirect" title="Lower bound">lower bound</a> on <a href="/wiki/Circuit_complexity" title="Circuit complexity">the size of</a> constant-depth <a href="/wiki/Boolean_circuits" class="mw-redirect" title="Boolean circuits">Boolean circuits</a> (for the <a href="/wiki/Parity_function" title="Parity function">parity function</a>).</td> <td>1989<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>paper 3<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>1995</td> <td><a href="/wiki/Neil_Immerman" title="Neil Immerman">Neil Immerman</a> and <a href="/wiki/R%C3%B3bert_Szelepcs%C3%A9nyi" title="Róbert Szelepcsényi">Róbert Szelepcsényi</a></td> <td>for the <a href="/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem" title="Immerman–Szelepcsényi theorem">Immerman–Szelepcsényi theorem</a> regarding nondeterministic space complexity</td> <td>1988,<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>paper 4<span class="cite-bracket">]</span></a></sup> 1988<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>paper 5<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>1996</td> <td><a href="/wiki/Mark_Jerrum" title="Mark Jerrum">Mark Jerrum</a> and <a href="/wiki/Alistair_Sinclair" title="Alistair Sinclair">Alistair Sinclair</a></td> <td>for work on <a href="/wiki/Markov_chains" class="mw-redirect" title="Markov chains">Markov chains</a> and the approximation of the <a href="/wiki/Permanent_(mathematics)" title="Permanent (mathematics)">permanent of a matrix</a></td> <td>1989,<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>paper 6<span class="cite-bracket">]</span></a></sup> 1989<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>paper 7<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>1997</td> <td><a href="/wiki/Joseph_Halpern" title="Joseph Halpern">Joseph Halpern</a> and <a href="/wiki/Yoram_Moses" title="Yoram Moses">Yoram Moses</a></td> <td>for defining a formal notion of "knowledge" in distributed environments</td> <td>1990<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>paper 8<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>1998</td> <td><a href="/wiki/Seinosuke_Toda" title="Seinosuke Toda">Seinosuke Toda</a></td> <td>for <a href="/wiki/Toda%27s_theorem" title="Toda's theorem">Toda's theorem</a>, which showed a connection between counting solutions (<a href="/wiki/PP_(complexity)" title="PP (complexity)">PP</a>) and alternation of quantifiers (<a href="/wiki/PH_(complexity)" title="PH (complexity)">PH</a>)</td> <td>1991<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>paper 9<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>1999</td> <td><a href="/wiki/Peter_Shor" title="Peter Shor">Peter Shor</a></td> <td>for <a href="/wiki/Shor%27s_algorithm" title="Shor's algorithm">Shor's algorithm</a> for <a href="/wiki/Integer_factorization" title="Integer factorization">factoring</a> numbers in <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> on a <a href="/wiki/Quantum_computer" class="mw-redirect" title="Quantum computer">quantum computer</a></td> <td>1997<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>paper 10<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2000</td> <td><a href="/wiki/Moshe_Y._Vardi" class="mw-redirect" title="Moshe Y. Vardi">Moshe Y. Vardi</a> and <a href="/wiki/Pierre_Wolper" title="Pierre Wolper">Pierre Wolper</a></td> <td>for work on <a href="/wiki/Temporal_logic" title="Temporal logic">temporal logic</a> with <a href="/wiki/Finite_automata" class="mw-redirect" title="Finite automata">finite automata</a></td> <td>1994<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>paper 11<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2001</td> <td><a href="/wiki/Sanjeev_Arora" title="Sanjeev Arora">Sanjeev Arora</a>, <a href="/wiki/Uriel_Feige" title="Uriel Feige">Uriel Feige</a>, <a href="/wiki/Shafi_Goldwasser" title="Shafi Goldwasser">Shafi Goldwasser</a>, <a href="/wiki/Carsten_Lund" title="Carsten Lund">Carsten Lund</a>, <a href="/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">László Lovász</a>, <a href="/wiki/Rajeev_Motwani" title="Rajeev Motwani">Rajeev Motwani</a>, <a href="/wiki/Shmuel_Safra" title="Shmuel Safra">Shmuel Safra</a>, <a href="/wiki/Madhu_Sudan" title="Madhu Sudan">Madhu Sudan</a>, and <a href="/wiki/Mario_Szegedy" title="Mario Szegedy">Mario Szegedy</a></td> <td>for the <a href="/wiki/PCP_theorem" title="PCP theorem">PCP theorem</a> and its applications to hardness of approximation</td> <td>1996,<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>paper 12<span class="cite-bracket">]</span></a></sup> 1998,<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>paper 13<span class="cite-bracket">]</span></a></sup> 1998<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>paper 14<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2002</td> <td><a href="/wiki/G%C3%A9raud_S%C3%A9nizergues" title="Géraud Sénizergues">Géraud Sénizergues</a></td> <td>for proving that equivalence of <a href="/wiki/Deterministic_pushdown_automaton" title="Deterministic pushdown automaton">deterministic pushdown automata</a> is <a href="/wiki/Decidability_(logic)" title="Decidability (logic)">decidable</a></td> <td>2001<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>paper 15<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2003</td> <td><a href="/wiki/Yoav_Freund" title="Yoav Freund">Yoav Freund</a> and <a href="/wiki/Robert_Schapire" title="Robert Schapire">Robert Schapire</a></td> <td>for the <a href="/wiki/AdaBoost" title="AdaBoost">AdaBoost</a> algorithm in <a href="/wiki/Machine_learning" title="Machine learning">machine learning</a></td> <td>1997<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>paper 16<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2004</td> <td><a href="/wiki/Maurice_Herlihy" title="Maurice Herlihy">Maurice Herlihy</a>, <a href="/wiki/Michael_Saks_(mathematician)" title="Michael Saks (mathematician)">Michael Saks</a>, <a href="/wiki/Nir_Shavit" title="Nir Shavit">Nir Shavit</a> and <a href="/wiki/Fotios_Zaharoglou" title="Fotios Zaharoglou">Fotios Zaharoglou</a></td> <td>for applications of <a href="/wiki/Topology" title="Topology">topology</a> to the theory of <a href="/wiki/Distributed_computing" title="Distributed computing">distributed computing</a></td> <td>1999,<sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>paper 17<span class="cite-bracket">]</span></a></sup> 2000<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>paper 18<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2005</td> <td><a href="/wiki/Noga_Alon" title="Noga Alon">Noga Alon</a>, <a href="/wiki/Yossi_Matias" title="Yossi Matias">Yossi Matias</a> and <a href="/wiki/Mario_Szegedy" title="Mario Szegedy">Mario Szegedy</a></td> <td>for their foundational contribution to <a href="/wiki/Streaming_algorithm" title="Streaming algorithm">streaming algorithms</a></td> <td>1999<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>paper 19<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2006</td> <td><a href="/wiki/Manindra_Agrawal" title="Manindra Agrawal">Manindra Agrawal</a>, <a href="/wiki/Neeraj_Kayal" title="Neeraj Kayal">Neeraj Kayal</a>, <a href="/wiki/Nitin_Saxena" title="Nitin Saxena">Nitin Saxena</a></td> <td>for the <a href="/wiki/AKS_primality_test" title="AKS primality test">AKS primality test</a></td> <td>2004<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>paper 20<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2007</td> <td><a href="/wiki/Alexander_Razborov" title="Alexander Razborov">Alexander Razborov</a>, <a href="/wiki/Steven_Rudich" title="Steven Rudich">Steven Rudich</a></td> <td>for <a href="/wiki/Natural_proof" title="Natural proof">natural proofs</a></td> <td>1997<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>paper 21<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2008</td> <td><a href="/wiki/Daniel_Spielman" title="Daniel Spielman">Daniel Spielman</a>, <a href="/wiki/Shanghua_Teng" class="mw-redirect" title="Shanghua Teng">Shang-Hua Teng</a></td> <td>for <a href="/wiki/Smoothed_analysis" title="Smoothed analysis">smoothed analysis</a> of algorithms</td> <td>2004<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>paper 22<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2009</td> <td><a href="/wiki/Omer_Reingold" title="Omer Reingold">Omer Reingold</a>, <a href="/wiki/Salil_Vadhan" title="Salil Vadhan">Salil Vadhan</a>, <a href="/wiki/Avi_Wigderson" title="Avi Wigderson">Avi Wigderson</a></td> <td>for <a href="/wiki/Zig-zag_product" title="Zig-zag product">zig-zag product</a> of <a href="/wiki/Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graphs</a> and <a href="/wiki/USTCON" class="mw-redirect" title="USTCON">undirected connectivity</a> in <a href="/wiki/Log_space" class="mw-redirect" title="Log space">log space</a></td> <td>2002,<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>paper 23<span class="cite-bracket">]</span></a></sup> 2008<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>paper 24<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2010</td> <td><a href="/wiki/Sanjeev_Arora" title="Sanjeev Arora">Sanjeev Arora</a>, <a href="/wiki/Joseph_S._B._Mitchell" title="Joseph S. B. Mitchell">Joseph S. B. Mitchell</a></td> <td>for their concurrent discovery of a <a href="/wiki/Polynomial-time_approximation_scheme" title="Polynomial-time approximation scheme">polynomial-time approximation scheme</a> for the Euclidean <a href="/wiki/Travelling_Salesman_Problem" class="mw-redirect" title="Travelling Salesman Problem">Travelling Salesman Problem</a></td> <td>1998,<sup id="cite_ref-27" class="reference"><a href="#cite_note-27"><span class="cite-bracket">[</span>paper 25<span class="cite-bracket">]</span></a></sup> 1999<sup id="cite_ref-28" class="reference"><a href="#cite_note-28"><span class="cite-bracket">[</span>paper 26<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2011</td> <td><a href="/wiki/Johan_H%C3%A5stad" title="Johan Håstad">Johan Håstad</a></td> <td>for proving optimal inapproximability results for various combinatorial problems</td> <td>2001<sup id="cite_ref-29" class="reference"><a href="#cite_note-29"><span class="cite-bracket">[</span>paper 27<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2012</td> <td><a href="/wiki/Elias_Koutsoupias" title="Elias Koutsoupias">Elias Koutsoupias</a>, <a href="/wiki/Christos_Papadimitriou" title="Christos Papadimitriou">Christos Papadimitriou</a>, <a href="/wiki/Noam_Nisan" title="Noam Nisan">Noam Nisan</a>, <a href="/wiki/Amir_Ronen" title="Amir Ronen">Amir Ronen</a>, <a href="/wiki/Tim_Roughgarden" title="Tim Roughgarden">Tim Roughgarden</a> and <a href="/wiki/%C3%89va_Tardos" title="Éva Tardos">Éva Tardos</a></td> <td>for laying the foundations of <a href="/wiki/Algorithmic_game_theory" title="Algorithmic game theory">algorithmic game theory</a><sup id="cite_ref-sigact-2012_30-0" class="reference"><a href="#cite_note-sigact-2012-30"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></td> <td>2009,<sup id="cite_ref-31" class="reference"><a href="#cite_note-31"><span class="cite-bracket">[</span>paper 28<span class="cite-bracket">]</span></a></sup> 2002,<sup id="cite_ref-32" class="reference"><a href="#cite_note-32"><span class="cite-bracket">[</span>paper 29<span class="cite-bracket">]</span></a></sup> 2001<sup id="cite_ref-33" class="reference"><a href="#cite_note-33"><span class="cite-bracket">[</span>paper 30<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2013</td> <td><a href="/wiki/Dan_Boneh" title="Dan Boneh">Dan Boneh</a>, <a href="/wiki/Matthew_K._Franklin" title="Matthew K. Franklin">Matthew K. Franklin</a>, and <a href="/wiki/Antoine_Joux" title="Antoine Joux">Antoine Joux</a></td> <td>for multi-party <a href="/wiki/Diffie%E2%80%93Hellman_key_exchange" title="Diffie–Hellman key exchange">Diffie–Hellman key exchange</a> and the <a href="/wiki/Boneh%E2%80%93Franklin_scheme" title="Boneh–Franklin scheme">Boneh–Franklin scheme</a> in cryptography<sup id="cite_ref-34" class="reference"><a href="#cite_note-34"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></td> <td>2003,<sup id="cite_ref-35" class="reference"><a href="#cite_note-35"><span class="cite-bracket">[</span>paper 31<span class="cite-bracket">]</span></a></sup> <p>2004<sup id="cite_ref-36" class="reference"><a href="#cite_note-36"><span class="cite-bracket">[</span>paper 32<span class="cite-bracket">]</span></a></sup> </p> </td></tr> <tr valign="top"> <td>2014</td> <td><a href="/wiki/Ronald_Fagin" title="Ronald Fagin">Ronald Fagin</a>, <a href="/w/index.php?title=Amnon_Lotem&action=edit&redlink=1" class="new" title="Amnon Lotem (page does not exist)">Amnon Lotem</a><span class="noprint" style="font-size:85%; font-style: normal;"> [<a href="https://fr.wikipedia.org/wiki/Amnon_Lotem" class="extiw" title="fr:Amnon Lotem">fr</a>]</span>, and <a href="/wiki/Moni_Naor" title="Moni Naor">Moni Naor</a></td> <td>for Optimal Aggregation Algorithms for <a href="/wiki/Middleware" title="Middleware">middleware</a><sup id="cite_ref-37" class="reference"><a href="#cite_note-37"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></td> <td>2003,<sup id="cite_ref-38" class="reference"><a href="#cite_note-38"><span class="cite-bracket">[</span>paper 33<span class="cite-bracket">]</span></a></sup> </td></tr> <tr valign="top"> <td>2015</td> <td><a href="/wiki/Daniel_Spielman" title="Daniel Spielman">Daniel Spielman</a>, <a href="/wiki/Shanghua_Teng" class="mw-redirect" title="Shanghua Teng">Shang-Hua Teng</a> </td> <td>for their series of papers on nearly-linear-time Laplacian solvers<sup id="cite_ref-39" class="reference"><a href="#cite_note-39"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup></td> <td> <p>2011<sup id="cite_ref-SpielmanTeng2011_40-0" class="reference"><a href="#cite_note-SpielmanTeng2011-40"><span class="cite-bracket">[</span>paper 34<span class="cite-bracket">]</span></a></sup> 2013<sup id="cite_ref-SpielmanTeng2013_41-0" class="reference"><a href="#cite_note-SpielmanTeng2013-41"><span class="cite-bracket">[</span>paper 35<span class="cite-bracket">]</span></a></sup> 2014<sup id="cite_ref-SpielmanTeng2014_42-0" class="reference"><a href="#cite_note-SpielmanTeng2014-42"><span class="cite-bracket">[</span>paper 36<span class="cite-bracket">]</span></a></sup> </p> </td></tr> <tr> <td>2016 </td> <td>Stephen Brookes and <a href="/wiki/Peter_O%27Hearn" title="Peter O'Hearn">Peter W. O'Hearn</a> </td> <td>for their invention of <a href="/wiki/Separation_logic#Concurrent_separation_logic" title="Separation logic">Concurrent Separation Logic</a> </td> <td>2007,<sup id="cite_ref-43" class="reference"><a href="#cite_note-43"><span class="cite-bracket">[</span>paper 37<span class="cite-bracket">]</span></a></sup> 2007<sup id="cite_ref-44" class="reference"><a href="#cite_note-44"><span class="cite-bracket">[</span>paper 38<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2017<sup id="cite_ref-Godël2017_2-1" class="reference"><a href="#cite_note-Godël2017-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/Cynthia_Dwork" title="Cynthia Dwork">Cynthia Dwork</a>, <a href="/wiki/Frank_McSherry" title="Frank McSherry">Frank McSherry</a>, <a href="/wiki/Kobbi_Nissim" title="Kobbi Nissim">Kobbi Nissim</a>, and <a href="/wiki/Adam_D._Smith" title="Adam D. Smith">Adam D. Smith</a> </td> <td>for the invention of <a href="/wiki/Differential_privacy" title="Differential privacy">differential privacy</a> </td> <td>2006<sup id="cite_ref-45" class="reference"><a href="#cite_note-45"><span class="cite-bracket">[</span>paper 39<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2018<sup id="cite_ref-Godël2018_46-0" class="reference"><a href="#cite_note-Godël2018-46"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/Oded_Regev_(Computer_Scientist)" class="mw-redirect" title="Oded Regev (Computer Scientist)">Oded Regev</a> </td> <td>for introducing the <a href="/wiki/Learning_with_errors" title="Learning with errors">learning with errors</a> problem </td> <td>2009<sup id="cite_ref-Regev2009_47-0" class="reference"><a href="#cite_note-Regev2009-47"><span class="cite-bracket">[</span>paper 40<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2019<sup id="cite_ref-Godël2019_48-0" class="reference"><a href="#cite_note-Godël2019-48"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/Irit_Dinur" title="Irit Dinur">Irit Dinur</a> </td> <td>for her new proof of the <a href="/wiki/PCP_theorem" title="PCP theorem">PCP theorem</a> by gap amplification </td> <td>2007<sup id="cite_ref-Dinur2007_49-0" class="reference"><a href="#cite_note-Dinur2007-49"><span class="cite-bracket">[</span>paper 41<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2020<sup id="cite_ref-Godël2020_50-0" class="reference"><a href="#cite_note-Godël2020-50"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </td> <td>Robin Moser and <a href="/wiki/G%C3%A1bor_Tardos" title="Gábor Tardos">Gábor Tardos</a> </td> <td>for their <a href="/wiki/Algorithmic_Lov%C3%A1sz_local_lemma" title="Algorithmic Lovász local lemma">constructive proof</a> of the <a href="/wiki/Lov%C3%A1sz_local_lemma" title="Lovász local lemma">Lovász local lemma</a> </td> <td>2010<sup id="cite_ref-MoserTardos2010_51-0" class="reference"><a href="#cite_note-MoserTardos2010-51"><span class="cite-bracket">[</span>paper 42<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2021<sup id="cite_ref-Godël2021_52-0" class="reference"><a href="#cite_note-Godël2021-52"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </td> <td>Andrei Bulatov, <a href="/wiki/Jin-Yi_Cai" title="Jin-Yi Cai">Jin-Yi Cai</a>, <a href="/wiki/Xi_Chen" title="Xi Chen">Xi Chen</a>, <a href="/wiki/Martin_Dyer" title="Martin Dyer">Martin Dyer</a>, and David Richerby </td> <td>for their work on the classification of the <a href="/wiki/Counting_problem_(complexity)" title="Counting problem (complexity)">counting complexity</a> of <a href="/wiki/Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problems</a> </td> <td>2013<sup id="cite_ref-Bulatov_2013_pp._1–41_53-0" class="reference"><a href="#cite_note-Bulatov_2013_pp._1–41-53"><span class="cite-bracket">[</span>paper 43<span class="cite-bracket">]</span></a></sup> 2013<sup id="cite_ref-Dyer_Richerby_2013_pp._1245–1274_54-0" class="reference"><a href="#cite_note-Dyer_Richerby_2013_pp._1245–1274-54"><span class="cite-bracket">[</span>paper 44<span class="cite-bracket">]</span></a></sup> 2017<sup id="cite_ref-Cai_Chen_pp._1–39_55-0" class="reference"><a href="#cite_note-Cai_Chen_pp._1–39-55"><span class="cite-bracket">[</span>paper 45<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2022<sup id="cite_ref-56" class="reference"><a href="#cite_note-56"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/Zvika_Brakerski" title="Zvika Brakerski">Zvika Brakerski</a>, <a href="/wiki/Craig_Gentry_(computer_scientist)" title="Craig Gentry (computer scientist)">Craig Gentry</a>, and <a href="/wiki/Vinod_Vaikuntanathan" title="Vinod Vaikuntanathan">Vinod Vaikuntanathan</a> </td> <td>for their transformative contributions to cryptography by constructing efficient fully <a href="/wiki/Homomorphic_encryption" title="Homomorphic encryption">homomorphic encryption</a> (FHE) schemes </td> <td>2014,<sup id="cite_ref-BV11_57-0" class="reference"><a href="#cite_note-BV11-57"><span class="cite-bracket">[</span>paper 46<span class="cite-bracket">]</span></a></sup> 2014<sup id="cite_ref-BGV12_58-0" class="reference"><a href="#cite_note-BGV12-58"><span class="cite-bracket">[</span>paper 47<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2023<sup id="cite_ref-59" class="reference"><a href="#cite_note-59"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/w/index.php?title=Samuel_Fiorini&action=edit&redlink=1" class="new" title="Samuel Fiorini (page does not exist)">Samuel Fiorini</a>, <a href="/wiki/Serge_Massar" title="Serge Massar">Serge Massar</a>, and <a href="/w/index.php?title=Sebastian_Pokutta&action=edit&redlink=1" class="new" title="Sebastian Pokutta (page does not exist)">Sebastian Pokutta</a>, <a href="/w/index.php?title=Hans_Raj_Tiwary&action=edit&redlink=1" class="new" title="Hans Raj Tiwary (page does not exist)">Hans Raj Tiwary</a>, <a href="/wiki/Ronald_de_Wolf" title="Ronald de Wolf">Ronald de Wolf</a>, and <a href="/w/index.php?title=Thomas_Rothvoss&action=edit&redlink=1" class="new" title="Thomas Rothvoss (page does not exist)">Thomas Rothvoss</a> </td> <td>for showing that any extended formulation for the <a href="/wiki/Travelling_salesman_problem" title="Travelling salesman problem">TSP</a> polytope has exponential size </td> <td>2015,<sup id="cite_ref-FMPTW15_60-0" class="reference"><a href="#cite_note-FMPTW15-60"><span class="cite-bracket">[</span>paper 48<span class="cite-bracket">]</span></a></sup> 2017<sup id="cite_ref-Rot17_61-0" class="reference"><a href="#cite_note-Rot17-61"><span class="cite-bracket">[</span>paper 49<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>2024<sup id="cite_ref-62" class="reference"><a href="#cite_note-62"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </td> <td><a href="/wiki/Ryan_Williams_(computer_scientist)" title="Ryan Williams (computer scientist)">Ryan Williams</a> </td> <td>for his work on <a href="/wiki/Circuit_lower_bounds" class="mw-redirect" title="Circuit lower bounds">circuit lower bounds</a> and the “algorithms to lower bounds” paradigm </td> <td>2011<sup id="cite_ref-63" class="reference"><a href="#cite_note-63"><span class="cite-bracket">[</span>paper 50<span class="cite-bracket">]</span></a></sup> </td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Winning_papers">Winning papers</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del_Prize&action=edit&section=2" title="Edit section: Winning papers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFBabaiMoran1988" class="citation cs2">Babai, László; Moran, Shlomo (1988), <a rel="nofollow" class="external text" href="http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf">"Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>, <b>36</b> (2): 254–276, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0022-0000%2888%2990028-1">10.1016/0022-0000(88)90028-1</a></span>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=Arthur-Merlin+games%3A+a+randomized+proof+system%2C+and+a+hierarchy+of+complexity+class&rft.volume=36&rft.issue=2&rft.pages=254-276&rft.date=1988&rft_id=info%3Adoi%2F10.1016%2F0022-0000%2888%2990028-1&rft.issn=0022-0000&rft.aulast=Babai&rft.aufirst=L%C3%A1szl%C3%B3&rft.au=Moran%2C+Shlomo&rft_id=http%3A%2F%2Fcrypto.cs.mcgill.ca%2F~crepeau%2FCOMP647%2F2007%2FTOPIC01%2FAMgames-Babai-Moran.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGoldwasserMicaliRackoff1989" class="citation cs2">Goldwasser, S.; Micali, S.; Rackoff, C. (1989), <a rel="nofollow" class="external text" href="http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf">"The knowledge complexity of interactive proof systems"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>, <b>18</b> (1): 186–208, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.397.4002">10.1.1.397.4002</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0218012">10.1137/0218012</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=The+knowledge+complexity+of+interactive+proof+systems&rft.volume=18&rft.issue=1&rft.pages=186-208&rft.date=1989&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.397.4002%23id-name%3DCiteSeerX&rft.issn=1095-7111&rft_id=info%3Adoi%2F10.1137%2F0218012&rft.aulast=Goldwasser&rft.aufirst=S.&rft.au=Micali%2C+S.&rft.au=Rackoff%2C+C.&rft_id=http%3A%2F%2Fcrypto.cs.mcgill.ca%2F~crepeau%2FCOMP647%2F2007%2FTOPIC02%2FGMR89.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHåstad1989" class="citation cs2">Håstad, Johan (1989), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120222163102/http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf">"Almost Optimal Lower Bounds for Small Depth Circuits"</a> <span class="cs1-format">(PDF)</span>, in Micali, Silvio (ed.), <i>Randomness and Computation</i>, Advances in Computing Research, vol. 5, JAI Press, pp. 6–20, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-89232-896-3" title="Special:BookSources/978-0-89232-896-3"><bdi>978-0-89232-896-3</bdi></a>, archived from <a rel="nofollow" class="external text" href="http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2012-02-22</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Almost+Optimal+Lower+Bounds+for+Small+Depth+Circuits&rft.btitle=Randomness+and+Computation&rft.series=Advances+in+Computing+Research&rft.pages=6-20&rft.pub=JAI+Press&rft.date=1989&rft.isbn=978-0-89232-896-3&rft.aulast=H%C3%A5stad&rft.aufirst=Johan&rft_id=http%3A%2F%2Freference.kfupm.edu.sa%2Fcontent%2Fa%2Fl%2Falmost_optimal_lower_bounds_for_small_de_134215.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFImmerman1988" class="citation cs2"><a href="/wiki/Neil_Immerman" title="Neil Immerman">Immerman, Neil</a> (1988), <a rel="nofollow" class="external text" href="http://www.cs.umass.edu/~immerman/pub/space.pdf">"Nondeterministic space is closed under complementation"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>, <b>17</b> (5): 935–938, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.5941">10.1.1.54.5941</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0217058">10.1137/0217058</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Nondeterministic+space+is+closed+under+complementation&rft.volume=17&rft.issue=5&rft.pages=935-938&rft.date=1988&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.54.5941%23id-name%3DCiteSeerX&rft.issn=1095-7111&rft_id=info%3Adoi%2F10.1137%2F0217058&rft.aulast=Immerman&rft.aufirst=Neil&rft_id=http%3A%2F%2Fwww.cs.umass.edu%2F~immerman%2Fpub%2Fspace.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSzelepcsényi1988" class="citation cs2">Szelepcsényi, R. (1988), <a rel="nofollow" class="external text" href="http://dml.cz/bitstream/handle/10338.dmlcz/120489/ActaOstrav_03-1995-1_10.pdf">"The method of forced enumeration for nondeterministic automata"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Acta_Informatica" title="Acta Informatica">Acta Informatica</a></i>, <b>26</b> (3): 279–284, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF00299636">10.1007/BF00299636</a>, <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10338.dmlcz%2F120489">10338.dmlcz/120489</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10838178">10838178</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Acta+Informatica&rft.atitle=The+method+of+forced+enumeration+for+nondeterministic+automata&rft.volume=26&rft.issue=3&rft.pages=279-284&rft.date=1988&rft_id=info%3Ahdl%2F10338.dmlcz%2F120489&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A10838178%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2FBF00299636&rft.aulast=Szelepcs%C3%A9nyi&rft.aufirst=R.&rft_id=http%3A%2F%2Fdml.cz%2Fbitstream%2Fhandle%2F10338.dmlcz%2F120489%2FActaOstrav_03-1995-1_10.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSinclairJerrum1989" class="citation cs2">Sinclair, A.; Jerrum, M. (1989), "Approximate counting, uniform generation and rapidly mixing Markov chains", <i><a href="/wiki/Information_and_Computation" title="Information and Computation">Information and Computation</a></i>, <b>82</b> (1): 93–133, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0890-5401%2889%2990067-9">10.1016/0890-5401(89)90067-9</a></span>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0890-5401">0890-5401</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+and+Computation&rft.atitle=Approximate+counting%2C+uniform+generation+and+rapidly+mixing+Markov+chains&rft.volume=82&rft.issue=1&rft.pages=93-133&rft.date=1989&rft_id=info%3Adoi%2F10.1016%2F0890-5401%2889%2990067-9&rft.issn=0890-5401&rft.aulast=Sinclair&rft.aufirst=A.&rft.au=Jerrum%2C+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJerrumSinclair1989" class="citation cs2">Jerrum, M.; Sinclair, Alistair (1989), "Approximating the permanent", <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>, <b>18</b> (6): 1149–1178, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.431.4190">10.1.1.431.4190</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0218077">10.1137/0218077</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Approximating+the+permanent&rft.volume=18&rft.issue=6&rft.pages=1149-1178&rft.date=1989&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.431.4190%23id-name%3DCiteSeerX&rft.issn=1095-7111&rft_id=info%3Adoi%2F10.1137%2F0218077&rft.aulast=Jerrum&rft.aufirst=M.&rft.au=Sinclair%2C+Alistair&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHalpernMoses1990" class="citation cs2"><a href="/wiki/Joseph_Halpern" title="Joseph Halpern">Halpern, Joseph</a>; <a href="/wiki/Yoram_Moses" title="Yoram Moses">Moses, Yoram</a> (1990), <a rel="nofollow" class="external text" href="https://www.cs.cornell.edu/home/halpern/papers/common_knowledge.pdf">"Knowledge and common knowledge in a distributed environment"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>37</b> (3): 549–587, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0006009">cs/0006009</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F79147.79161">10.1145/79147.79161</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:52151232">52151232</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Knowledge+and+common+knowledge+in+a+distributed+environment&rft.volume=37&rft.issue=3&rft.pages=549-587&rft.date=1990&rft_id=info%3Aarxiv%2Fcs%2F0006009&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A52151232%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F79147.79161&rft.aulast=Halpern&rft.aufirst=Joseph&rft.au=Moses%2C+Yoram&rft_id=https%3A%2F%2Fwww.cs.cornell.edu%2Fhome%2Fhalpern%2Fpapers%2Fcommon_knowledge.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFToda1991" class="citation cs2">Toda, Seinosuke (1991), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160303170125/http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf">"PP is as hard as the polynomial-time hierarchy"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>, <b>20</b> (5): 865–877, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.1246">10.1.1.121.1246</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0220053">10.1137/0220053</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a>, archived from <a rel="nofollow" class="external text" href="http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2016-03-03<span class="reference-accessdate">, retrieved <span class="nowrap">2010-06-08</span></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=PP+is+as+hard+as+the+polynomial-time+hierarchy&rft.volume=20&rft.issue=5&rft.pages=865-877&rft.date=1991&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.121.1246%23id-name%3DCiteSeerX&rft.issn=1095-7111&rft_id=info%3Adoi%2F10.1137%2F0220053&rft.aulast=Toda&rft.aufirst=Seinosuke&rft_id=http%3A%2F%2Ffaculty.cs.tamu.edu%2Fchen%2Fcourses%2F637%2F2008%2Fpres%2Fkorben.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFShor1997" class="citation cs2">Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>, <b>26</b> (5): 1484–1509, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9508027">quant-ph/9508027</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539795293172">10.1137/S0097539795293172</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2337707">2337707</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Polynomial-Time+Algorithms+for+Prime+Factorization+and+Discrete+Logarithms+on+a+Quantum+Computer&rft.volume=26&rft.issue=5&rft.pages=1484-1509&rft.date=1997&rft_id=info%3Aarxiv%2Fquant-ph%2F9508027&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A2337707%23id-name%3DS2CID&rft.issn=1095-7111&rft_id=info%3Adoi%2F10.1137%2FS0097539795293172&rft.aulast=Shor&rft.aufirst=Peter+W.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFVardiWolper1994" class="citation cs2">Vardi, Moshe Y.; Wolper, Pierre (1994), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110825210914/http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf">"Reasoning about infinite computations"</a> <span class="cs1-format">(PDF)</span>, <i>Information and Computation</i>, <b>115</b> (1): 1–37, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Finco.1994.1092">10.1006/inco.1994.1092</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0890-5401">0890-5401</a>, archived from <a rel="nofollow" class="external text" href="http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2011-08-25</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+and+Computation&rft.atitle=Reasoning+about+infinite+computations&rft.volume=115&rft.issue=1&rft.pages=1-37&rft.date=1994&rft_id=info%3Adoi%2F10.1006%2Finco.1994.1092&rft.issn=0890-5401&rft.aulast=Vardi&rft.aufirst=Moshe+Y.&rft.au=Wolper%2C+Pierre&rft_id=http%3A%2F%2Freference.kfupm.edu.sa%2Fcontent%2Fr%2Fe%2Freasoning_about_infinite_computations__102167.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFeigeGoldwasserLovászSafra1996" class="citation cs2">Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), <a rel="nofollow" class="external text" href="http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf">"Interactive proofs and the hardness of approximating cliques"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>43</b> (2): 268–292, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F226643.226652">10.1145/226643.226652</a></span>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Interactive+proofs+and+the+hardness+of+approximating+cliques&rft.volume=43&rft.issue=2&rft.pages=268-292&rft.date=1996&rft_id=info%3Adoi%2F10.1145%2F226643.226652&rft.issn=0004-5411&rft.aulast=Feige&rft.aufirst=Uriel&rft.au=Goldwasser%2C+Shafi&rft.au=Lov%C3%A1sz%2C+Laszlo&rft.au=Safra%2C+Shmuel&rft.au=Szegedy%2C+Mario&rft_id=http%3A%2F%2Fgroups.csail.mit.edu%2Fcis%2Fpubs%2Fshafi%2F1996-jacm.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAroraSafra1998" class="citation cs2">Arora, Sanjeev; Safra, Shmuel (1998), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110610101051/http://www.cs.umd.edu/~gasarch/pcp/AS.pdf">"Probabilistic checking of proofs: a new characterization of NP"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>45</b> (1): 70–122, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F273865.273901">10.1145/273865.273901</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:751563">751563</a>, archived from <a rel="nofollow" class="external text" href="http://www.cs.umd.edu/~gasarch/pcp/AS.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2011-06-10</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Probabilistic+checking+of+proofs%3A+a+new+characterization+of+NP&rft.volume=45&rft.issue=1&rft.pages=70-122&rft.date=1998&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A751563%23id-name%3DS2CID&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F273865.273901&rft.aulast=Arora&rft.aufirst=Sanjeev&rft.au=Safra%2C+Shmuel&rft_id=http%3A%2F%2Fwww.cs.umd.edu%2F~gasarch%2Fpcp%2FAS.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAroraLundMotwaniSudan1998" class="citation cs2">Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110610101241/https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf">"Proof verification and the hardness of approximation problems"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>45</b> (3): 501–555, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.4652">10.1.1.145.4652</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F278298.278306">10.1145/278298.278306</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8561542">8561542</a>, archived from <a rel="nofollow" class="external text" href="https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2011-06-10</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Proof+verification+and+the+hardness+of+approximation+problems&rft.volume=45&rft.issue=3&rft.pages=501-555&rft.date=1998&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.145.4652%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A8561542%23id-name%3DS2CID&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F278298.278306&rft.aulast=Arora&rft.aufirst=Sanjeev&rft.au=Lund%2C+Carsten&rft.au=Motwani%2C+Rajeev&rft.au=Sudan%2C+Madhu&rft.au=Szegedy%2C+Mario&rft_id=https%3A%2F%2Fwww.cs.umd.edu%2F~gasarch%2Fpcp%2FALMSS.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSénizergues2001" class="citation cs2">Sénizergues, Géraud (2001), "L(A) = L(B)? decidability results from complete formal systems", <i>Theor. Comput. Sci.</i>, <b>251</b> (1): 1–166, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-3975%2800%2900285-1">10.1016/S0304-3975(00)00285-1</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0304-3975">0304-3975</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theor.+Comput.+Sci.&rft.atitle=L%28A%29+%3D+L%28B%29%3F+decidability+results+from+complete+formal+systems&rft.volume=251&rft.issue=1&rft.pages=1-166&rft.date=2001&rft_id=info%3Adoi%2F10.1016%2FS0304-3975%2800%2900285-1&rft.issn=0304-3975&rft.aulast=S%C3%A9nizergues&rft.aufirst=G%C3%A9raud&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFreundSchapire1997" class="citation cs2">Freund, Y.; Schapire, R.E. (1997), <a rel="nofollow" class="external text" href="http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf">"A decision-theoretic generalization of on-line learning and an application to boosting"</a> <span class="cs1-format">(PDF)</span>, <i>Journal of Computer and System Sciences</i>, <b>55</b> (1): 119–139, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.1997.1504">10.1006/jcss.1997.1504</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1090-2724">1090-2724</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=A+decision-theoretic+generalization+of+on-line+learning+and+an+application+to+boosting&rft.volume=55&rft.issue=1&rft.pages=119-139&rft.date=1997&rft_id=info%3Adoi%2F10.1006%2Fjcss.1997.1504&rft.issn=1090-2724&rft.aulast=Freund&rft.aufirst=Y.&rft.au=Schapire%2C+R.E.&rft_id=http%3A%2F%2Fwww-ai.cs.tu-dortmund.de%2FLEHRE%2FPG%2FPG445%2Fliteratur%2Ffreund_schapire_97a.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHerlihyShavit1999" class="citation cs2"><a href="/wiki/Maurice_Herlihy" title="Maurice Herlihy">Herlihy, Maurice</a>; <a href="/wiki/Nir_Shavit" title="Nir Shavit">Shavit, Nir</a> (1999), <a rel="nofollow" class="external text" href="http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf">"The topological structure of asynchronous computability"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>46</b> (6): 858–923, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.78.1455">10.1.1.78.1455</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F331524.331529">10.1145/331524.331529</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5797174">5797174</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=The+topological+structure+of+asynchronous+computability&rft.volume=46&rft.issue=6&rft.pages=858-923&rft.date=1999&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.78.1455%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A5797174%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F331524.331529&rft.aulast=Herlihy&rft.aufirst=Maurice&rft.au=Shavit%2C+Nir&rft_id=http%3A%2F%2Fwww.cs.brown.edu%2F~mph%2FHerlihyS99%2Fp858-herlihy.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span>. <a rel="nofollow" class="external text" href="http://www.cs.brown.edu/~mph/finland.pdf">Gödel prize lecture</a></span> </li> <li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSaksZaharoglou2000" class="citation cs2"><a href="/wiki/Michael_Saks_(mathematician)" title="Michael Saks (mathematician)">Saks, Michael</a>; <a href="/wiki/Fotios_Zaharoglou" title="Fotios Zaharoglou">Zaharoglou, Fotios</a> (2000), "Wait-free <i>k</i>-set agreement is impossible: The topology of public knowledge", <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>, <b>29</b> (5): 1449–1483, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539796307698">10.1137/S0097539796307698</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Wait-free+k-set+agreement+is+impossible%3A+The+topology+of+public+knowledge&rft.volume=29&rft.issue=5&rft.pages=1449-1483&rft.date=2000&rft_id=info%3Adoi%2F10.1137%2FS0097539796307698&rft.aulast=Saks&rft.aufirst=Michael&rft.au=Zaharoglou%2C+Fotios&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlonMatiasSzegedy1999" class="citation cs2"><a href="/wiki/Noga_Alon" title="Noga Alon">Alon, Noga</a>; Matias, Yossi; Szegedy, Mario (1999), <a rel="nofollow" class="external text" href="http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf">"The space complexity of approximating the frequency moments"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>, <b>58</b> (1): 137–147, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.1997.1545">10.1006/jcss.1997.1545</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=The+space+complexity+of+approximating+the+frequency+moments&rft.volume=58&rft.issue=1&rft.pages=137-147&rft.date=1999&rft_id=info%3Adoi%2F10.1006%2Fjcss.1997.1545&rft.aulast=Alon&rft.aufirst=Noga&rft.au=Matias%2C+Yossi&rft.au=Szegedy%2C+Mario&rft_id=http%3A%2F%2Fwww.math.tau.ac.il%2F~noga%2FPDFS%2Famsz4.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span>. First presented at the <a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">Symposium on Theory of Computing</a> (STOC) in 1996.</span> </li> <li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAgrawalKayalSaxena2004" class="citation cs2">Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES is in P", <i><a href="/wiki/Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a></i>, <b>160</b> (2): 781–793, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.4007%2Fannals.2004.160.781">10.4007/annals.2004.160.781</a></span>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0003-486X">0003-486X</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics&rft.atitle=PRIMES+is+in+P&rft.volume=160&rft.issue=2&rft.pages=781-793&rft.date=2004&rft_id=info%3Adoi%2F10.4007%2Fannals.2004.160.781&rft.issn=0003-486X&rft.aulast=Agrawal&rft.aufirst=M.&rft.au=Kayal%2C+N.&rft.au=Saxena%2C+N.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRazborovRudich1997" class="citation cs2">Razborov, Alexander A.; Rudich, Steven (1997), "Natural proofs", <i><a href="/wiki/Journal_of_Computer_and_System_Sciences" title="Journal of Computer and System Sciences">Journal of Computer and System Sciences</a></i>, <b>55</b> (1): 24–35, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.1997.1494">10.1006/jcss.1997.1494</a></span>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a>, <a href="/wiki/Electronic_Colloquium_on_Computational_Complexity" title="Electronic Colloquium on Computational Complexity">ECCC</a> <a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/1994/010/">TR94-010</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=Natural+proofs&rft.volume=55&rft.issue=1&rft.pages=24-35&rft.date=1997&rft_id=info%3Adoi%2F10.1006%2Fjcss.1997.1494&rft.issn=0022-0000&rft.aulast=Razborov&rft.aufirst=Alexander+A.&rft.au=Rudich%2C+Steven&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSpielmanTeng2004" class="citation cs2">Spielman, Daniel A.; <a href="/wiki/Shanghua_Teng" class="mw-redirect" title="Shanghua Teng">Teng, Shang-Hua</a> (2004), "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time", <i>J. ACM</i>, <b>51</b> (3): 385–463, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/0212413">math/0212413</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F990308.990310">10.1145/990308.990310</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+ACM&rft.atitle=Smoothed+analysis+of+algorithms%3A+Why+the+simplex+algorithm+usually+takes+polynomial+time&rft.volume=51&rft.issue=3&rft.pages=385-463&rft.date=2004&rft_id=info%3Aarxiv%2Fmath%2F0212413&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F990308.990310&rft.aulast=Spielman&rft.aufirst=Daniel+A.&rft.au=Teng%2C+Shang-Hua&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFReingoldVadhanWigderson2002" class="citation cs2">Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "Entropy waves, the zig-zag graph product, and new constant-degree expanders", <i><a href="/wiki/Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a></i>, <b>155</b> (1): 157–187, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.236.8669">10.1.1.236.8669</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F3062153">10.2307/3062153</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0003-486X">0003-486X</a>, <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3062153">3062153</a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1888797">1888797</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:120739405">120739405</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Annals+of+Mathematics&rft.atitle=Entropy+waves%2C+the+zig-zag+graph+product%2C+and+new+constant-degree+expanders&rft.volume=155&rft.issue=1&rft.pages=157-187&rft.date=2002&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A120739405%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.2307%2F3062153&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.236.8669%23id-name%3DCiteSeerX&rft.issn=0003-486X&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F3062153%23id-name%3DJSTOR&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1888797%23id-name%3DMR&rft.aulast=Reingold&rft.aufirst=Omer&rft.au=Vadhan%2C+Salil&rft.au=Wigderson%2C+Avi&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFReingold2008" class="citation cs2">Reingold, Omer (2008), <a rel="nofollow" class="external text" href="http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps">"Undirected connectivity in log-space"</a>, <i>J. ACM</i>, <b>55</b> (4): 1–24, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1391289.1391291">10.1145/1391289.1391291</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207168478">207168478</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+ACM&rft.atitle=Undirected+connectivity+in+log-space&rft.volume=55&rft.issue=4&rft.pages=1-24&rft.date=2008&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A207168478%23id-name%3DS2CID&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F1391289.1391291&rft.aulast=Reingold&rft.aufirst=Omer&rft_id=http%3A%2F%2Fwww.weizmann.ac.il%2Fmathusers%2Freingold%2Fpublications%2Fsl.ps&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span><sup class="noprint Inline-Template"><span style="white-space: nowrap;">[<i><a href="/wiki/Wikipedia:Link_rot" title="Wikipedia:Link rot"><span title=" Dead link tagged December 2017">permanent dead link</span></a></i><span style="visibility:hidden; color:transparent; padding-left:2px">‍</span>]</span></sup></span> </li> <li id="cite_note-27"><span class="mw-cite-backlink"><b><a href="#cite_ref-27">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFArora1998" class="citation cs2"><a href="/wiki/Sanjeev_Arora" title="Sanjeev Arora">Arora, Sanjeev</a> (1998), "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>45</b> (5): 753–782, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.6765">10.1.1.23.6765</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F290179.290180">10.1145/290179.290180</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3023351">3023351</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Polynomial+time+approximation+schemes+for+Euclidean+traveling+salesman+and+other+geometric+problems&rft.volume=45&rft.issue=5&rft.pages=753-782&rft.date=1998&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.23.6765%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A3023351%23id-name%3DS2CID&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F290179.290180&rft.aulast=Arora&rft.aufirst=Sanjeev&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-28"><span class="mw-cite-backlink"><b><a href="#cite_ref-28">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMitchell1999" class="citation cs2"><a href="/wiki/Joseph_S._B._Mitchell" title="Joseph S. B. Mitchell">Mitchell, Joseph S. B.</a> (1999), "Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems", <i>SIAM Journal on Computing</i>, <b>28</b> (4): 1298–1309, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539796309764">10.1137/S0097539796309764</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1095-7111">1095-7111</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Guillotine+Subdivisions+Approximate+Polygonal+Subdivisions%3A+A+Simple+Polynomial-Time+Approximation+Scheme+for+Geometric+TSP%2C+k-MST%2C+and+Related+Problems&rft.volume=28&rft.issue=4&rft.pages=1298-1309&rft.date=1999&rft_id=info%3Adoi%2F10.1137%2FS0097539796309764&rft.issn=1095-7111&rft.aulast=Mitchell&rft.aufirst=Joseph+S.+B.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-29"><span class="mw-cite-backlink"><b><a href="#cite_ref-29">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHåstad2001" class="citation cs2"><a href="/wiki/Johan_H%C3%A5stad" title="Johan Håstad">Håstad, Johan</a> (2001), <a rel="nofollow" class="external text" href="http://www.csc.kth.se/~johanh/optimalinap.pdf">"Some optimal inapproximability results"</a> <span class="cs1-format">(PDF)</span>, <i><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></i>, <b>48</b> (4): 798–859, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.638.2808">10.1.1.638.2808</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F502090.502098">10.1145/502090.502098</a>, <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5120748">5120748</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Some+optimal+inapproximability+results&rft.volume=48&rft.issue=4&rft.pages=798-859&rft.date=2001&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.638.2808%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A5120748%23id-name%3DS2CID&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F502090.502098&rft.aulast=H%C3%A5stad&rft.aufirst=Johan&rft_id=http%3A%2F%2Fwww.csc.kth.se%2F~johanh%2Foptimalinap.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-31"><span class="mw-cite-backlink"><b><a href="#cite_ref-31">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKoutsoupiasPapadimitriou,_Christos2009" class="citation journal cs1">Koutsoupias, Elias; Papadimitriou, Christos (2009). "Worst-case equilibria". <i>Computer Science Review</i>. <b>3</b> (2): 65–69. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.cosrev.2009.04.003">10.1016/j.cosrev.2009.04.003</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computer+Science+Review&rft.atitle=Worst-case+equilibria&rft.volume=3&rft.issue=2&rft.pages=65-69&rft.date=2009&rft_id=info%3Adoi%2F10.1016%2Fj.cosrev.2009.04.003&rft.aulast=Koutsoupias&rft.aufirst=Elias&rft.au=Papadimitriou%2C+Christos&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-32"><span class="mw-cite-backlink"><b><a href="#cite_ref-32">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRoughgardenTardos,_Éva2002" class="citation journal cs1">Roughgarden, Tim; Tardos, Éva (2002). "How bad is selfish routing?". <i>Journal of the ACM</i>. <b>49</b> (2): 236–259. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1081">10.1.1.147.1081</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F506147.506153">10.1145/506147.506153</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207638789">207638789</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=How+bad+is+selfish+routing%3F&rft.volume=49&rft.issue=2&rft.pages=236-259&rft.date=2002&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.147.1081%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A207638789%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F506147.506153&rft.aulast=Roughgarden&rft.aufirst=Tim&rft.au=Tardos%2C+%C3%89va&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-33"><span class="mw-cite-backlink"><b><a href="#cite_ref-33">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFNisanRonen,_Amir2001" class="citation journal cs1">Nisan, Noam; Ronen, Amir (2001). "Algorithmic Mechanism Design". <i>Games and Economic Behavior</i>. <b>35</b> (1–2): 166–196. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.1731">10.1.1.21.1731</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fgame.1999.0790">10.1006/game.1999.0790</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Games+and+Economic+Behavior&rft.atitle=Algorithmic+Mechanism+Design&rft.volume=35&rft.issue=1%E2%80%932&rft.pages=166-196&rft.date=2001&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.21.1731%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1006%2Fgame.1999.0790&rft.aulast=Nisan&rft.aufirst=Noam&rft.au=Ronen%2C+Amir&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-35"><span class="mw-cite-backlink"><b><a href="#cite_ref-35">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBonehFranklin2003" class="citation journal cs1">Boneh, Dan; Franklin, Matthew (2003). "Identity-based encryption from the Weil pairing". <i>SIAM Journal on Computing</i>. <b>32</b> (3): 586–615. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.1131">10.1.1.66.1131</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539701398521">10.1137/S0097539701398521</a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2001745">2001745</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Identity-based+encryption+from+the+Weil+pairing&rft.volume=32&rft.issue=3&rft.pages=586-615&rft.date=2003&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.66.1131%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2001745%23id-name%3DMR&rft_id=info%3Adoi%2F10.1137%2FS0097539701398521&rft.aulast=Boneh&rft.aufirst=Dan&rft.au=Franklin%2C+Matthew&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-36"><span class="mw-cite-backlink"><b><a href="#cite_ref-36">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJoux2004" class="citation journal cs1">Joux, Antoine (2004). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00145-004-0312-y">"A one round protocol for tripartite Diffie-Hellman"</a>. <i>Journal of Cryptology</i>. <b>17</b> (4): 263–276. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00145-004-0312-y">10.1007/s00145-004-0312-y</a></span>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2090557">2090557</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3350730">3350730</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Cryptology&rft.atitle=A+one+round+protocol+for+tripartite+Diffie-Hellman&rft.volume=17&rft.issue=4&rft.pages=263-276&rft.date=2004&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D2090557%23id-name%3DMR&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A3350730%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2Fs00145-004-0312-y&rft.aulast=Joux&rft.aufirst=Antoine&rft_id=https%3A%2F%2Fdoi.org%2F10.1007%252Fs00145-004-0312-y&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-38"><span class="mw-cite-backlink"><b><a href="#cite_ref-38">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFaginLotemNaor2003" class="citation journal cs1">Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "Optimal aggregation algorithms for middleware". <i>Journal of Computer and System Sciences</i>. <b>66</b> (4): 614–656. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0204046">cs/0204046</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0022-0000%2803%2900026-6">10.1016/S0022-0000(03)00026-6</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Computer+and+System+Sciences&rft.atitle=Optimal+aggregation+algorithms+for+middleware&rft.volume=66&rft.issue=4&rft.pages=614-656&rft.date=2003&rft_id=info%3Aarxiv%2Fcs%2F0204046&rft_id=info%3Adoi%2F10.1016%2FS0022-0000%2803%2900026-6&rft.aulast=Fagin&rft.aufirst=Ronald&rft.au=Lotem%2C+Amnon&rft.au=Naor%2C+Moni&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-SpielmanTeng2011-40"><span class="mw-cite-backlink"><b><a href="#cite_ref-SpielmanTeng2011_40-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSpielmanTeng2011" class="citation journal cs1">Spielman, Daniel A.; Teng, Shang-Hua (2011). "Spectral Sparsification of Graphs". <i>SIAM Journal on Computing</i>. <b>40</b> (4): 981–1025. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0808.4134">0808.4134</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F08074489X">10.1137/08074489X</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9646279">9646279</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Spectral+Sparsification+of+Graphs&rft.volume=40&rft.issue=4&rft.pages=981-1025&rft.date=2011&rft_id=info%3Aarxiv%2F0808.4134&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A9646279%23id-name%3DS2CID&rft.issn=0097-5397&rft_id=info%3Adoi%2F10.1137%2F08074489X&rft.aulast=Spielman&rft.aufirst=Daniel+A.&rft.au=Teng%2C+Shang-Hua&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-SpielmanTeng2013-41"><span class="mw-cite-backlink"><b><a href="#cite_ref-SpielmanTeng2013_41-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSpielmanTeng2013" class="citation journal cs1">Spielman, Daniel A.; Teng, Shang-Hua (2013). "A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning". <i>SIAM Journal on Computing</i>. <b>42</b> (1): 1–26. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0809.3232">0809.3232</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F080744888">10.1137/080744888</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9151077">9151077</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=A+Local+Clustering+Algorithm+for+Massive+Graphs+and+Its+Application+to+Nearly+Linear+Time+Graph+Partitioning&rft.volume=42&rft.issue=1&rft.pages=1-26&rft.date=2013&rft_id=info%3Aarxiv%2F0809.3232&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A9151077%23id-name%3DS2CID&rft.issn=0097-5397&rft_id=info%3Adoi%2F10.1137%2F080744888&rft.aulast=Spielman&rft.aufirst=Daniel+A.&rft.au=Teng%2C+Shang-Hua&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-SpielmanTeng2014-42"><span class="mw-cite-backlink"><b><a href="#cite_ref-SpielmanTeng2014_42-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSpielmanTeng2014" class="citation journal cs1">Spielman, Daniel A.; Teng, Shang-Hua (2014). "Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems". <i>SIAM Journal on Matrix Analysis and Applications</i>. <b>35</b> (3): 835–885. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0607105">cs/0607105</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F090771430">10.1137/090771430</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0895-4798">0895-4798</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1750944">1750944</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Matrix+Analysis+and+Applications&rft.atitle=Nearly+Linear+Time+Algorithms+for+Preconditioning+and+Solving+Symmetric%2C+Diagonally+Dominant+Linear+Systems&rft.volume=35&rft.issue=3&rft.pages=835-885&rft.date=2014&rft_id=info%3Aarxiv%2Fcs%2F0607105&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1750944%23id-name%3DS2CID&rft.issn=0895-4798&rft_id=info%3Adoi%2F10.1137%2F090771430&rft.aulast=Spielman&rft.aufirst=Daniel+A.&rft.au=Teng%2C+Shang-Hua&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-43"><span class="mw-cite-backlink"><b><a href="#cite_ref-43">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrookes2007" class="citation journal cs1">Brookes, Stephen (2007). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~brookes/papers/seplogicrevisedfinal.pdf">"A Semantics for Concurrent Separation Logic"</a> <span class="cs1-format">(PDF)</span>. <i>Theoretical Computer Science</i>. <b>375</b> (1–3): 227–270. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2006.12.034">10.1016/j.tcs.2006.12.034</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=A+Semantics+for+Concurrent+Separation+Logic&rft.volume=375&rft.issue=1%E2%80%933&rft.pages=227-270&rft.date=2007&rft_id=info%3Adoi%2F10.1016%2Fj.tcs.2006.12.034&rft.aulast=Brookes&rft.aufirst=Stephen&rft_id=https%3A%2F%2Fwww.cs.cmu.edu%2F~brookes%2Fpapers%2Fseplogicrevisedfinal.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-44"><span class="mw-cite-backlink"><b><a href="#cite_ref-44">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFO'Hearn2007" class="citation journal cs1">O'Hearn, Peter (2007). <a rel="nofollow" class="external text" href="http://www.cs.ucl.ac.uk/staff/p.ohearn/papers/concurrency.pdf">"Resources, Concurrency and Local Reasoning"</a> <span class="cs1-format">(PDF)</span>. <i>Theoretical Computer Science</i>. <b>375</b> (1–3): 271–307. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2006.12.035">10.1016/j.tcs.2006.12.035</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theoretical+Computer+Science&rft.atitle=Resources%2C+Concurrency+and+Local+Reasoning&rft.volume=375&rft.issue=1%E2%80%933&rft.pages=271-307&rft.date=2007&rft_id=info%3Adoi%2F10.1016%2Fj.tcs.2006.12.035&rft.aulast=O%27Hearn&rft.aufirst=Peter&rft_id=http%3A%2F%2Fwww.cs.ucl.ac.uk%2Fstaff%2Fp.ohearn%2Fpapers%2Fconcurrency.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-45"><span class="mw-cite-backlink"><b><a href="#cite_ref-45">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDworkMcSherryNissimSmith2006" class="citation conference cs1">Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (eds.). <i>Calibrating Noise to Sensitivity in Private Data Analysis</i>. Theory of Cryptography (TCC). Lecture Notes in Computer Science. Vol. 3876. Springer-Verlag. pp. 265–284. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11681878_14">10.1007/11681878_14</a></span>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-540-32731-8" title="Special:BookSources/978-3-540-32731-8"><bdi>978-3-540-32731-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=Calibrating+Noise+to+Sensitivity+in+Private+Data+Analysis&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=265-284&rft.pub=Springer-Verlag&rft.date=2006&rft_id=info%3Adoi%2F10.1007%2F11681878_14&rft.isbn=978-3-540-32731-8&rft.aulast=Dwork&rft.aufirst=Cynthia&rft.au=McSherry%2C+Frank&rft.au=Nissim%2C+Kobbi&rft.au=Smith%2C+Adam&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Regev2009-47"><span class="mw-cite-backlink"><b><a href="#cite_ref-Regev2009_47-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRegev2009" class="citation journal cs1">Regev, Oded (2009). "On lattices, learning with errors, random linear codes, and cryptography". <i>Journal of the ACM</i>. <b>56</b> (6): 1–40. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.215.3543">10.1.1.215.3543</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1568318.1568324">10.1145/1568318.1568324</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207156623">207156623</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=On+lattices%2C+learning+with+errors%2C+random+linear+codes%2C+and+cryptography&rft.volume=56&rft.issue=6&rft.pages=1-40&rft.date=2009&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.215.3543%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A207156623%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F1568318.1568324&rft.aulast=Regev&rft.aufirst=Oded&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Dinur2007-49"><span class="mw-cite-backlink"><b><a href="#cite_ref-Dinur2007_49-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDinur2007" class="citation journal cs1">Dinur, Irit (2007). <a rel="nofollow" class="external text" href="https://dl.acm.org/citation.cfm?id=1236459">"The PCP theorem by gap amplification"</a>. <i>Journal of the ACM</i>. <b>54</b> (3): 12–es. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1236457.1236459">10.1145/1236457.1236459</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:53244523">53244523</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=The+PCP+theorem+by+gap+amplification&rft.volume=54&rft.issue=3&rft.pages=12-es&rft.date=2007&rft_id=info%3Adoi%2F10.1145%2F1236457.1236459&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A53244523%23id-name%3DS2CID&rft.aulast=Dinur&rft.aufirst=Irit&rft_id=https%3A%2F%2Fdl.acm.org%2Fcitation.cfm%3Fid%3D1236459&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-MoserTardos2010-51"><span class="mw-cite-backlink"><b><a href="#cite_ref-MoserTardos2010_51-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation journal cs1">"A constructive proof of the general Lovász Local Lemma". <i>Journal of the ACM</i>. <b>57</b> (2). 2010. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1667053">10.1145/1667053</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=A+constructive+proof+of+the+general+Lov%C3%A1sz+Local+Lemma&rft.volume=57&rft.issue=2&rft.date=2010&rft_id=info%3Adoi%2F10.1145%2F1667053&rft.issn=0004-5411&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Bulatov_2013_pp._1–41-53"><span class="mw-cite-backlink"><b><a href="#cite_ref-Bulatov_2013_pp._1–41_53-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBulatov2013" class="citation journal cs1">Bulatov, Andrei A. (2013). "The complexity of the counting constraint satisfaction problem". <i>Journal of the ACM</i>. <b>60</b> (5). Association for Computing Machinery: 1–41. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2528400">10.1145/2528400</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8964233">8964233</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=The+complexity+of+the+counting+constraint+satisfaction+problem&rft.volume=60&rft.issue=5&rft.pages=1-41&rft.date=2013&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A8964233%23id-name%3DS2CID&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F2528400&rft.aulast=Bulatov&rft.aufirst=Andrei+A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Dyer_Richerby_2013_pp._1245–1274-54"><span class="mw-cite-backlink"><b><a href="#cite_ref-Dyer_Richerby_2013_pp._1245–1274_54-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDyerRicherby2013" class="citation journal cs1">Dyer, Martin; Richerby, David (2013). "An Effective Dichotomy for the Counting Constraint Satisfaction Problem". <i>SIAM Journal on Computing</i>. <b>42</b> (3). Society for Industrial & Applied Mathematics (SIAM): 1245–1274. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1003.3879">1003.3879</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F100811258">10.1137/100811258</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1247279">1247279</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=An+Effective+Dichotomy+for+the+Counting+Constraint+Satisfaction+Problem&rft.volume=42&rft.issue=3&rft.pages=1245-1274&rft.date=2013&rft_id=info%3Aarxiv%2F1003.3879&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1247279%23id-name%3DS2CID&rft.issn=0097-5397&rft_id=info%3Adoi%2F10.1137%2F100811258&rft.aulast=Dyer&rft.aufirst=Martin&rft.au=Richerby%2C+David&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Cai_Chen_pp._1–39-55"><span class="mw-cite-backlink"><b><a href="#cite_ref-Cai_Chen_pp._1–39_55-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCaiChen2017" class="citation journal cs1">Cai, Jin-Yi; Chen, Xi (2017-06-22). "Complexity of Counting CSP with Complex Weights". <i>Journal of the ACM</i>. <b>64</b> (3). Association for Computing Machinery: 1–39. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1111.2384">1111.2384</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2822891">10.1145/2822891</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0004-5411">0004-5411</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1053684">1053684</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Complexity+of+Counting+CSP+with+Complex+Weights&rft.volume=64&rft.issue=3&rft.pages=1-39&rft.date=2017-06-22&rft_id=info%3Aarxiv%2F1111.2384&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1053684%23id-name%3DS2CID&rft.issn=0004-5411&rft_id=info%3Adoi%2F10.1145%2F2822891&rft.aulast=Cai&rft.aufirst=Jin-Yi&rft.au=Chen%2C+Xi&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-BV11-57"><span class="mw-cite-backlink"><b><a href="#cite_ref-BV11_57-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrakerskiVaikuntanathan2014" class="citation journal cs1">Brakerski, Zvika; Vaikuntanathan, Vinod (January 2014). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1137/120868669">"Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$"</a>. <i>SIAM Journal on Computing</i>. <b>43</b> (2): 831–871. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F120868669">10.1137/120868669</a>. <a href="/wiki/Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/1721.1%2F115488">1721.1/115488</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8831240">8831240</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Efficient+Fully+Homomorphic+Encryption+from+%28Standard%29+%24%5Cmathsf%7BLWE%7D%24&rft.volume=43&rft.issue=2&rft.pages=831-871&rft.date=2014-01&rft_id=info%3Ahdl%2F1721.1%2F115488&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A8831240%23id-name%3DS2CID&rft.issn=0097-5397&rft_id=info%3Adoi%2F10.1137%2F120868669&rft.aulast=Brakerski&rft.aufirst=Zvika&rft.au=Vaikuntanathan%2C+Vinod&rft_id=http%3A%2F%2Fdx.doi.org%2F10.1137%2F120868669&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-BGV12-58"><span class="mw-cite-backlink"><b><a href="#cite_ref-BGV12_58-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrakerskiGentryVaikuntanathan2012" class="citation book cs1">Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1145/2090236.2090262">"(Leveled) fully homomorphic encryption without bootstrapping"</a>. <i>Proceedings of the 3rd Innovations in Theoretical Computer Science Conference</i>. New York, New York, USA: ACM Press. pp. 309–325. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2090236.2090262">10.1145/2090236.2090262</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9781450311151" title="Special:BookSources/9781450311151"><bdi>9781450311151</bdi></a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2602543">2602543</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=%28Leveled%29+fully+homomorphic+encryption+without+bootstrapping&rft.btitle=Proceedings+of+the+3rd+Innovations+in+Theoretical+Computer+Science+Conference&rft.place=New+York%2C+New+York%2C+USA&rft.pages=309-325&rft.pub=ACM+Press&rft.date=2012&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A2602543%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F2090236.2090262&rft.isbn=9781450311151&rft.aulast=Brakerski&rft.aufirst=Zvika&rft.au=Gentry%2C+Craig&rft.au=Vaikuntanathan%2C+Vinod&rft_id=http%3A%2F%2Fdx.doi.org%2F10.1145%2F2090236.2090262&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-FMPTW15-60"><span class="mw-cite-backlink"><b><a href="#cite_ref-FMPTW15_60-0">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFioriniMassarPokuttaTiwary2015" class="citation journal cs1">Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald (2015). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/2716307">"Exponential Lower Bounds for Polytopes in Combinatorial Optimization"</a>. <i>Journal of the ACM</i>. <b>62</b> (2): 17:1–17:23. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1111.0837">1111.0837</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2716307">10.1145/2716307</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7372000">7372000</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=Exponential+Lower+Bounds+for+Polytopes+in+Combinatorial+Optimization&rft.volume=62&rft.issue=2&rft.pages=17%3A1-17%3A23&rft.date=2015&rft_id=info%3Aarxiv%2F1111.0837&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A7372000%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F2716307&rft.aulast=Fiorini&rft.aufirst=Samuel&rft.au=Massar%2C+Serge&rft.au=Pokutta%2C+Sebastian&rft.au=Tiwary%2C+Hans+Raj&rft.au=de+Wolf%2C+Ronald&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F2716307&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Rot17-61"><span class="mw-cite-backlink"><b><a href="#cite_ref-Rot17_61-0">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRothvoss2017" class="citation journal cs1">Rothvoss, Thomas (2017). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/3127497">"The Matching Polytope has Exponential Extension Complexity"</a>. <i>Journal of the ACM</i>. <b>64</b> (6): 41:1–41:19. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1311.2369">1311.2369</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3127497">10.1145/3127497</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:47045361">47045361</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+ACM&rft.atitle=The+Matching+Polytope+has+Exponential+Extension+Complexity&rft.volume=64&rft.issue=6&rft.pages=41%3A1-41%3A19&rft.date=2017&rft_id=info%3Aarxiv%2F1311.2369&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A47045361%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1145%2F3127497&rft.aulast=Rothvoss&rft.aufirst=Thomas&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%2F3127497&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-63"><span class="mw-cite-backlink"><b><a href="#cite_ref-63">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWilliams2011" class="citation book cs1">Williams, Ryan (June 2011). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1109/ccc.2011.36">"Non-uniform ACC Circuit Lower Bounds"</a>. <i>2011 IEEE 26th Annual Conference on Computational Complexity</i>. IEEE. pp. 115–125. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fccc.2011.36">10.1109/ccc.2011.36</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4577-0179-5" title="Special:BookSources/978-1-4577-0179-5"><bdi>978-1-4577-0179-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Non-uniform+ACC+Circuit+Lower+Bounds&rft.btitle=2011+IEEE+26th+Annual+Conference+on+Computational+Complexity&rft.pages=115-125&rft.pub=IEEE&rft.date=2011-06&rft_id=info%3Adoi%2F10.1109%2Fccc.2011.36&rft.isbn=978-1-4577-0179-5&rft.aulast=Williams&rft.aufirst=Ryan&rft_id=http%3A%2F%2Fdx.doi.org%2F10.1109%2Fccc.2011.36&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del_Prize&action=edit&section=3" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/List_of_computer_science_awards" title="List of computer science awards">List of computer science awards</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del_Prize&action=edit&section=4" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://rjlipton.wordpress.com/the-gdel-letter/">"The Gödel Letter"</a>. 2009-02-12.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=The+G%C3%B6del+Letter&rft.date=2009-02-12&rft_id=https%3A%2F%2Frjlipton.wordpress.com%2Fthe-gdel-letter%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Godël2017-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-Godël2017_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Godël2017_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize">"2017 Gödel Prize"</a>. <i>European Association for Theoretical Computer Science</i>. EATCS<span class="reference-accessdate">. Retrieved <span class="nowrap">29 March</span> 2017</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=European+Association+for+Theoretical+Computer+Science&rft.atitle=2017+G%C3%B6del+Prize&rft_id=https%3A%2F%2Fwww.eatcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2450-2017-godel-prize&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-sigact-2012-30"><span class="mw-cite-backlink"><b><a href="#cite_ref-sigact-2012_30-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation news cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012">"Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory"</a>. 16 May 2012. Archived from <a rel="nofollow" class="external text" href="http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012">the original</a> on 18 July 2013<span class="reference-accessdate">. Retrieved <span class="nowrap">16 May</span> 2012</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.atitle=Three+Papers+Cited+for+Laying+Foundation+of+Growth+in+Algorithmic+Game+Theory&rft.date=2012-05-16&rft_id=http%3A%2F%2Fwww.acm.org%2Fpress-room%2Fnews-releases%2F2012%2Fgoedel-prize-2012&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-34"><span class="mw-cite-backlink"><b><a href="#cite_ref-34">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.acm.org/press-room/news-releases/2013/goedel-prize-13/">ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20130601191333/http://www.acm.org/press-room/news-releases/2013/goedel-prize-13">Archived</a> 2013-06-01 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, <a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a>, May 29, 2013.</span> </li> <li id="cite_note-37"><span class="mw-cite-backlink"><b><a href="#cite_ref-37">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://eatcs.org/index.php/component/content/article/1-news/1908-goedel-prize-2014">Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources</a>, <a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a>, April 30, 2014.</span> </li> <li id="cite_note-39"><span class="mw-cite-backlink"><b><a href="#cite_ref-39">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.sigact.org/Prizes/Godel/citation2015.pdf">2015 Gödel Prize announcement</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20171209021752/http://www.sigact.org/Prizes/Godel/citation2015.pdf">Archived</a> 2017-12-09 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a> by <a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a>.</span> </li> <li id="cite_note-Godël2018-46"><span class="mw-cite-backlink"><b><a href="#cite_ref-Godël2018_46-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize">"2018 Gödel Prize citation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=2018+G%C3%B6del+Prize+citation&rft_id=http%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2670-2018-godel-prize&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Godël2019-48"><span class="mw-cite-backlink"><b><a href="#cite_ref-Godël2019_48-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09">"2019 Gödel Prize citation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=2019+G%C3%B6del+Prize+citation&rft_id=http%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2807-2019-03-12-20-31-09&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Godël2020-50"><span class="mw-cite-backlink"><b><a href="#cite_ref-Godël2020_50-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://eatcs.org/index.php/component/content/article/1-news/2850-2020-03-31-12-11-16">"2020 Gödel Prize citation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=2020+G%C3%B6del+Prize+citation&rft_id=http%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2850-2020-03-31-12-11-16&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-Godël2021-52"><span class="mw-cite-backlink"><b><a href="#cite_ref-Godël2021_52-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://eatcs.org/index.php/component/content/article/1-news/2885-2021-05-07-21-20-13">"2021 Gödel Prize citation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=2021+G%C3%B6del+Prize+citation&rft_id=https%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2885-2021-05-07-21-20-13&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-56"><span class="mw-cite-backlink"><b><a href="#cite_ref-56">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://eatcs.org/index.php/component/content/article/1-news/2917-2022-05-21-20-13-45">"2022 Gödel Prize citation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=2022+G%C3%B6del+Prize+citation&rft_id=https%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2917-2022-05-21-20-13-45&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-59"><span class="mw-cite-backlink"><b><a href="#cite_ref-59">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://eatcs.org/index.php/component/content/article/1-news/2945-2023-05-18-18-41-48">"2023 Gödel Prize citation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=2023+G%C3%B6del+Prize+citation&rft_id=https%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2945-2023-05-18-18-41-48&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> <li id="cite_note-62"><span class="mw-cite-backlink"><b><a href="#cite_ref-62">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://eatcs.org/index.php/component/content/article/1-news/2982-2024-05-13-10-59-08">"2024 Gödel Prize citation"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=2024+G%C3%B6del+Prize+citation&rft_id=https%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F2982-2024-05-13-10-59-08&rfr_id=info%3Asid%2Fen.wikipedia.org%3AG%C3%B6del+Prize" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=G%C3%B6del_Prize&action=edit&section=5" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://www.sigact.org/prizes/g%C3%B6del.html">Prize website with list of winners</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Gödel_Prize_laureates" style="padding:3px"><table class="nowraplinks hlist mw-collapsible expanded navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:G%C3%B6del_Prize_laureates" title="Template:Gödel Prize laureates"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:G%C3%B6del_Prize_laureates" title="Template talk:Gödel Prize laureates"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:G%C3%B6del_Prize_laureates" title="Special:EditPage/Template:Gödel Prize laureates"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Gödel_Prize_laureates" style="font-size:114%;margin:0 4em"><a class="mw-selflink selflink">Gödel Prize</a> laureates</div></th></tr><tr><td colspan="2" class="navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/L%C3%A1szl%C3%B3_Babai" title="László Babai">Babai</a> / <a href="/wiki/Shafi_Goldwasser" title="Shafi Goldwasser">Goldwasser</a> / <a href="/wiki/Silvio_Micali" title="Silvio Micali">Micali</a> / <a href="/wiki/Shlomo_Moran" title="Shlomo Moran">Moran</a> / <a href="/wiki/Charles_Rackoff" title="Charles Rackoff">Rackoff</a> (1993)</li> <li><a href="/wiki/Johan_H%C3%A5stad" title="Johan Håstad">Håstad</a> (1994)</li> <li><a href="/wiki/Neil_Immerman" title="Neil Immerman">Immerman</a> / <a href="/wiki/R%C3%B3bert_Szelepcs%C3%A9nyi" title="Róbert Szelepcsényi">Szelepcsényi</a> (1995)</li> <li><a href="/wiki/Mark_Jerrum" title="Mark Jerrum">Jerrum</a> / <a href="/wiki/Alistair_Sinclair" title="Alistair Sinclair">Sinclair</a> (1996)</li> <li><a href="/wiki/Joseph_Halpern" title="Joseph Halpern">Halpern</a> / <a href="/wiki/Yoram_Moses" title="Yoram Moses">Moses</a> (1997)</li> <li><a href="/wiki/Seinosuke_Toda" title="Seinosuke Toda">Toda</a> (1998)</li> <li><a href="/wiki/Peter_Shor" title="Peter Shor">Shor</a> (1999)</li> <li><a href="/wiki/Moshe_Y._Vardi" class="mw-redirect" title="Moshe Y. Vardi">Vardi</a> / <a href="/wiki/Pierre_Wolper" title="Pierre Wolper">Wolper</a> (2000)</li> <li><a href="/wiki/Sanjeev_Arora" title="Sanjeev Arora">Arora</a> / <a href="/wiki/Uriel_Feige" title="Uriel Feige">Feige</a> / <a href="/wiki/Shafi_Goldwasser" title="Shafi Goldwasser">Goldwasser</a> / <a href="/wiki/Carsten_Lund" title="Carsten Lund">Lund</a> / <a href="/wiki/L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">Lovász</a> / <a href="/wiki/Rajeev_Motwani" title="Rajeev Motwani">Motwani</a> / <a href="/wiki/Shmuel_Safra" title="Shmuel Safra">Safra</a> / <a href="/wiki/Madhu_Sudan" title="Madhu Sudan">Sudan</a> / <a href="/wiki/Mario_Szegedy" title="Mario Szegedy">Szegedy</a> (2001)</li> <li><a href="/wiki/G%C3%A9raud_S%C3%A9nizergues" title="Géraud Sénizergues">Sénizergues</a> (2002)</li> <li><a href="/wiki/Yoav_Freund" title="Yoav Freund">Freund</a> / <a href="/wiki/Robert_Schapire" title="Robert Schapire">Schapire</a> (2003)</li> <li><a href="/wiki/Maurice_Herlihy" title="Maurice Herlihy">Herlihy</a> / <a href="/wiki/Michael_Saks_(mathematician)" title="Michael Saks (mathematician)">Saks</a> / <a href="/wiki/Nir_Shavit" title="Nir Shavit">Shavit</a> / <a href="/wiki/Fotios_Zaharoglou" title="Fotios Zaharoglou">Zaharoglou</a> (2004)</li> <li><a href="/wiki/Noga_Alon" title="Noga Alon">Alon</a> / <a href="/wiki/Yossi_Matias" title="Yossi Matias">Matias</a> / <a href="/wiki/Mario_Szegedy" title="Mario Szegedy">Szegedy</a> (2005)</li> <li><a href="/wiki/Manindra_Agrawal" title="Manindra Agrawal">Agrawal</a> / <a href="/wiki/Neeraj_Kayal" title="Neeraj Kayal">Kayal</a> / <a href="/wiki/Nitin_Saxena" title="Nitin Saxena">Saxena</a> (2006)</li> <li><a href="/wiki/Alexander_Razborov" title="Alexander Razborov">Razborov</a> / <a href="/wiki/Steven_Rudich" title="Steven Rudich">Rudich</a> (2007)</li> <li><a href="/wiki/Shang-Hua_Teng" title="Shang-Hua Teng">Teng</a> / <a href="/wiki/Daniel_Spielman" title="Daniel Spielman">Spielman</a> (2008)</li> <li><a href="/wiki/Omer_Reingold" title="Omer Reingold">Reingold</a> / <a href="/wiki/Salil_Vadhan" title="Salil Vadhan">Vadhan</a> / <a href="/wiki/Avi_Wigderson" title="Avi Wigderson">Wigderson</a> (2009)</li> <li><a href="/wiki/Sanjeev_Arora" title="Sanjeev Arora">Arora</a> / <a href="/wiki/Joseph_S._B._Mitchell" title="Joseph S. B. Mitchell">Mitchell</a> (2010)</li> <li><a href="/wiki/Johan_H%C3%A5stad" title="Johan Håstad">Håstad</a> (2011)</li> <li><a href="/wiki/Elias_Koutsoupias" title="Elias Koutsoupias">Koutsoupias</a> / <a href="/wiki/Christos_Papadimitriou" title="Christos Papadimitriou">Papadimitriou</a> / <a href="/wiki/Tim_Roughgarden" title="Tim Roughgarden">Roughgarden</a> / <a href="/wiki/%C3%89va_Tardos" title="Éva Tardos">É. Tardos</a> / <a href="/wiki/Noam_Nisan" title="Noam Nisan">Nisan</a> / <a href="/wiki/Amir_Ronen" title="Amir Ronen">Ronen</a> (2012)</li> <li><a href="/wiki/Dan_Boneh" title="Dan Boneh">Boneh</a> / <a href="/wiki/Matthew_K._Franklin" title="Matthew K. Franklin">Franklin</a> / <a href="/wiki/Antoine_Joux" title="Antoine Joux">Joux</a> (2013)</li> <li><a href="/wiki/Ronald_Fagin" title="Ronald Fagin">Fagin</a> / <a href="/w/index.php?title=Amnon_Lotem&action=edit&redlink=1" class="new" title="Amnon Lotem (page does not exist)">Lotem</a> / <a href="/wiki/Moni_Naor" title="Moni Naor">Naor</a> (2014)</li> <li><a href="/wiki/Daniel_Spielman" title="Daniel Spielman">Spielman</a> / <a href="/wiki/Shang-Hua_Teng" title="Shang-Hua Teng">Teng</a> (2015)</li> <li><a href="/w/index.php?title=Stephen_Brookes_(computer_scientist)&action=edit&redlink=1" class="new" title="Stephen Brookes (computer scientist) (page does not exist)">Brookes</a> / <a href="/wiki/Peter_O%27Hearn" title="Peter O'Hearn">O'Hearn</a> (2016)</li> <li><a href="/wiki/Cynthia_Dwork" title="Cynthia Dwork">Dwork</a> / <a href="/wiki/Frank_McSherry" title="Frank McSherry">McSherry</a> / <a href="/wiki/Kobbi_Nissim" title="Kobbi Nissim">Nissim</a> / <a href="/wiki/Adam_D._Smith" title="Adam D. Smith">Smith</a> (2017)</li> <li><a href="/wiki/Oded_Regev_(Computer_Scientist)" class="mw-redirect" title="Oded Regev (Computer Scientist)">Regev</a> (2018)</li> <li><a href="/wiki/Irit_Dinur" title="Irit Dinur">Dinur</a> (2019)</li> <li><a href="/w/index.php?title=Robin_Moser&action=edit&redlink=1" class="new" title="Robin Moser (page does not exist)">Moser</a> / <a href="/wiki/G%C3%A1bor_Tardos" title="Gábor Tardos">G. Tardos</a> (2020)</li> <li><a href="/w/index.php?title=Andrei_A._Bulatov&action=edit&redlink=1" class="new" title="Andrei A. Bulatov (page does not exist)">Bulatov</a> / <a href="/wiki/Jin-Yi_Cai" title="Jin-Yi Cai">Cai</a> / <a href="/wiki/Xi_Chen" title="Xi Chen">Chen</a> / <a href="/wiki/Martin_Dyer" title="Martin Dyer">Dyer</a> / <a href="/w/index.php?title=David_Richerby&action=edit&redlink=1" class="new" title="David Richerby (page does not exist)">Richerby</a> (2021)</li> <li><a href="/wiki/Zvika_Brakerski" title="Zvika Brakerski">Brakerski</a> / <a href="/wiki/Craig_Gentry_(computer_scientist)" title="Craig Gentry (computer scientist)">Gentry</a> / <a href="/wiki/Vinod_Vaikuntanathan" title="Vinod Vaikuntanathan">Vaikuntanathan</a> (2022)</li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Association_for_Computing_Machinery" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Association_for_Computing_Machinery" title="Template:Association for Computing Machinery"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Association_for_Computing_Machinery" title="Template talk:Association for Computing Machinery"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Association_for_Computing_Machinery" title="Special:EditPage/Template:Association for Computing Machinery"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Association_for_Computing_Machinery" style="font-size:114%;margin:0 4em"><a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Association_for_Computing_Machinery#Special_Interest_Groups" title="Association for Computing Machinery">Special Interest Groups</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/SIGACCESS" title="SIGACCESS">SIGACCESS</a></li> <li><a href="/wiki/ACM_SIGACT" title="ACM SIGACT">SIGACT</a></li> <li>SIGAda</li> <li><a href="/wiki/SIGAI" title="SIGAI">SIGAI</a></li> <li>SIGAPP</li> <li><a href="/wiki/ACM_SIGARCH" title="ACM SIGARCH">SIGARCH</a></li> <li>SIGBED</li> <li>SIGBio</li> <li>SIGCAS</li> <li><a href="/wiki/SIGCHI" title="SIGCHI">SIGCHI</a></li> <li><a href="/wiki/SIGCOMM" title="SIGCOMM">SIGCOMM</a></li> <li><a href="/wiki/SIGCSE" title="SIGCSE">SIGCSE</a></li> <li><a href="/wiki/Special_Interest_Group_on_Design_Automation" title="Special Interest Group on Design Automation">SIGDA</a></li> <li><a href="/wiki/SIGDOC" title="SIGDOC">SIGDOC</a></li> <li>SIGecom</li> <li>SIGEVO</li> <li><a href="/wiki/ACM_SIGGRAPH" title="ACM SIGGRAPH">SIGGRAPH</a></li> <li><a href="/wiki/ACM_SIGHPC" title="ACM SIGHPC">SIGHPC</a></li> <li><a href="/wiki/Special_Interest_Group_on_Information_Retrieval" title="Special Interest Group on Information Retrieval">SIGIR</a></li> <li>SIGITE</li> <li><a href="/wiki/SIGKDD" class="mw-redirect" title="SIGKDD">SIGKDD</a></li> <li><a href="/wiki/ACM_SIGLOG" title="ACM SIGLOG">SIGLOG</a></li> <li><a href="/wiki/SIGMETRICS" title="SIGMETRICS">SIGMETRICS</a></li> <li>SIGMICRO</li> <li>SIGMIS</li> <li><a href="/wiki/SIGMM" class="mw-redirect" title="SIGMM">SIGMM</a></li> <li><a href="/wiki/SIGMOBILE" title="SIGMOBILE">SIGMOBILE</a></li> <li><a href="/wiki/SIGMOD" title="SIGMOD">SIGMOD</a></li> <li><a href="/wiki/ACM_SIGOPS" title="ACM SIGOPS">SIGOPS</a></li> <li><a href="/wiki/SIGPLAN" title="SIGPLAN">SIGPLAN</a></li> <li>SIGSAC</li> <li><a href="/wiki/SIGSAM" title="SIGSAM">SIGSAM</a></li> <li><a href="/wiki/SIGSIM" class="mw-redirect" title="SIGSIM">SIGSIM</a></li> <li><a href="/wiki/SIGSOFT" title="SIGSOFT">SIGSOFT</a></li> <li>SIGSPATIAL</li> <li><a href="/wiki/SIGUCCS" title="SIGUCCS">SIGUCCS</a></li> <li><a href="/wiki/ACM_SIGWEB" title="ACM SIGWEB">SIGWEB</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Association_for_Computing_Machinery#Awards" title="Association for Computing Machinery">Awards</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">ACM</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Turing_Award" title="Turing Award">Turing Award</a></li> <li><a href="/wiki/ACM_Fellow" title="ACM Fellow">ACM Fellowship</a></li> <li><a href="/wiki/ACM-AAAI_Allen_Newell_Award" class="mw-redirect" title="ACM-AAAI Allen Newell Award">ACM-AAAI Allen Newell Award</a></li> <li><a href="/wiki/Association_for_Computing_Machinery#Athena_Lectures" title="Association for Computing Machinery">Athena Lecturer Award</a></li> <li><a href="/wiki/Eckert%E2%80%93Mauchly_Award" title="Eckert–Mauchly Award">Eckert–Mauchly Award</a></li> <li><a href="/wiki/ACM_Eugene_L._Lawler_Award" title="ACM Eugene L. Lawler Award">Eugene L. Lawler Award</a></li> <li><a href="/wiki/ACM_Doctoral_Dissertation_Award" title="ACM Doctoral Dissertation Award">ACM Doctoral Dissertation Award</a></li> <li><a href="/wiki/Gordon_Bell_Prize" title="Gordon Bell Prize">Gordon Bell Prize</a></li> <li><a href="/wiki/Grace_Murray_Hopper_Award" title="Grace Murray Hopper Award">Grace Murray Hopper Award</a></li> <li><a href="/wiki/Ken_Kennedy_Award" title="Ken Kennedy Award">Ken Kennedy Award</a></li> <li><a href="/wiki/Paris_Kanellakis_Award" title="Paris Kanellakis Award">Paris Kanellakis Theory and Practice Award</a></li> <li><a href="/wiki/ACM_Prize_in_Computing" title="ACM Prize in Computing">ACM Prize in Computing</a></li> <li><a href="/wiki/ACM_Software_System_Award" title="ACM Software System Award">ACM Software System Award</a></li> <li><a href="/wiki/SIAM/ACM_Prize_in_Computational_Science_and_Engineering" class="mw-redirect" title="SIAM/ACM Prize in Computational Science and Engineering">SIAM/ACM Prize in Computational Science and Engineering</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">SIGs</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/CHI_Academy" title="CHI Academy">CHI Academy</a></li> <li><a class="mw-selflink selflink">Gödel Prize</a></li> <li><a href="/wiki/Knuth_Prize" title="Knuth Prize">Knuth Prize</a></li> <li><a href="/wiki/Steven_A._Coons_Award" class="mw-redirect" title="Steven A. Coons Award">Steven A. Coons Award</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Association_for_Computing_Machinery#Publications" title="Association for Computing Machinery">Publications</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Journal_of_the_ACM" title="Journal of the ACM">Journal of the ACM</a></li> <li><a href="/wiki/Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></li> <li><a href="/wiki/RISKS_Digest" title="RISKS Digest">RISKS Digest</a></li> <li><a href="/wiki/ACM_Digital_Library" class="mw-redirect" title="ACM Digital Library">ACM Digital Library</a></li> <li><a href="/wiki/ACM_Computing_Surveys" title="ACM Computing Surveys">ACM Computing Surveys</a></li> <li><a href="/wiki/Computers_in_Entertainment" title="Computers in Entertainment">Computers in Entertainment</a></li> <li><a href="/wiki/ACM_Interactions" title="ACM Interactions">ACM Interactions</a></li> <li><a href="/wiki/ACM_Queue" title="ACM Queue">ACM Queue</a></li> <li><a href="/wiki/XRDS_(magazine)" title="XRDS (magazine)">ACM XRDS</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Association_for_Computing_Machinery#Conferences" title="Association for Computing Machinery">Conferences</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/ACM_Multimedia" title="ACM Multimedia">ACM-MM</a></li> <li><a href="/wiki/AAAI/ACM_Conference_on_AI,_Ethics,_and_Society" title="AAAI/ACM Conference on AI, Ethics, and Society">AIES</a></li> <li><a href="/wiki/International_Conference_on_Architectural_Support_for_Programming_Languages_and_Operating_Systems" title="International Conference on Architectural Support for Programming Languages and Operating Systems">ASPLOS</a></li> <li><a href="/wiki/Conference_on_Human_Factors_in_Computing_Systems" title="Conference on Human Factors in Computing Systems">CHI</a></li> <li><a href="/wiki/Conference_on_Information_and_Knowledge_Management" title="Conference on Information and Knowledge Management">CIKM</a></li> <li><a href="/wiki/Design_Automation_Conference" title="Design Automation Conference">DAC</a></li> <li><a href="/wiki/Distributed_Event-Based_Systems" title="Distributed Event-Based Systems">DEBS</a></li> <li><a href="/wiki/ACM_Conference_on_Fairness,_Accountability,_and_Transparency" title="ACM Conference on Fairness, Accountability, and Transparency">FAccT</a></li> <li><a href="/wiki/Federated_Computing_Research_Conference" title="Federated Computing Research Conference">FCRC</a></li> <li><a href="/wiki/Genetic_and_Evolutionary_Computation_Conference" title="Genetic and Evolutionary Computation Conference">GECCO</a></li> <li><a href="/wiki/Grace_Hopper_Celebration_of_Women_in_Computing" title="Grace Hopper Celebration of Women in Computing">GHC</a></li> <li><a href="/wiki/History_of_Programming_Languages" class="mw-redirect" title="History of Programming Languages">HOPL</a></li> <li><a href="/wiki/Hot_Chips" class="mw-redirect" title="Hot Chips">Hot Chips</a></li> <li><a href="/w/index.php?title=Conference_on_Hypertext_and_Hypermedia&action=edit&redlink=1" class="new" title="Conference on Hypertext and Hypermedia (page does not exist)">Hypertext</a></li> <li><a href="/wiki/Conference_on_Embedded_Networked_Sensor_Systems" title="Conference on Embedded Networked Sensor Systems">SenSys</a></li> <li><a href="/wiki/International_Symposium_on_Computer_Architecture" title="International Symposium on Computer Architecture">ISCA</a></li> <li><a href="/wiki/International_Symposium_on_Memory_Management" title="International Symposium on Memory Management">ISMM</a></li> <li><a href="/wiki/International_Symposium_on_Physical_Design" title="International Symposium on Physical Design">ISPD</a></li> <li><a href="/wiki/International_Symposium_on_Symbolic_and_Algebraic_Computation" title="International Symposium on Symbolic and Algebraic Computation">ISSAC</a></li> <li><a href="/wiki/Joint_Conference_on_Digital_Libraries" title="Joint Conference on Digital Libraries">JCDL</a></li> <li><a href="/wiki/International_Symposium_on_Microarchitecture" title="International Symposium on Microarchitecture">MICRO</a></li> <li><a href="/wiki/International_Conference_on_Mobile_Computing_and_Networking" title="International Conference on Mobile Computing and Networking">MobiCom</a></li> <li><a href="/wiki/Programming_Language_Design_and_Implementation" class="mw-redirect" title="Programming Language Design and Implementation">PLDI</a></li> <li><a href="/wiki/Symposium_on_Principles_of_Distributed_Computing" title="Symposium on Principles of Distributed Computing">PODC</a></li> <li><a href="/wiki/Symposium_on_Principles_of_Database_Systems" title="Symposium on Principles of Database Systems">PODS</a></li> <li><a href="/wiki/Symposium_on_Principles_of_Programming_Languages" title="Symposium on Principles of Programming Languages">POPL</a></li> <li><a href="/wiki/Symposium_on_Principles_and_Practice_of_Parallel_Programming" title="Symposium on Principles and Practice of Parallel Programming">PPoPP</a></li> <li><a href="/wiki/ACM_Conference_on_Recommender_Systems" title="ACM Conference on Recommender Systems">RecSys</a></li> <li><a href="/wiki/ACM/IEEE_Supercomputing_Conference" title="ACM/IEEE Supercomputing Conference">SC</a></li> <li><a href="/wiki/SIGCOMM" title="SIGCOMM">SIGCOMM</a></li> <li><a href="/wiki/SIGCSE_Technical_Symposium_on_Computer_Science_Education" title="SIGCSE Technical Symposium on Computer Science Education">SIGCSE</a></li> <li><a href="/wiki/SIGGRAPH" title="SIGGRAPH">SIGGRAPH</a></li> <li><a href="/wiki/Symposium_on_Computational_Geometry" title="Symposium on Computational Geometry">SoCG</a></li> <li><a href="/wiki/Symposium_on_Discrete_Algorithms" title="Symposium on Discrete Algorithms">SODA</a></li> <li><a href="/wiki/Symposium_on_Operating_Systems_Principles" title="Symposium on Operating Systems Principles">SOSP</a></li> <li><a href="/wiki/Symposium_on_Parallelism_in_Algorithms_and_Architectures" title="Symposium on Parallelism in Algorithms and Architectures">SPAA</a></li> <li><a href="/wiki/SPLASH_(conference)" title="SPLASH (conference)">SPLASH</a></li> <li><a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">STOC</a></li> <li><a href="/wiki/Richard_Tapia_Celebration_of_Diversity_in_Computing" title="Richard Tapia Celebration of Diversity in Computing">TAPIA</a></li> <li><a href="/wiki/ACM_Symposium_on_User_Interface_Software_and_Technology" title="ACM Symposium on User Interface Software and Technology">UIST</a></li> <li><a href="/wiki/ACM/IEEE_Virtual_Reality_International_Conference" title="ACM/IEEE Virtual Reality International Conference">VRIC</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Educational programs</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/ACM-W" title="ACM-W">ACM-W</a></li> <li><a href="/wiki/ACM_International_Collegiate_Programming_Contest" class="mw-redirect" title="ACM International Collegiate Programming Contest">ACM International Collegiate Programming Contest</a></li> <li><a href="/wiki/ACM_Student_Research_Competition" title="ACM Student Research Competition">ACM Student Research Competition</a></li> <li><a href="/wiki/Upsilon_Pi_Epsilon" title="Upsilon Pi Epsilon">Upsilon Pi Epsilon</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Gödel_Prize&oldid=1239821267">https://en.wikipedia.org/w/index.php?title=Gödel_Prize&oldid=1239821267</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Theoretical_computer_science" title="Category:Theoretical computer science">Theoretical computer science</a></li><li><a href="/wiki/Category:Computer_science_awards" title="Category:Computer science awards">Computer science awards</a></li><li><a href="/wiki/Category:Awards_established_in_1993" title="Category:Awards established in 1993">Awards established in 1993</a></li><li><a href="/wiki/Category:Annual_events" title="Category:Annual events">Annual events</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:All_articles_with_dead_external_links" title="Category:All articles with dead external links">All articles with dead external links</a></li><li><a href="/wiki/Category:Articles_with_dead_external_links_from_December_2017" title="Category:Articles with dead external links from December 2017">Articles with dead external links from December 2017</a></li><li><a href="/wiki/Category:Articles_with_permanently_dead_external_links" title="Category:Articles with permanently dead external links">Articles with permanently dead external links</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 11 August 2024, at 19:10<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=G%C3%B6del_Prize&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-57488d5c7d-qdjvw","wgBackendResponseTime":625,"wgPageParseReport":{"limitreport":{"cputime":"0.849","walltime":"0.968","ppvisitednodes":{"value":3979,"limit":1000000},"postexpandincludesize":{"value":174183,"limit":2097152},"templateargumentsize":{"value":1504,"limit":2097152},"expansiondepth":{"value":17,"limit":100},"expensivefunctioncount":{"value":3,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":250214,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 847.601 1 -total"," 67.82% 574.831 2 Template:Reflist"," 30.95% 262.310 27 Template:Citation"," 14.93% 126.512 20 Template:Cite_journal"," 11.01% 93.295 1 Template:Short_description"," 10.77% 91.286 3 Template:Navbox"," 10.15% 86.045 1 Template:Gödel_Prize_laureates"," 6.98% 59.204 2 Template:Pagetype"," 4.57% 38.717 9 Template:Cite_web"," 4.45% 37.725 1 Template:Dead_link"]},"scribunto":{"limitreport-timeusage":{"value":"0.545","limit":"10.000"},"limitreport-memusage":{"value":5981661,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-5566db54f9-98xcb","timestamp":"20241127143459","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"G\u00f6del Prize","url":"https:\/\/en.wikipedia.org\/wiki\/G%C3%B6del_Prize","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1417143","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1417143","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2004-05-09T00:24:34Z","dateModified":"2024-08-11T19:10:53Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/c\/c1\/1925_kurt_g%C3%B6del.png","headline":"award for outstanding papers in the area of theoretical computer science"}</script> </body> </html>