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>Tim Roughgarden - 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":"6752d4d8-d4ce-4f01-8aeb-a6a710695ea6","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Tim_Roughgarden","wgTitle":"Tim Roughgarden","wgCurRevisionId":1245484939,"wgRevisionId":1245484939,"wgArticleId":35870516,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: multiple names: authors list","Articles with short description","Short description matches Wikidata","Use mdy dates from March 2024","Articles with hCards","All stub articles","Living people","American theoretical computer scientists","Columbia University faculty","Stanford University faculty","Gödel Prize laureates","1975 births","2023 fellows of the Association for Computing Machinery","Recipients of the Presidential Early Career Award for Scientists and Engineers" ,"Computer scientist stubs"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Tim_Roughgarden","wgRelevantArticleId":35870516,"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":7000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty" :false,"wgWikibaseItemId":"Q7804199","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.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","site","mediawiki.page.ready","jquery.makeCollapsible","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.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%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/b/b6/Tim_Roughgarden_2022.jpg"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1513"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/b/b6/Tim_Roughgarden_2022.jpg"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="1008"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="807"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Tim Roughgarden - 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/Tim_Roughgarden"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Tim_Roughgarden&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/Tim_Roughgarden"> <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-Tim_Roughgarden rootpage-Tim_Roughgarden 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=Tim+Roughgarden" 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=Tim+Roughgarden" 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=Tim+Roughgarden" 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=Tim+Roughgarden" 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-Selected_publications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Selected_publications"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Selected publications</span> </div> </a> <ul id="toc-Selected_publications-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">2</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>External links</span> </div> </a> <ul id="toc-External_links-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">Tim Roughgarden</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 2 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-2" 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">2 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Tim_Roughgarden" title="Tim Roughgarden – German" lang="de" hreflang="de" data-title="Tim Roughgarden" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Tim_Roughgarden" title="Tim Roughgarden – French" lang="fr" hreflang="fr" data-title="Tim Roughgarden" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</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/Q7804199#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/Tim_Roughgarden" 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:Tim_Roughgarden" 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/Tim_Roughgarden"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Tim_Roughgarden&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=Tim_Roughgarden&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/Tim_Roughgarden"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Tim_Roughgarden&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=Tim_Roughgarden&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/Tim_Roughgarden" 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/Tim_Roughgarden" 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=Tim_Roughgarden&oldid=1245484939" 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=Tim_Roughgarden&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=Tim_Roughgarden&id=1245484939&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%2FTim_Roughgarden"><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%2FTim_Roughgarden"><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=Tim_Roughgarden&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=Tim_Roughgarden&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 id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q7804199" 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">American computer scientist</div> <p class="mw-empty-elt"> </p> <style data-mw-deduplicate="TemplateStyles:r1257001546">.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme) div:not(.notheme){background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table tr{display:table-row!important}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}</style><table class="infobox biography vcard"><tbody><tr><th colspan="2" class="infobox-above" style="font-size:125%;"><div class="fn">Timothy Avelin Roughgarden</div></th></tr><tr><td colspan="2" class="infobox-image"><span class="mw-default-size" typeof="mw:File/Frameless"><a href="/wiki/File:Tim_Roughgarden_2022.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Tim_Roughgarden_2022.jpg/220px-Tim_Roughgarden_2022.jpg" decoding="async" width="220" height="277" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Tim_Roughgarden_2022.jpg/330px-Tim_Roughgarden_2022.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Tim_Roughgarden_2022.jpg/440px-Tim_Roughgarden_2022.jpg 2x" data-file-width="480" data-file-height="605" /></a></span><div class="infobox-caption">Roughgarden in 2022</div></td></tr><tr><th scope="row" class="infobox-label">Born</th><td class="infobox-data"><span style="display:none"> (<span class="bday">1975-07-20</span>) </span>July 20, 1975<span class="noprint ForceAgeToShow"> (age 49)</span></td></tr><tr><th scope="row" class="infobox-label">Alma mater</th><td class="infobox-data"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style><div class="plainlist"> <ul><li><a href="/wiki/Stanford_University" title="Stanford University">Stanford University</a></li> <li><a href="/wiki/Cornell_University" title="Cornell University">Cornell University</a></li></ul> </div></td></tr><tr><th scope="row" class="infobox-label">Known for</th><td class="infobox-data">Contributions to <a href="/wiki/Price_of_anarchy#Selfish_Routing" title="Price of anarchy">Selfish Routing</a> in the context of <a href="/wiki/Computer_Science" class="mw-redirect" title="Computer Science">Computer Science</a></td></tr><tr><th scope="row" class="infobox-label">Awards</th><td class="infobox-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1126788409"><div class="plainlist"> <ul><li><a href="/wiki/Grace_Murray_Hopper_Award" title="Grace Murray Hopper Award">Grace Murray Hopper Award</a> (2009)</li> <li><a href="/wiki/G%C3%B6del_prize" class="mw-redirect" title="Gödel prize">Gödel prize</a> (2012)</li> <li>Social Choice and Welfare Prize (2014)</li> <li><a href="/wiki/Kalai_Prize" title="Kalai Prize">Kalai Prize</a> (2016)</li></ul> </div></td></tr><tr><td colspan="2" class="infobox-full-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1257001546"><b>Scientific career</b></td></tr><tr><th scope="row" class="infobox-label">Fields</th><td class="infobox-data category"><a href="/wiki/Computer_Science" class="mw-redirect" title="Computer Science">Computer Science</a>, <a href="/wiki/Game_Theory" class="mw-redirect" title="Game Theory">Game Theory</a></td></tr><tr><th scope="row" class="infobox-label">Institutions</th><td class="infobox-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1126788409"><div class="plainlist"> <ul><li><a href="/wiki/Columbia_University" title="Columbia University">Columbia University</a></li> <li><a href="/wiki/Stanford_University" title="Stanford University">Stanford University</a></li></ul> </div></td></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/Thesis" title="Thesis">Thesis</a></th><td class="infobox-data"><i><a rel="nofollow" class="external text" href="http://theory.stanford.edu/~tim/papers/thesis.pdf">Selfish routing</a></i> <span style="font-size:97%;">(2002)</span></td></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/Doctoral_advisor" title="Doctoral advisor">Doctoral advisor</a></th><td class="infobox-data"><a href="/wiki/%C3%89va_Tardos" title="Éva Tardos">Éva Tardos</a></td></tr><tr style="display:none"><td colspan="2"> </td></tr><tr><th scope="row" class="infobox-label">Website</th><td class="infobox-data"><a rel="nofollow" class="external free" href="http://timroughgarden.org/">http://timroughgarden.org/</a></td></tr></tbody></table> <p><b>Timothy Avelin Roughgarden</b> (born July 20, 1975) is an American computer scientist and a professor of Computer Science at <a href="/wiki/Columbia_University" title="Columbia University">Columbia University</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> Roughgarden's work deals primarily with <a href="/wiki/Game_theory" title="Game theory">game theoretic</a> questions in <a href="/wiki/Computer_science" title="Computer science">computer science</a>. </p><p>Roughgarden received his Ph.D. from <a href="/wiki/Cornell_University" title="Cornell University">Cornell University</a> in 2002, under the supervision of <a href="/wiki/%C3%89va_Tardos" title="Éva Tardos">Éva Tardos</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> He did a postdoc at <a href="/wiki/University_of_California,_Berkeley" title="University of California, Berkeley">University of California, Berkeley</a> in 2004. From 2004 to 2018, Roughgarden was a professor at the Computer Science department at <a href="/wiki/Stanford_University" title="Stanford University">Stanford University</a> working on algorithms and game theory. Roughgarden teaches a four-part algorithms specialization on <a href="/wiki/Coursera" title="Coursera">Coursera</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>He received the <a href="/wiki/Symposium_on_Theory_of_Computing#Awards" title="Symposium on Theory of Computing">Danny Lewin award</a> at <a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing">STOC</a> 2002 for the best student paper. He received the <a href="/wiki/Presidential_Early_Career_Award_for_Scientists_and_Engineers" title="Presidential Early Career Award for Scientists and Engineers">Presidential Early Career Award for Scientists and Engineers</a> in 2007,<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> the <a href="/wiki/Grace_Murray_Hopper_Award" title="Grace Murray Hopper Award">Grace Murray Hopper Award</a> in 2009,<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> and the <a href="/wiki/G%C3%B6del_Prize" title="Gödel Prize">Gödel Prize</a> in 2012 for his work on routing traffic in large-scale communication networks to optimize performance of a congested network.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> He received a <a href="/wiki/Guggenheim_Fellowship" title="Guggenheim Fellowship">Guggenheim Fellowship</a> in 2017<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> and the <a href="/wiki/Kalai_Prize" title="Kalai Prize">Kalai Prize</a> in 2016. </p><p>Roughgarden is a co-editor of the 2016 textbook <i>Algorithmic Game Theory</i>, as well as the author of two chapters (<i>Introduction to the Inefficiency of Equilibria</i> and <i>Routing Games)</i>.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Selected_publications">Selected publications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Tim_Roughgarden&action=edit&section=1" title="Edit section: Selected publications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><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="CITEREFRoughgarden2016" class="citation book cs1">Roughgarden, Tim (2016). <i>Twenty Lectures on Algorithmic Game Theory</i>. Cambridge University Press.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Twenty+Lectures+on+Algorithmic+Game+Theory&rft.pub=Cambridge+University+Press&rft.date=2016&rft.aulast=Roughgarden&rft.aufirst=Tim&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRoughgarden2005" class="citation book cs1">Roughgarden, Tim (2005). <i>Selfish Routing and the Price of Anarchy</i>. MIT Press.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Selfish+Routing+and+the+Price+of+Anarchy&rft.pub=MIT+Press&rft.date=2005&rft.aulast=Roughgarden&rft.aufirst=Tim&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRoughgardenTardos2002" class="citation journal cs1">Roughgarden, Tim; <a href="/wiki/%C3%89va_Tardos" title="Éva Tardos">Tardos, Éva</a> (March 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-03&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%3ATim+Roughgarden" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRoughgarden2002" class="citation cs2">Roughgarden, Tim (2002), "The price of anarchy is independent of the network topology", <a href="/wiki/Symposium_on_Theory_of_Computing" title="Symposium on Theory of Computing"><i>Proceedings of the 34th Symposium on Theory of Computing</i></a>, pp. 428–437</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=The+price+of+anarchy+is+independent+of+the+network+topology&rft.btitle=Proceedings+of+the+34th+Symposium+on+Theory+of+Computing&rft.pages=428-437&rft.date=2002&rft.aulast=Roughgarden&rft.aufirst=Tim&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" class="Z3988"></span></li></ul> <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=Tim_Roughgarden&action=edit&section=2" title="Edit section: References"><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"> <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="http://theory.stanford.edu/~tim/">"Tim Roughgarden's Homepage"</a>. <i>theory.stanford.edu</i><span class="reference-accessdate">. Retrieved <span class="nowrap">July 6,</span> 2015</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=theory.stanford.edu&rft.atitle=Tim+Roughgarden%27s+Homepage&rft_id=http%3A%2F%2Ftheory.stanford.edu%2F~tim%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</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://archive.today/20120717014255/http://soe.stanford.edu/research/surreal.htm">"Tim Roughgarden's Profile - Stanford Profiles"</a>. <i>soe.stanford.edu</i>. <a href="/wiki/Stanford_University" title="Stanford University">Stanford University</a>. Archived from <a rel="nofollow" class="external text" href="http://soe.stanford.edu/research/surreal.htm">the original</a> on July 17, 2012<span class="reference-accessdate">. Retrieved <span class="nowrap">July 6,</span> 2015</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=soe.stanford.edu&rft.atitle=Tim+Roughgarden%27s+Profile+-+Stanford+Profiles&rft_id=http%3A%2F%2Fsoe.stanford.edu%2Fresearch%2Fsurreal.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</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://www.coursera.org/specializations/algorithms">"Algorithms Specialization"</a>. <i>coursera.org</i>. <a href="/wiki/Coursera" title="Coursera">Coursera Inc.</a><span class="reference-accessdate"> Retrieved <span class="nowrap">May 17,</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=coursera.org&rft.atitle=Algorithms+Specialization&rft_id=https%3A%2F%2Fwww.coursera.org%2Fspecializations%2Falgorithms&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" 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 class="citation pressrelease cs1"><a rel="nofollow" class="external text" href="https://georgewbush-whitehouse.archives.gov/news/releases/2008/12/20081219-10.html">"White House Announces 2007 Awards for Early Career Scientists and Engineers"</a>. <i>The George W. Bush White House Archives</i> (Press release). <a href="/wiki/Washington,_D.C." title="Washington, D.C.">Washington, D.C.</a>: <a href="/wiki/Office_of_Science_and_Technology_Policy" title="Office of Science and Technology Policy">Office of Science and Technology Policy</a>. December 19, 2008<span class="reference-accessdate">. Retrieved <span class="nowrap">January 19,</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=White+House+Announces+2007+Awards+for+Early+Career+Scientists+and+Engineers&rft.place=Washington%2C+D.C.&rft.pub=Office+of+Science+and+Technology+Policy&rft.date=2008-12-19&rft_id=https%3A%2F%2Fgeorgewbush-whitehouse.archives.gov%2Fnews%2Freleases%2F2008%2F12%2F20081219-10.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" 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 class="citation pressrelease cs1"><a rel="nofollow" class="external text" href="https://cacm.acm.org/careers/82077-acm-awards-recognize-computer-science-innovation/fulltext?mobile=true?mobile=false">"ACM Awards Recognize Computer Science Innovation"</a>. <i>acm.org</i> (Press release). <a href="/wiki/Association_for_Computing_Machinery" title="Association for Computing Machinery">Association for Computing Machinery</a>. March 31, 2010<span class="reference-accessdate">. Retrieved <span class="nowrap">January 19,</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=ACM+Awards+Recognize+Computer+Science+Innovation&rft.pub=Association+for+Computing+Machinery&rft.date=2010-03-31&rft_id=https%3A%2F%2Fcacm.acm.org%2Fcareers%2F82077-acm-awards-recognize-computer-science-innovation%2Ffulltext%3Fmobile%3Dtrue%3Fmobile%3Dfalse&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" 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 class="citation web cs1"><a rel="nofollow" class="external text" href="http://eatcs.org/index.php/component/content/article/1-news/1251-the-goedel-prize-2012-laudatio-">"The Gödel Prize 2012 - Laudatio"</a>. European Association for Theoretical Computer Science. 2012<span class="reference-accessdate">. Retrieved <span class="nowrap">January 19,</span> 2020</span>.</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+Prize+2012+-+Laudatio&rft.pub=European+Association+for+Theoretical+Computer+Science&rft.date=2012&rft_id=http%3A%2F%2Featcs.org%2Findex.php%2Fcomponent%2Fcontent%2Farticle%2F1-news%2F1251-the-goedel-prize-2012-laudatio-&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" 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 class="citation web cs1"><a rel="nofollow" class="external text" href="http://gametheorysociety.org/acm-godel-prize-for-seminal-papers-in-algorithmic-game-theory/">"ACM Gödel Prize for Seminal Papers in Algorithmic Game Theory"</a>. Game Theory Society. June 3, 2012<span class="reference-accessdate">. Retrieved <span class="nowrap">January 19,</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=ACM+G%C3%B6del+Prize+for+Seminal+Papers+in+Algorithmic+Game+Theory&rft.pub=Game+Theory+Society&rft.date=2012-06-03&rft_id=http%3A%2F%2Fgametheorysociety.org%2Facm-godel-prize-for-seminal-papers-in-algorithmic-game-theory%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" 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 class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.gf.org/fellows/all-fellows/tim-roughgarden/">"Tim Roughgarden: Fellow, Awarded 2017"</a>. <i>gf.org</i>. <a href="/wiki/John_Simon_Guggenheim_Memorial_Foundation" title="John Simon Guggenheim Memorial Foundation">John Simon Guggenheim Memorial Foundation</a>. 2017<span class="reference-accessdate">. Retrieved <span class="nowrap">January 19,</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=gf.org&rft.atitle=Tim+Roughgarden%3A+Fellow%2C+Awarded+2017&rft.date=2017&rft_id=https%3A%2F%2Fwww.gf.org%2Ffellows%2Fall-fellows%2Ftim-roughgarden%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" 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="CITEREFKnowles2017" class="citation news cs1">Knowles, Hannah (April 17, 2017). <a rel="nofollow" class="external text" href="https://www.stanforddaily.com/2017/04/16/four-professors-named-guggenheim-fellows/">"Four professors named Guggenheim fellows"</a>. <i><a href="/wiki/The_Stanford_Daily" title="The Stanford Daily">The Stanford Daily</a></i><span class="reference-accessdate">. Retrieved <span class="nowrap">January 19,</span> 2020</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Stanford+Daily&rft.atitle=Four+professors+named+Guggenheim+fellows&rft.date=2017-04-17&rft.aulast=Knowles&rft.aufirst=Hannah&rft_id=https%3A%2F%2Fwww.stanforddaily.com%2F2017%2F04%2F16%2Ffour-professors-named-guggenheim-fellows%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" 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="CITEREFHrsg.2007" class="citation book cs1">Hrsg., Nisan, Noam (September 24, 2007). <a rel="nofollow" class="external text" href="http://worldcat.org/oclc/870638977"><i>Algorithmic game theory</i></a>. Cambridge University Press. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-521-87282-9" title="Special:BookSources/978-0-521-87282-9"><bdi>978-0-521-87282-9</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/870638977">870638977</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Algorithmic+game+theory&rft.pub=Cambridge+University+Press&rft.date=2007-09-24&rft_id=info%3Aoclcnum%2F870638977&rft.isbn=978-0-521-87282-9&rft.aulast=Hrsg.&rft.aufirst=Nisan%2C+Noam&rft_id=http%3A%2F%2Fworldcat.org%2Foclc%2F870638977&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_book" title="Template:Cite book">cite book</a>}}</code>: CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</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 class="citation web cs1"><a rel="nofollow" class="external text" href="http://timroughgarden.org/books.html">"Tim Roughgarden's Books and Surveys"</a>. <i>timroughgarden.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">April 7,</span> 2021</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=timroughgarden.org&rft.atitle=Tim+Roughgarden%27s+Books+and+Surveys&rft_id=http%3A%2F%2Ftimroughgarden.org%2Fbooks.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ATim+Roughgarden" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Tim_Roughgarden&action=edit&section=3" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://genealogy.math.ndsu.nodak.edu/id.php?id=73527">Mathematics Genealogy Project</a></li> <li>Roughgarden's textbook: <i><a rel="nofollow" class="external text" href="https://www.amazon.com/Algorithmic-Game-Theory-Noam-Nisan/dp/0521872820">Algorithmic Game Theory</a></i></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="Grace_Murray_Hopper_Award_recipients" 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"><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:Hopper_winners" title="Template:Hopper winners"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Hopper_winners" title="Template talk:Hopper winners"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Hopper_winners" title="Special:EditPage/Template:Hopper winners"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Grace_Murray_Hopper_Award_recipients" style="font-size:114%;margin:0 4em"><a href="/wiki/Grace_Murray_Hopper_Award" title="Grace Murray Hopper Award">Grace Murray Hopper Award</a> recipients</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><span class="nowrap"><a href="/wiki/Donald_Knuth" title="Donald Knuth">Knuth</a> (1971)</span></li> <li><span class="nowrap"><a href="/wiki/Paul_H._Dirksen" class="mw-redirect" title="Paul H. Dirksen">Dirksen</a> (1972)</span></li> <li><span class="nowrap"><a href="/wiki/Paul_H._Cress" title="Paul H. Cress">Cress</a> (1972)</span></li> <li><span class="nowrap"><a href="/wiki/Lawrence_M._Breed" title="Lawrence M. Breed">Breed</a>/<a href="/wiki/Richard_H._Lathwell" title="Richard H. Lathwell">Lathwell</a>/<a href="/wiki/Roger_Moore_(computer_scientist)" title="Roger Moore (computer scientist)">Moore</a> (1973)</span></li> <li><span class="nowrap"><a href="/wiki/George_N._Baird" title="George N. Baird">Baird</a> (1974)</span></li> <li><span class="nowrap"><a href="/wiki/Allan_L._Scherr" title="Allan L. Scherr">Scherr</a> (1975)</span></li> <li><span class="nowrap"><a href="/wiki/Edward_H._Shortliffe" title="Edward H. Shortliffe">Shortliffe</a> (1976)</span></li> <li><span class="nowrap"><a href="/wiki/Ray_Kurzweil" title="Ray Kurzweil">Kurzweil</a> (1978)</span></li> <li><span class="nowrap"><a href="/wiki/Steve_Wozniak" title="Steve Wozniak">Wozniak</a> (1979)</span></li> <li><span class="nowrap"><a href="/wiki/Robert_Metcalfe" title="Robert Metcalfe">Metcalfe</a> (1980)</span></li> <li><span class="nowrap"><a href="/wiki/Daniel_S._Bricklin" class="mw-redirect" title="Daniel S. Bricklin">Bricklin</a> (1981)</span></li> <li><span class="nowrap"><a href="/wiki/Brian_Reid_(computer_scientist)" title="Brian Reid (computer scientist)">Reid</a> (1982)</span></li> <li><span class="nowrap"><a href="/wiki/Dan_Ingalls" title="Dan Ingalls">Ingalls</a> (1984)</span></li> <li><span class="nowrap"><a href="/wiki/Cordell_Green" title="Cordell Green">Green</a> (1985)</span></li> <li><span class="nowrap"><a href="/wiki/Bill_Joy" title="Bill Joy">Joy</a> (1986)</span></li> <li><span class="nowrap"><a href="/wiki/John_Ousterhout" title="John Ousterhout">Ousterhout</a> (1987)</span></li> <li><span class="nowrap"><a href="/wiki/Guy_L._Steele_Jr." title="Guy L. Steele Jr.">Steele</a> (1988)</span></li> <li><span class="nowrap"><a href="/wiki/Danny_Hillis" title="Danny Hillis">Hillis</a> (1989)</span></li> <li><span class="nowrap"><a href="/wiki/Richard_Stallman" title="Richard Stallman">Stallman</a> (1990)</span></li> <li><span class="nowrap"><a href="/wiki/Feng-hsiung_Hsu" title="Feng-hsiung Hsu">Hsu</a> (1991)</span></li> <li><span class="nowrap"><a href="/wiki/Bjarne_Stroustrup" title="Bjarne Stroustrup">Stroustrup</a> (1993)</span></li> <li><span class="nowrap"><a href="/wiki/Shafi_Goldwasser" title="Shafi Goldwasser">Goldwasser</a> (1996)</span></li> <li><span class="nowrap"><a href="/wiki/Wen-mei_Hwu" title="Wen-mei Hwu">Hwu</a> (1999)</span></li> <li><span class="nowrap"><a href="/wiki/Lydia_Kavraki" title="Lydia Kavraki">Kavraki</a> (2000)</span></li> <li><span class="nowrap"><a href="/wiki/George_Necula" title="George Necula">Necula</a> (2001)</span></li> <li><span class="nowrap"><a href="/wiki/Ramakrishnan_Srikant" title="Ramakrishnan Srikant">Srikant</a> (2002)</span></li> <li><span class="nowrap"><a href="/wiki/Stephen_W._Keckler" title="Stephen W. Keckler">Keckler</a> (2003)</span></li> <li><span class="nowrap"><a href="/wiki/Jennifer_Rexford" title="Jennifer Rexford">Rexford</a> (2004)</span></li> <li><span class="nowrap"><a href="/wiki/Omer_Reingold" title="Omer Reingold">Reingold</a> (2005)</span></li> <li><span class="nowrap"><a href="/wiki/Dan_Klein" title="Dan Klein">Klein</a> (2006)</span></li> <li><span class="nowrap"><a href="/wiki/Vern_Paxson" title="Vern Paxson">Paxson</a> (2007)</span></li> <li><span class="nowrap"><a href="/wiki/Dawson_Engler" title="Dawson Engler">Engler</a> (2008)</span></li> <li><span class="nowrap"><a class="mw-selflink selflink">Roughgarden</a> (2009)</span></li> <li><span class="nowrap"><a href="/wiki/Craig_Gentry_(computer_scientist)" title="Craig Gentry (computer scientist)">Gentry</a> (2010)</span></li> <li><span class="nowrap"><a href="/wiki/Luis_von_Ahn" title="Luis von Ahn">Ahn</a> (2011)</span></li> <li><span class="nowrap"><a href="/wiki/Martin_Casado" title="Martin Casado">Casado</a> and <a href="/wiki/Dina_Katabi" title="Dina Katabi">Katabi</a> (2012)</span></li> <li><span class="nowrap"><a href="/wiki/Pedro_Felipe_Felzenszwalb" title="Pedro Felipe Felzenszwalb">Felzenszwalb</a> (2013)</span></li> <li><span class="nowrap"><a href="/wiki/Sylvia_Ratnasamy" title="Sylvia Ratnasamy">Ratnasamy</a> (2014)</span></li> <li><span class="nowrap"><a href="/wiki/Brent_Waters" title="Brent Waters">Waters</a> (2015)</span></li> <li><span class="nowrap"><a href="/wiki/Jeffrey_Heer" title="Jeffrey Heer">Heer</a> (2016)</span></li> <li><span class="nowrap"><a href="/wiki/Amanda_Randles" title="Amanda Randles">Randles</a> (2017)</span></li> <li><span class="nowrap"><a href="/wiki/Constantinos_Daskalakis" title="Constantinos Daskalakis">Daskalakis</a> and <a href="/wiki/Michael_J._Freedman" title="Michael J. Freedman">Freedman</a> (2018)</span></li> <li><span class="nowrap"><a href="/wiki/Maria-Florina_Balcan" title="Maria-Florina Balcan">Balcan</a> (2019)</span></li> <li><span class="nowrap"><a href="/w/index.php?title=Shyamnath_Gollakota&action=edit&redlink=1" class="new" title="Shyamnath Gollakota (page does not exist)">Gollakota</a> (2020)</span></li> <li><span class="nowrap"><a href="/w/index.php?title=Raluca_Ada_Popa&action=edit&redlink=1" class="new" title="Raluca Ada Popa (page does not exist)">Popa</a> (2021)</span></li> <li><span class="nowrap"><a href="/w/index.php?title=Mohammad_Alizadeh&action=edit&redlink=1" class="new" title="Mohammad Alizadeh (page does not exist)">Alizadeh</a> (2022)</span></li> <li><span class="nowrap"><a href="/w/index.php?title=Prateek_Mittal&action=edit&redlink=1" class="new" title="Prateek Mittal (page does not exist)">Mittal</a> (2023)</span></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="Gödel_Prize_laureates" 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: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 href="/wiki/G%C3%B6del_Prize" title="Gödel Prize">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 class="mw-selflink selflink">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"><style data-mw-deduplicate="TemplateStyles:r1038841319">.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q7804199#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata" 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"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q7804199#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata" style="font-size:114%;margin:0 4em"><a href="/wiki/Help:Authority_control" title="Help:Authority control">Authority control databases</a> <span class="mw-valign-text-top noprint" typeof="mw:File/Frameless"><a href="https://www.wikidata.org/wiki/Q7804199#identifiers" title="Edit this at Wikidata"><img alt="Edit this at Wikidata" src="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/10px-OOjs_UI_icon_edit-ltr-progressive.svg.png" decoding="async" width="10" height="10" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/15px-OOjs_UI_icon_edit-ltr-progressive.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/8/8a/OOjs_UI_icon_edit-ltr-progressive.svg/20px-OOjs_UI_icon_edit-ltr-progressive.svg.png 2x" data-file-width="20" data-file-height="20" /></a></span></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">International</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://isni.org/isni/0000000117195180">ISNI</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://viaf.org/viaf/164900074">VIAF</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.oclc.org/worldcat/entity/E39PBJqBw6Pc3qXYcrRgT4HQv3">WorldCat</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/1117167275">Germany</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/n2004014759">United States</a></span></li><li><span class="uid"><span class="rt-commentedText tooltip tooltip-dotted" title="Roughgarden, Tim"><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=vse20201097374&CON_LNG=ENG">Czech Republic</a></span></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="http://olduli.nli.org.il/F/?func=find-b&local_base=NLX10&find_code=UID&request=987007451064505171">Israel</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Academics</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.mathgenealogy.org/id.php?id=73527">Mathematics Genealogy Project</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://dl.acm.org/profile/81342509525">Association for Computing Machinery</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://scholar.google.com/citations?user=0lcJYs8AAAAJ">Google Scholar</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://dblp.org/pid/r/TimRoughgarden">DBLP</a></span></li><li><span class="uid"><a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet/MRAuthorID/694023">MathSciNet</a></span></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://www.idref.fr/160109787">IdRef</a></span></li></ul></div></td></tr></tbody></table></div> <p><br /> </p> <style data-mw-deduplicate="TemplateStyles:r1012311289">.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}</style><div role="note" class="metadata plainlinks asbox stub"><table role="presentation"><tbody><tr class="noresize"><td><big><b>P ≟ NP</b></big> </td><td><p class="asbox-body">This biographical article relating to a <a href="/wiki/Computer_scientist" title="Computer scientist">computer scientist</a> is a <a href="/wiki/Wikipedia:Stub" title="Wikipedia:Stub">stub</a>. You can help Wikipedia by <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Tim_Roughgarden&action=edit">expanding it</a>.</p></td></tr></tbody></table><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:Compu-scientist-stub" title="Template:Compu-scientist-stub"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Compu-scientist-stub" title="Template talk:Compu-scientist-stub"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Compu-scientist-stub" title="Special:EditPage/Template:Compu-scientist-stub"><abbr title="Edit this template">e</abbr></a></li></ul></div></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=Tim_Roughgarden&oldid=1245484939">https://en.wikipedia.org/w/index.php?title=Tim_Roughgarden&oldid=1245484939</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:Living_people" title="Category:Living people">Living people</a></li><li><a href="/wiki/Category:American_theoretical_computer_scientists" title="Category:American theoretical computer scientists">American theoretical computer scientists</a></li><li><a href="/wiki/Category:Columbia_University_faculty" title="Category:Columbia University faculty">Columbia University faculty</a></li><li><a href="/wiki/Category:Stanford_University_faculty" title="Category:Stanford University faculty">Stanford University faculty</a></li><li><a href="/wiki/Category:G%C3%B6del_Prize_laureates" title="Category:Gödel Prize laureates">Gödel Prize laureates</a></li><li><a href="/wiki/Category:1975_births" title="Category:1975 births">1975 births</a></li><li><a href="/wiki/Category:2023_fellows_of_the_Association_for_Computing_Machinery" title="Category:2023 fellows of the Association for Computing Machinery">2023 fellows of the Association for Computing Machinery</a></li><li><a href="/wiki/Category:Recipients_of_the_Presidential_Early_Career_Award_for_Scientists_and_Engineers" title="Category:Recipients of the Presidential Early Career Award for Scientists and Engineers">Recipients of the Presidential Early Career Award for Scientists and Engineers</a></li><li><a href="/wiki/Category:Computer_scientist_stubs" title="Category:Computer scientist stubs">Computer scientist stubs</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:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">CS1 maint: multiple names: authors list</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_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Use_mdy_dates_from_March_2024" title="Category:Use mdy dates from March 2024">Use mdy dates from March 2024</a></li><li><a href="/wiki/Category:Articles_with_hCards" title="Category:Articles with hCards">Articles with hCards</a></li><li><a href="/wiki/Category:All_stub_articles" title="Category:All stub articles">All stub articles</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 13 September 2024, at 07:41<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=Tim_Roughgarden&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-f69cdc8f6-lljb8","wgBackendResponseTime":181,"wgPageParseReport":{"limitreport":{"cputime":"0.561","walltime":"0.718","ppvisitednodes":{"value":2941,"limit":1000000},"postexpandincludesize":{"value":72760,"limit":2097152},"templateargumentsize":{"value":4203,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":75497,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 635.438 1 -total"," 31.86% 202.458 1 Template:Infobox_scientist"," 15.21% 96.649 3 Template:Cite_book"," 13.25% 84.193 1 Template:Hopper_winners"," 13.10% 83.252 2 Template:Navbox"," 13.03% 82.775 1 Template:Short_description"," 11.05% 70.188 1 Template:Reflist"," 8.52% 54.156 1 Template:Birth_date_and_age"," 7.12% 45.246 2 Template:Pagetype"," 6.44% 40.909 21 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.386","limit":"10.000"},"limitreport-memusage":{"value":7464181,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-6xdtf","timestamp":"20241122161553","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Tim Roughgarden","url":"https:\/\/en.wikipedia.org\/wiki\/Tim_Roughgarden","sameAs":"http:\/\/www.wikidata.org\/entity\/Q7804199","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q7804199","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":"2012-05-19T12:51:24Z","dateModified":"2024-09-13T07:41:13Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/b\/b6\/Tim_Roughgarden_2022.jpg","headline":"American computer scientist"}</script> </body> </html>