{"id":329,"date":"2008-05-27T19:17:26","date_gmt":"2008-05-27T23:17:26","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=329"},"modified":"2008-05-27T19:17:26","modified_gmt":"2008-05-27T23:17:26","slug":"great-ideas-in-theoretical-computer-science-lectures-16-19","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=329","title":{"rendered":"Great Ideas in Theoretical Computer Science Lectures 16-19"},"content":{"rendered":"<p>In the next-to-last GITCS installment, we cover some of the greatest hits of the 70&#8217;s and 80&#8217;s.<\/p>\n<ul>\n<li><a href=\"http:\/\/stellar.mit.edu\/S\/course\/6\/sp08\/6.080\/courseMaterial\/topics\/topic1\/lectureNotes\/lec161\/lec16.pdf\">Lecture 16<\/a>: Private-Key Cryptography<\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/stellar.mit.edu\/S\/course\/6\/sp08\/6.080\/courseMaterial\/topics\/topic1\/lectureNotes\/lec171\/lec17.pdf\">Lecture 17<\/a>: Public-Key Cryptography<\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/stellar.mit.edu\/S\/course\/6\/sp08\/6.080\/courseMaterial\/topics\/topic1\/lectureNotes\/lec181\/lec18.pdf\">Lecture 18<\/a>: Cryptographic Protocols <em>(including: how computer scientists date!)<\/em><\/li>\n<\/ul>\n<ul>\n<li><a href=\"http:\/\/stellar.mit.edu\/S\/course\/6\/sp08\/6.080\/courseMaterial\/topics\/topic1\/lectureNotes\/lec19\/lec19.pdf\">Lecture 19<\/a>: Interactive Proofs \/ Machine Learning<\/li>\n<\/ul>\n<p>(Something tells me Lecture 18 is going to get more hits than the other three combined&#8230;)<\/p>\n<p>The course itself ended two weeks ago; last week was the final exam. Thanks so much to all of my students for signing up for a brand-new course, asking probing questions, enduring my excruciating jokes, and doing a fantastic job with the notes.   (Of course, thanks also to my eagle-eyed readers for spotting errors.)  Thanks above all to my TA, Yinmeng Zhang, who went way beyond her job description to work with students individually, tell me when I was being a doofus, etc.  Because of the input of everyone who participated, this course will be better when I teach it the second time around.<\/p>\n<p>Also, for anyone who might want to teach a similar course, the recipe is simple (much simpler than I expected, actually):<\/p>\n<ol>\n<li>Start with a standard, off-the-shelf, undergraduate computability and complexity theory course.<\/li>\n<li>Cut out the most boring parts, like pushdown automata, context-free grammars, and 10<sup>5000<\/sup> NP-completeness reductions.  (Yes, I know these things <em>can<\/em> be taught in a non-boring way, but why make it hard on yourself?)<\/li>\n<li>Fill in the gaps with more interesting material, like zero-knowledge proofs, computational learning theory, or quantum computing.<\/li>\n<li>Add a pinch (to taste) of mindblowing results that can&#8217;t be covered in detail, like the PCP Theorem, the independence of the Continuum Hypothesis, or cosmological limits on computation.<\/li>\n<\/ol>\n<p>Serves 10-100.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the next-to-last GITCS installment, we cover some of the greatest hits of the 70&#8217;s and 80&#8217;s. Lecture 16: Private-Key Cryptography Lecture 17: Public-Key Cryptography Lecture 18: Cryptographic Protocols (including: how computer scientists date!) Lecture 19: Interactive Proofs \/ Machine Learning (Something tells me Lecture 18 is going to get more hits than the other [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[5,27],"tags":[],"class_list":["post-329","post","type-post","status-publish","format-standard","hentry","category-complexity","category-gitcs"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/329","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=329"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/329\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=329"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=329"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=329"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}