CINXE.COM

<!DOCTYPE html>     <html class="no-js" lang="en" dir="ltr"> <head><script type="text/javascript" src="/_static/js/bundle-playback.js?v=HxkREWBo" charset="utf-8"></script> <script type="text/javascript" src="/_static/js/wombat.js?v=txqj7nKC" charset="utf-8"></script> <script>window.RufflePlayer=window.RufflePlayer||{};window.RufflePlayer.config={"autoplay":"on","unmuteOverlay":"hidden"};</script> <script type="text/javascript" src="/_static/js/ruffle/ruffle.js"></script> <script type="text/javascript"> __wm.init("https://web.archive.org/web"); __wm.wombat("http://www.math.ias.edu/csdm","20160521155639","https://web.archive.org/","web","/_static/", "1463846199"); </script> <link rel="stylesheet" type="text/css" href="/_static/css/banner-styles.css?v=S1zqJCYt" /> <link rel="stylesheet" type="text/css" href="/_static/css/iconochive.css?v=3PDvdIFv" />  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"/> <link rel="shortcut icon" href="https://web.archive.org/web/20160521155639im_/http://www.math.ias.edu/sites/all/themes/math/favicon.ico" type="image/vnd.microsoft.icon"/> <link rel="shortlink" href="/web/20160521155639/http://www.math.ias.edu/node/497"/> <script type="text/x-mathjax-config">MathJax.Hub.Config({ extensions: ['tex2jax.js'], jax: ['input/TeX','output/HTML-CSS'], tex2jax: { inlineMath: [ ['$','$'], ['\$','\$'] ], processEscapes: true }, showProcessingMessages: false, messageStyle: 'none' });</script><meta name="Generator" content="Drupal 7 (http://drupal.org)"/> <link rel="canonical" href="/web/20160521155639/http://www.math.ias.edu/csdm"/> <title>Theoretical Computer Science and Discrete Mathematics (CSDM) | IAS School of Mathematics</title> <meta name="HandheldFriendly" content="True"> <meta name="MobileOptimized" content="320"> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta http-equiv="cleartype" content="on"> <script src="//web.archive.org/web/20160521155639js_/http://use.typekit.net/cbu2zjn.js"></script> <script>try{Typekit.load();}catch(e){}</script> <style type="text/css" media="all"> @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/modules/system/system.messages.css?o7j4rc"); </style> <style type="text/css" media="all"> @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/modules/book/book.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/modules/comment/comment.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/date/date_api/date.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/date/date_popup/themes/datepicker.1.7.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/date/date_repeat_field/date_repeat_field.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/modules/field/theme/field.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/google_cse/google_cse.css?o7j4rc"); </style> <style type="text/css" media="screen"> @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/ias_calendar/ias_calendar.css?o7j4rc"); </style> <style type="text/css" media="all"> @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/modules/node/node.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/picture/picture_wysiwyg.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/modules/search/search.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/modules/user/user.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/calendar/css/calendar_multiday.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/views/css/views.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/ckeditor/css/ckeditor.css?o7j4rc"); </style> <style type="text/css" media="all"> @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/ctools/css/ctools.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/lightbox2/css/lightbox.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/modules/print/css/printlinks.css?o7j4rc"); </style> <style type="text/css" media="all"> @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/themes/math/css/style.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/themes/math/css/ie.css?o7j4rc"); @import url("https://web.archive.org/web/20160521155639cs_/http://www.math.ias.edu/sites/all/themes/math/css/math.css?o7j4rc"); </style> <script src="/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/ckeditor/css/ckeditor.css"></script> </head> <body class="html not-front not-logged-in one-sidebar sidebar-second page-node page-node- page-node-497 node-type-page role-anonymous-user with-subnav page-csdm section-csdm role-anonymous-user with-subnav page-csdm section-csdm"> <div id="skip-link"> <a href="#content" class="element-invisible element-focusable">Jump to Navigation</a> </div> <div id="page" class="page with-navigation with-subnav with-navigation with-subnav">  <header class="header"> <a class="mobile-logo" href="https://web.archive.org/web/20160521155639/https://www.ias.edu/" title="Back to IAS" rel="home"> <h1>IAS School of Mathematics</h1> </a> <div class="mobile-menu-btn"> <span class="menu-btn"></span> </div> <span class="mobile-nav-bg"></span> <nav id="nav-bar" role="navigation" tabindex="-1"> <span class="mobile-page-overlay"></span> <div class="nav-wrapper"> <div class="nav-top cf"> <div id="block-menu-menu-utility-menu" class="block block-menu menu-utility block-odd first block-odd first"> <div class="block-inner"> <div class="block-content"> <div class="menu-wrapper lvl-1"><ul class="menu menu-lvl-1"><li class="first leaf"><a href="https://web.archive.org/web/20160521155639/https://www.ias.edu/campus-resources">Campus Resources</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/https://www.ias.edu/programs-outreach">Programs & Outreach</a></li> <li class="last leaf"><a href="https://web.archive.org/web/20160521155639/https://www.ias.edu/apply">Apply</a></li> </ul></div> </div> </div> </div> <div id="block-menu-menu-school-menu" class="block block-menu menu-school block-even last block-even last"> <div class="block-inner"> <div class="block-content"> <div class="menu-wrapper lvl-1"><ul class="menu menu-lvl-1"><li class="first leaf"><a href="https://web.archive.org/web/20160521155639/http://www.hs.ias.edu/">Historical Studies</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/" class="main active">Mathematics</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://www.sns.ias.edu/">Natural Sciences</a></li> <li class="last leaf"><a href="https://web.archive.org/web/20160521155639/http://www.sss.ias.edu/">Social Science</a></li> </ul></div> </div> </div> </div> </div> <div class="nav-bottom cf"> <a class="logo" href="/web/20160521155639/http://www.math.ias.edu/" title="Home" rel="home"> <h1>IAS School of Mathematics</h1> </a> <div class="menu-wrapper lvl-1"><ul class="menu menu-lvl-1"><li class="first leaf"><a href="/web/20160521155639/http://www.math.ias.edu/" title="Home">home</a></li> <li class="expanded active-trail"><a href="/web/20160521155639/http://www.math.ias.edu/activities" title="activities" class="active-trail">activities</a><a href="javascript:;" class="mobile-menu-toggle"></a><div class="menu-wrapper lvl-2"><ul class="menu menu-lvl-2"><li class="first leaf active-trail"><a href="/web/20160521155639/http://www.math.ias.edu/csdm" class="active-trail active">Computer Science and Discrete Mathematics (CSDM)</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/calendar" title="calendar of events">events calendar</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/seminars/weyl-lecture-series" title="Hermann Weyl Survey Lecture Series">Hermann Weyl Survey Lecture Series</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/seminars/morse-lecture-series" title="Marston Morse Lecture Series">Marston Morse Lecture Series</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/math-conversations">Mathematical Conversations</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://www.mathinstitutes.org/" title="">NSF Mathematics Institutes</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://pcmi.ias.edu/" title="">park city (pcmi)</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/seminars">seminars</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/special-years" title="special years">special years</a></li> <li class="last leaf"><a href="/web/20160521155639/http://www.math.ias.edu/wam" title="Women and Mathematics">Women and Mathematics</a></li> </ul></div></li> <li class="expanded"><a href="/web/20160521155639/http://www.math.ias.edu/administration/mission" title="">administration</a><a href="javascript:;" class="mobile-menu-toggle"></a><div class="menu-wrapper lvl-2"><ul class="menu menu-lvl-2"><li class="first leaf"><a href="/web/20160521155639/http://www.math.ias.edu/administration/contact-us">contact us</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/administration/mission">mission</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/administration/how-to-apply" title="How to Apply">how to apply</a></li> <li class="last leaf"><a href="/web/20160521155639/http://www.math.ias.edu/local-info" title="local information">local-info</a></li> </ul></div></li> <li class="expanded"><a href="/web/20160521155639/http://www.math.ias.edu/people">people</a><a href="javascript:;" class="mobile-menu-toggle"></a><div class="menu-wrapper lvl-2"><ul class="menu menu-lvl-2"><li class="first leaf"><a href="/web/20160521155639/http://www.math.ias.edu/people/faculty">faculty</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/people/members">members</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/people/short-term-visitors" title="short-term visitors">short-term visitors</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/people/staff">staff</a></li> <li class="last leaf"><a href="/web/20160521155639/http://www.math.ias.edu/people/students" title="students">students</a></li> </ul></div></li> <li class="expanded"><a href="/web/20160521155639/http://www.math.ias.edu/publications" title="publications">publications</a><a href="javascript:;" class="mobile-menu-toggle"></a><div class="menu-wrapper lvl-2"><ul class="menu menu-lvl-2"><li class="first leaf"><a href="https://web.archive.org/web/20160521155639/http://www.math.princeton.edu/~annals/index.html" title="Annals of Mathematics">Annals of Mathematics</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/qft" title="Lectures and problems on Quantum Field Theory">Lectures and problems on Quantum Field Theory</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://publications.ias.edu/deligne" title="Selected works of Pierre Deligne">Selected works of Pierre Deligne</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://publications.ias.edu/pg" title="Selected works of Philip Griffiths">Selected works of Philip Griffiths</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://publications.ias.edu/rpl" title="The work of Robert Langlands">The work of Robert Langlands</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://publications.ias.edu/sarnak" title="Selected works of Peter Sarnak">Selected works of Peter Sarnak</a></li> <li class="last leaf"><a href="https://web.archive.org/web/20160521155639/http://publications.ias.edu/selberg" title="Selected works of Atle Selberg">Selected works of Atle Selberg</a></li> </ul></div></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/https://video.ias.edu/sm" title="School of Mathematics video lectures">video lectures</a></li> <li class="expanded"><a href="/web/20160521155639/http://www.math.ias.edu/computing">services</a><a href="javascript:;" class="mobile-menu-toggle"></a><div class="menu-wrapper lvl-2"><ul class="menu menu-lvl-2"><li class="first leaf"><a href="/web/20160521155639/http://www.math.ias.edu/computing" title="Welcome">computing</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/https://mail.math.ias.edu/" title="webmail">email</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://library.ias.edu/mn/" title="">library</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://mail.math.ias.edu/kronolith" title="Kronolith">webcalendar</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/mathlinks" title="">math links</a></li> <li class="last leaf"><a href="https://web.archive.org/web/20160521155639/http://ttrade.tigerapps.org/" title="Princeton University Tiger Trade (Login using IAS CAS)">tiger trade</a></li> </ul></div></li> <li class="last leaf"><a href="https://web.archive.org/web/20160521155639/http://www.ias.edu/" title="Institute Home Page">IAS</a></li> </ul></div> <span class="show-search"></span> <div class="search-container"> <form action="/web/20160521155639/http://www.math.ias.edu/csdm" method="post" id="search-block-form--2" accept-charset="UTF-8"><div><div class="container-inline"> <h2 class="element-invisible">Search form</h2> <div class="form-item form-type-textfield form-item-search-block-form"> <label class="element-invisible" for="edit-search-block-form--4">Search </label> <input title="Enter the terms you wish to search for." type="text" id="edit-search-block-form--4" name="search_block_form" value="" size="15" maxlength="128" class="form-text"/> </div> <div class="form-actions form-wrapper" id="edit-actions--2"><input type="submit" id="edit-submit--2" name="op" value="Search" class="form-submit"/></div><input type="hidden" name="form_build_id" value="form-0YLBF4-M1X0ln7A4xntsLX1ldRjd8xIB9oEmbw3gECQ"/> <input type="hidden" name="form_id" value="search_block_form"/> </div> </div></form> </div> </div> </div> </nav> </header>  <div id="main"> <section id="content-top"> <div class="block-menu_block-1 block block-menu-block block-sub-menu lvl-2 block-odd first last block-odd first last cf"> <div class="block-inner cf"> <div class="menu-block-wrapper menu-block-1 menu-name-main-menu parent-mlid-0 menu-level-2"> <div class="menu-wrapper lvl-1"><ul class="menu menu-lvl-1"><li class="first leaf active-trail active menu-mlid-987"><a href="/web/20160521155639/http://www.math.ias.edu/csdm" class="active-trail active">Computer Science and Discrete Mathematics (CSDM)</a></li> <li class="leaf menu-mlid-1150"><a href="/web/20160521155639/http://www.math.ias.edu/calendar" title="calendar of events">events calendar</a></li> <li class="leaf menu-mlid-6932"><a href="/web/20160521155639/http://www.math.ias.edu/seminars/weyl-lecture-series" title="Hermann Weyl Survey Lecture Series">Hermann Weyl Survey Lecture Series</a></li> <li class="leaf menu-mlid-5042"><a href="/web/20160521155639/http://www.math.ias.edu/seminars/morse-lecture-series" title="Marston Morse Lecture Series">Marston Morse Lecture Series</a></li> <li class="leaf menu-mlid-6520"><a href="/web/20160521155639/http://www.math.ias.edu/math-conversations">Mathematical Conversations</a></li> <li class="leaf menu-mlid-190"><a href="https://web.archive.org/web/20160521155639/http://www.mathinstitutes.org/" title="">NSF Mathematics Institutes</a></li> <li class="leaf menu-mlid-188"><a href="https://web.archive.org/web/20160521155639/http://pcmi.ias.edu/" title="">park city (pcmi)</a></li> <li class="leaf menu-mlid-189"><a href="/web/20160521155639/http://www.math.ias.edu/seminars">seminars</a></li> <li class="leaf menu-mlid-465"><a href="/web/20160521155639/http://www.math.ias.edu/special-years" title="special years">special years</a></li> <li class="last leaf menu-mlid-4244"><a href="/web/20160521155639/http://www.math.ias.edu/wam" title="Women and Mathematics">Women and Mathematics</a></li> </ul></div></div> </div> </div> <div id="content-header"> </div>  </section> <section id="content"> <div class="content-wrapper l-row l-container cf"> <div id="content-area" class="node-content col-two-thirds p-left"> <h1 class="content-title">Theoretical Computer Science and Discrete Mathematics (CSDM)</h1> <div id="block-system-main" class="block block-system block-odd first last block-odd first last"> <div class="block-inner"> <div class="block-content"> <article id="node-497" class="cf node node-page node-odd page node-odd page"> <div class="cb-row cb-editor"> <span class="print-link"></span><div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even"><table style="text-align:center; width:100%"><tbody><tr><td><center><img alt="Abacus" src="/web/20160521155639im_/http://www.math.ias.edu/images/abacus.jpg" style="height:85px"/></center></td> <td><center><img alt="Analytical engine by Charles Babbage" src="/web/20160521155639im_/http://www.math.ias.edu/images/babbage.jpg" style="height:85px"/></center></td> <td><center><img alt="Turing Machine" src="/web/20160521155639im_/http://www.math.ias.edu/images/turing.gif" style="height:85px"/></center></td> </tr><tr><td><center>Abacus</center></td> <td><center>Analytical engine by Charles Babbage</center></td> <td><center>Turing Machine</center></td> </tr></tbody></table><p>聽</p> <table align="center" border="0" cellpadding="0" cellspacing="0" style="width:300px"><tbody><tr><td colspan="2" style="text-align:center">Sponsored by:</td> </tr><tr><td style="text-align:center"><a href="https://web.archive.org/web/20160521155639/http://www.nsf.gov/"><center><img alt="National Science Foundation" src="/web/20160521155639im_/http://www.math.ias.edu/images/nsf.gif" style="height:90px; margin:0px; padding:0px; width:90px"/></center><br/>National Science Foundation</a></td> <td style="text-align:center"><a href="https://web.archive.org/web/20160521155639/http://www.state.nj.us/"><center><img alt="State of New Jersey" src="/web/20160521155639im_/http://www.math.ias.edu/images/new_jersey.gif" style="height:90px; margin:0px; padding:0px; width:90px"/></center><br/>State of New Jersey</a></td> </tr></tbody></table><p>聽</p> <div>聽</div> <p>If you would like to learn about this program and our activities, follow one of these links or read the <a href="#background">background information</a>.</p> <ul><li><a href="/web/20160521155639/http://www.math.ias.edu/csdm/seminars">Theoretical Computer Science and Discrete Math Seminars</a></li> <li><a href="https://web.archive.org/web/20160521155639/https://www.math.ias.edu/csdm/current">Current Members</a></li> <li><a href="/web/20160521155639/http://www.math.ias.edu/csdm/postdocs">Postdoctoral Positions</a></li> <li>NSF Grants:<br/><a href="https://web.archive.org/web/20160521155639/https://www.math.ias.edu/node/30375">Theory of Computation - Pushing the State-of-the-Art</a></li> <li><a href="/web/20160521155639/http://www.math.ias.edu/csdm/nearby">Related near-by seminars</a></li> <li><a href="/web/20160521155639/http://www.math.ias.edu/csdm/links">Useful links</a></li> <li><a href="https://web.archive.org/web/20160521155639/https://www.math.ias.edu/avi60">October 2016 - A conference organized in honor of Avi Wigderson's 60th birthday</a></li> </ul><p>The CSDM program, which is in its 16th year, has two weekly seminars. The main purpose of this program is intensive research, often in cooperation with short-term visitors and local people from academic and research institutions such as聽 <a href="https://web.archive.org/web/20160521155639/http://www.cs.princeton.edu/">Princeton University</a>, <a href="https://web.archive.org/web/20160521155639/http://www.cs.rutgers.edu/">Rutgers University</a>, <a href="https://web.archive.org/web/20160521155639/http://dimacs.rutgers.edu/">DIMACS</a> or <a href="https://web.archive.org/web/20160521155639/http://www.research.att.com/">AT&T</a>.聽 For more information, check out the pages <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/seminars">Seminars</a> and <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/current">People</a>.</p> <p>Previous activities of the CSDM program can be found through the links listed in the sidebar to the right.</p> <hr/><p><a name="background" id="background"></a><strong>Background Information</strong><br/> 聽</p> <p><strong>General</strong></p> <p>Welcome to the home page of the special program in Theoretical Computer Science and Discrete Mathematics (<em>TCS/DM</em>).聽</p> <p>This field is one of the most vibrant and active areas of scientific study today.聽 Starting half a century ago, even before computers existed, theoretical computer scientists set out to define mathematically the concept of "computation", and to study its power and limits.聽 The theoretical discoveries of Alan Turing, John von Neumann (Institute faculty member, 1933-57) and their contemporaries led to the practical construction of the first stored program computer at the IAS, followed by the computer "revolution" we are witnessing today.聽</p> <p>The practical use of computers and, simultaneously, the unexpected mathematical depth of the abstract notion of "computation" have significantly altered and expanded theoretical computer science. 聽In the last quarter century it has turned into a rich and beautiful field, making connections to other areas and attracting talented young scientists.聽 More technical (but still popular) descriptions of various related aspects can be found in these brief essays:聽</p> <ul><li><em><a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/aspects">Some aspects of the evolution undergone by Theoretical Computer Science in the last quarter century</a>聽</em></li> <li><em><a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/relations">On relations between TCS and other sciences</a>聽</em></li> <li><em><a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/dm">Discrete Mathematics: Past, Present and Future</a>聽</em></li> </ul><p>as well as in the comprehensive article</p> <ul><li><a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/%7Eavi/PUBLICATIONS/MYPAPERS/W06/w06.pdf">P, NP and Mathematics - a computational complexity perspective </a></li> </ul><p>written by <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/%7Eavi">Avi Wigderson</a>聽for the Proceedings of the International Congress of Mathematicians in Madrid (2006).</p> <p>聽</p> <p><strong>TCS/DM at the Institute</strong></p> <p>The "parent" disciplines聽 from which Theoretical Computer Science and Discrete Mathematics evolved were once represented at the Institute by John von Neumann (1933-57) and Kurt Godel (1953-76).聽 After a considerable gap,聽 the School of Mathematics began to explore the possibility of re-opening this stream of research in the early 1990s with a well-received series of lectures given by <a href="https://web.archive.org/web/20160521155639/http://www.seas.harvard.edu/directory/rabin">Michael Rabin</a> and <a href="https://web.archive.org/web/20160521155639/https://www.eecs.berkeley.edu/Faculty/Homepages/karp.html">Richard Karp.</a>聽 The year 1993 marked the opening of a series of exploratory programs led by various leading researchers from all over the world.聽 In the same year the weekly seminar (now known as <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/seminars">Theoretical Computer Science and Discrete Math Seminar</a>) was established.聽</p> <p>The exploratory programs proved to be quite successful, both scientifically and educationally, and also were well-received by the mathematical community outside the Institute. 聽Thus, it was decided to go ahead, and in <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/97-98">1997-98</a> and <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/98-99">1998-99</a>, <a href="https://web.archive.org/web/20160521155639/http://www.math.tau.ac.il/%7Enogaa">Noga Alon</a> and <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/%7Eavi">Avi Wigderson</a> assumed the leadership of further programs in combinatorics and computational complexity.聽</p> <p>A commitment to the permanent presence of Theoretical Computer Science and Discrete Mathematics was made by appointing <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/%7Eavi">Avi Wigderson</a> to the newly created faculty position (1999).聽 This event also marks the formal beginning of the TCS/DM special program.聽</p> <p>Almost immediately (in the academic year of 2000-01) the Program was holding a <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/00-01/">Special Year on Computational Complexity</a> that attracted <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/00-01/members">well-known researchers in this field</a>.聽 As another part of the effort to get it established, <a href="https://web.archive.org/web/20160521155639/http://genesis.mi.ras.ru/%7Erazborov">Alexander Razborov</a> was appointed to be in residence as a senior member in 2001-2006.</p> <p>Previous activities can be found through the links listed in the sidebar above under <em>previous years.</em></p> <p>聽</p> <p><strong>Collaborations and Education</strong></p> <p>From its very beginning, the CSDM Program has been working in close collaboration with near-by academic establishments, as well as with industry research groups.聽 The list of our principal collaborators in particular includes:</p> <ul><li><a href="https://web.archive.org/web/20160521155639/http://dimacs.rutgers.edu/">Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)</a></li> <li><a href="https://web.archive.org/web/20160521155639/http://www.cs.princeton.edu/">Department of Computer Science at Princeton University</a></li> <li><a href="https://web.archive.org/web/20160521155639/http://www.cra.org/reports/labs/nec.html">NEC Research Institute</a></li> </ul><p>The Program puts a special stress on educational aspects. Under the auspices of <a href="https://web.archive.org/web/20160521155639/https://pcmi.ias.edu/">IAS/Park City Institute</a>, in the summer of 2000 <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/%7Eavi">Avi Wigderson </a>and <a href="https://web.archive.org/web/20160521155639/http://www.cs.cmu.edu/%7Erudich/">Steven Rudich</a>聽(Carnegie-Mellon) organized a Graduate Summer School in Computational Complexity.聽 Every year the Program seeks postdoctoral applications from graduating Ph.D.s in the areas of Theoretical Computer Science and Discrete Mathematics.</p> <ul><li><a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/postdocs">More information on Postdoctoral positions</a></li> </ul><p><em>Return to the <a href="https://web.archive.org/web/20160521155639/http://www.math.ias.edu/csdm/#top">top of this page</a></em></p> </div></div></div><ul class="links inline"><li class="print_html first last"><a href="/web/20160521155639/http://www.math.ias.edu/print/csdm" title="Display a printer-friendly version of this page." class="print-page" rel="nofollow">Printer-friendly version</a></li> </ul> </div> </article>  </div> </div> </div> </div> <aside id="sidebar-second" class="column sidebar second col-third"> <div class="sidebar-inner"> <div id="block-ias_math-upcoming-csdm-events" class="block block-ias-math block-odd first block-odd first"> <div class="block-inner"> <h2 class="block-title">Upcoming CSDM Events</h2> <div class="block-content"> <div class="ias_calendar_csdm_seminars_upcoming_block"><h3 class="ias-calendar-block-date">September 19, 2016</h3><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104124/1474298100/1474301700">CSDM I: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">11:15am-12:15pm</div><div class="ias-calendar-block-event-location">S-101</div></div><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104124/1474298100/1474301700">CSDM I: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">11:15am-12:15pm</div><div class="ias-calendar-block-event-location">S-101</div></div><h3 class="ias-calendar-block-date">September 20, 2016</h3><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104364/1474381800/1474389000">CSDM II: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">10:30am-12:30pm</div><div class="ias-calendar-block-event-location">S-101</div></div><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104364/1474381800/1474389000">CSDM II: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">10:30am-12:30pm</div><div class="ias-calendar-block-event-location">S-101</div></div><h3 class="ias-calendar-block-date">September 26, 2016</h3><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104134/1474902900/1474906500">CSDM I: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">11:15am-12:15pm</div><div class="ias-calendar-block-event-location">S-101</div></div><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104134/1474902900/1474906500">CSDM I: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">11:15am-12:15pm</div><div class="ias-calendar-block-event-location">S-101</div></div><h3 class="ias-calendar-block-date">September 27, 2016</h3><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104374/1474986600/1474993800">CSDM II: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">10:30am-12:30pm</div><div class="ias-calendar-block-event-location">S-101</div></div><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104374/1474986600/1474993800">CSDM II: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">10:30am-12:30pm</div><div class="ias-calendar-block-event-location">S-101</div></div><h3 class="ias-calendar-block-date">October 3, 2016</h3><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104144/1475507700/1475511300">CSDM I: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">11:15am-12:15pm</div><div class="ias-calendar-block-event-location">S-101</div></div><div class="ias_calendar_csdm_seminar"><div class="ias_calendar_csdm_seminar_topic"><strong><a href="/web/20160521155639/http://www.math.ias.edu/calendar/event/104144/1475507700/1475511300">CSDM I: To Be Announced</a></strong></div><div class="ias-calendar-block-event-speaker">To Be Announced</div><div class="ias-calendar-block-event-time">11:15am-12:15pm</div><div class="ias-calendar-block-event-location">S-101</div></div></div> </div> </div> </div> <div id="block-menu-menu-csdm" class="block block-menu block-even last block-even last"> <div class="block-inner"> <h2 class="block-title">Computer Science and Discrete Mathematics</h2> <div class="block-content"> <div class="menu-wrapper lvl-1"><ul class="menu menu-lvl-1"><li class="first leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm" title="" class="active">csdm home</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/current" title="current members">current members</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/seminars">current seminars</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/nearby" title="nearby seminars">nearby seminars</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://video.ias.edu/csdm" title="Link to Video site. ">video of lectures</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/pseudo2010" title="Workshop on Pseudo-randomness in Mathematical Structures">Pseudorandomness 2010</a></li> <li class="expanded active-trail"><a href="/web/20160521155639/http://www.math.ias.edu/csdm" title="about the program" class="active-trail active">about</a><a href="javascript:;" class="mobile-menu-toggle"></a><div class="menu-wrapper lvl-2"><ul class="menu menu-lvl-2"><li class="first leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/aspects">theoretical computer science</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/dm" title="Discrete Mathematics: past, present and future">discrete mathematics</a></li> <li class="last leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/relations" title="On relations between Theoretical Computer Science and the other sciences">relations</a></li> </ul></div></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/postdocs" title="postdoctoral positions">postdocs</a></li> <li class="expanded"><a href="/web/20160521155639/http://www.math.ias.edu/csdm" title="" class="active">previous years</a><a href="javascript:;" class="mobile-menu-toggle"></a><div class="menu-wrapper lvl-2"><ul class="menu menu-lvl-2"><li class="first collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/14-15">2014-2015</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/13-14" title="2013-2014">2013-2014</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/12-13" title="2012-2013">2012-2013</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/11-12">2011-2012</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/10-11">2010-2011</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/09-10">2009-2010</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/08-09">2008-2009</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/07-08">2007-2008</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/06-07">2006-2007</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/05-06">2005-2006</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/04-05">2004-2005</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/03-04">2003-2004</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/02-03">2002-2003</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/01-02">2001-2002</a></li> <li class="collapsed"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/00-01">2000-2001</a></li> <li class="leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/98-99">1998-1999</a></li> <li class="last leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/97-98">1997-1998</a></li> </ul></div></li> <li class="last leaf"><a href="/web/20160521155639/http://www.math.ias.edu/csdm/links">links</a></li> </ul></div> </div> </div> </div> </div> </aside>  </div>  </section>  </div>   <footer id="footer"> <div class="footer-bottom cf"> <div class="l-container"> <div id="block-menu-menu-footer-menu" class="block block-menu menu-footer cf block-odd first last block-odd first last"> <div class="block-inner"> <div class="block-content"> <div class="menu-wrapper lvl-1"><ul class="menu menu-lvl-1"><li class="first leaf"><a href="https://web.archive.org/web/20160521155639/https://www.ias.edu/privacy-policy">Privacy Policy</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/https://www.ias.edu/careers">Careers</a></li> <li class="last leaf"><a href="https://web.archive.org/web/20160521155639/https://www.ias.edu/press-center">Press Center</a></li> </ul></div> </div> </div> </div> </div> </div> <div class="footer-top l-container cf"> <div class="l-faux-table"> <div id="block-block-14" class="block block-block block-main-info col-third block-odd first block-odd first"> <div class="block-inner"> <div class="block-content"> <p><span style="font-size:10px">The School of Mathematics wishes to acknowledge and thank the following for their generous support of the School's programs each year:<br/> National Science Foundation</span></p> <p>1 Einstein Drive<br/> Princeton, New Jersey<br/> 08540 USA</p> <p>Phone <a href="https://web.archive.org/web/20160521155639/tel:609-734-8000">(609) 734-8100</a><br/> Email <a href="https://web.archive.org/web/20160521155639/mailto:math@mathias.edu">math@math.ias.edu</a><br/> Fax: 609-951-4459</p> </div> </div> </div> <div id="block-block-15" class="block block-block block-support col-third block-even last block-even last"> <div class="block-inner"> <h2 class="block-title">Support</h2> <div class="block-content"> <p>Help our scientists and scholars continue their field-shaping work.</p> <p><a class="btn border white" href="https://web.archive.org/web/20160521155639/https://www.ias.edu/iasfund">Give Now</a></p> </div> </div> </div> <div class="block block-footer-action col-third"> <div id="block-block-13" class="block block-block connect-block block-odd first block-odd first"> <div class="block-inner"> <h2 class="block-title">Connect</h2> <div class="block-content"> <p><a class="btn border white" href="https://web.archive.org/web/20160521155639/https://www.ias.edu/ias-enews-subscription">eNews Signup</a></p> </div> </div> </div> <div id="block-menu-menu-footer-social-menu" class="block block-menu menu-socials block-even last block-even last"> <div class="block-inner"> <div class="block-content"> <div class="menu-wrapper lvl-1"><ul class="menu menu-lvl-1"><li class="first leaf"><a href="https://web.archive.org/web/20160521155639/https://twitter.com/iasmathhelp" class="icon-twitter" target="_blank" title="">Twitter</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/https://www.facebook.com/InstituteforAdvancedStudy" class="icon-social-facebook" target="_blank">Facebook</a></li> <li class="leaf"><a href="https://web.archive.org/web/20160521155639/http://www.youtube.com/videosfromIAS" class="icon-youtube-square" target="_blank">YouTube</a></li> <li class="last leaf"><a href="https://web.archive.org/web/20160521155639/https://www.instagram.com/institute_for_advanced_study" class="icon-instagram" target="_blank">Instagram</a></li> </ul></div> </div> </div> </div> </div> </div> <div class="copyright">Copyright © 2016 Institute for Advanced Study</div> </div> </footer> </div>  <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/picture/picturefill2/picturefill.min.js?v=2.3.1"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/picture/picture.min.js?v=7.43"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/lightbox2/js/lightbox.js?1463838719"></script> <div id="js-mediaquery-reference"></div> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/jquery_update/replace/jquery/1.10/jquery.min.js?v=1.10.2"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/misc/jquery.once.js?v=1.2"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/misc/drupal.js?o7j4rc"></script> <script type="text/javascript"> <![CDATA[//><!]]> </script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/ias_calendar/upcoming_events_block.js?o7j4rc"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/libraries/dateformat/date.format.js?o7j4rc"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/mathjax/mathjax.js?o7j4rc"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/modules/google_analytics/googleanalytics.js?o7j4rc"></script> <script type="text/javascript"> <![CDATA[//><!]]> </script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/themes/ias/js/vendor/modernizr.min.js?o7j4rc"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/themes/ias/js/vendor/plugins.min.js?o7j4rc"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/themes/ias/js/scripts.js?o7j4rc"></script> <script type="text/javascript" src="https://web.archive.org/web/20160521155639js_/http://www.math.ias.edu/sites/all/themes/math/math_custom/math-script.js?o7j4rc"></script> <script type="text/javascript"> <![CDATA[//><!]]> </script> </body> </html>