tag:blogger.com,1999:blog-3722233.post7359275432536426939..comments2023-10-04T18:19:45.646-05:00Comments on Computational Complexity: Teaching PCPs to UndergradsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-50771665018898715492011-10-20T22:19:02.450-05:002011-10-20T22:19:02.450-05:00I once did a similar lecture many years ago for my...I once did a similar lecture many years ago for my mathematics department's undergraduate colloquium (50 minutes). Discussed the NP completeness of approximation for SAT, and related it to proof checking. No proofs of course! I did not relate it to other problems like Clique or Vertex Cover though.<br /><br />This was back when I still used handwritten slides. I doubt I still have them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18562847503185228202011-10-19T21:28:30.188-05:002011-10-19T21:28:30.188-05:00Whats all this about Taking PCPs with undergraduat...Whats all this about Taking PCPs with undergraduates. Isn't the drug problem bad enough<br />without us adding to it. OH, you mean<br />Prob. Checkable Proofs! That's entirely different!<br />Never Mind.<br /><br />Emily LitellaAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76233131462026698682011-10-18T16:39:29.081-05:002011-10-18T16:39:29.081-05:00The assignment is the proof you can check with thr...The assignment is the proof you can check with three queries by picking a random clause. I briefly mention this in class but it's the application to approximation that is more important.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11148734518446825072011-10-18T15:01:48.434-05:002011-10-18T15:01:48.434-05:00Lance, do you explain what the above statement has...Lance, do you explain what the above statement has to do with the checking of proofs? (I'm assuming you tell your students what PCP stands for.)<br /><br />Amit CAChttps://www.blogger.com/profile/14911233583375020356noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77031195967666990982011-10-17T18:51:22.933-05:002011-10-17T18:51:22.933-05:00In all seriousness: would it really not be possibl...In all seriousness: would it <em>really</em> not be possible to give the proof in a graduate seminar? Assuming the students had taken a graduate complexity class beforehand, I think covering the proof, in full detail, could be done in < 10 1-hour lectures. <br /><br />Moreover, there have already been several classes devoted to the PCP theorem. =)Anonymousnoreply@blogger.com