tag:blogger.com,1999:blog-3722233.post6443988696551418549..comments2023-02-01T09:07:35.326-06:00Comments on Computational Complexity: Topics for theory grad course for non theorists?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-75304772571722002172008-07-19T13:32:00.000-05:002008-07-19T13:32:00.000-05:00I have been reading "The Lady Tasting Tea". http:...I have been reading "The Lady Tasting Tea". <BR/>http://www.amazon.com/Lady-Tasting-Tea-Statistics-Revolutionized/dp/0805071342<BR/><BR/>It has some good statistics stuff in it. Its more reading.. but is a great launching point for what is possible to present.mathdadhttps://www.blogger.com/profile/12445433981878357601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5161987251590167632008-07-18T12:45:00.000-05:002008-07-18T12:45:00.000-05:00You should have at least one example showing why r...You should have at least one example showing why randomized processes are more powerful than deterministic ones, a little bit of the first moment method would be good tooAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86575489511609735982008-07-18T10:09:00.000-05:002008-07-18T10:09:00.000-05:00My own perspective on science and technology is co...My own perspective on science and technology is conditioned on Jonathan Israel's two-volume (so far) history of the eighteenth century Enlightenment, and also by the early history of the Royal Society ... both can be read as essays on the power of mathematics, science, and engineering for catalyzing federative activities. <BR/><BR/>It seems to me that similar federative themes are emerging as being of central importance in this, the twenty-first century.<BR/><BR/>A survey of CS theory organized around the theme "sharing" might cover two or three fundamental theorems from each of the following topics: (1) cryptography (shared secrets), (2) error-correcting codes (shared information), (3) model order reduction (shared descriptors), (4) efficient simulation (shared confidence), (5) game theory (shared benefit), (6) imaging (shared vision), and (7) QIT (shared quantum entanglement!).<BR/><BR/>The pedagogic advantage of this federative perspective is that it naturally unites CS skill-sets that are hugely in-demand by employers with theorems from among the trendiest topics in theoretical CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91565720559270961722008-07-18T06:07:00.000-05:002008-07-18T06:07:00.000-05:00If theory also encompasses the theory of programmi...If theory also encompasses the theory of programming languages, as I think it should, then you could teach about language expressivity: in addition to the aforementioned impossibility of consensus, I recommend to introduce Palamidessi's impossibility results on encoding mixed choice in asynchronous pi-calculus, and some of the game- and pi-calculus based full-abstraction results for sequential languages.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77880879340164023752008-07-17T21:49:00.000-05:002008-07-17T21:49:00.000-05:00Shannon's theorems (or is that the bailiwick of an...Shannon's theorems (or is that the bailiwick of another part of the department?)<BR/><BR/>PCP and some of the related inapproximability results (these might be doable, since you're not emphasizing proofs).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86559169532335565042008-07-17T18:44:00.000-05:002008-07-17T18:44:00.000-05:00We also have an algorithms course using CLRS. So t...We also have an algorithms course using CLRS. So this course should cover CS theory, broadly defined, minus what is in CLRS. <BR/><BR/>Kirk PruhsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87706954667050216302008-07-17T17:50:00.000-05:002008-07-17T17:50:00.000-05:00Pardon my unfamiliarity with CS lingo, but what ar...Pardon my unfamiliarity with CS lingo, but what are the differences betweens a formal proof and a mathematical proof? Aren't logic and TCS branches of mathematics?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27091938442953966192008-07-17T14:45:00.000-05:002008-07-17T14:45:00.000-05:00Anonymous recommends: LP and geometric view of opt...Anonymous recommends: <I>LP and geometric view of optimization including Ellipsoid method and its consequences.</I><BR/><BR/>This is a good idea IMHO. And then build upon it with a geometric survey of compressive sampling and sparse reconstruction methods, including (e.g.) RIP sampling matrices.<BR/><BR/>Then build further with geometric descriptions of model order reduction, iterative methods for solving large system of equations ... <BR/><BR/>The result would be a course focussed upon the theme of geometric methods in CS ... <BR/><BR/>Has any reader ever taught or taken such a course? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42428752454059280252008-07-17T11:25:00.000-05:002008-07-17T11:25:00.000-05:00LP and geometric view ofoptimization including Ell...LP and geometric view of<BR/>optimization including Ellipsoid method and its consequences. Formal proofs are not necessary but the ideas are easy to convey. <BR/><BR/>One or two classes on parallel algorithms and complexity? Seems like an apt topic these days.<BR/><BR/>A class on expanders? Show existence via probabilistic method.<BR/>Explain one or two applications, perhaps to P2P.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87364877007739179062008-07-17T11:13:00.000-05:002008-07-17T11:13:00.000-05:00Why just "complexity"? If this is "the" theory gr...Why just "complexity"? If this is "the" theory grad course (for non-theorists), shouldn't you cover some algorithms as well?<BR/><BR/>It might take two classes, but I'd suggest (at least one direction) of Shannon's theorem. Besides being an important result, it fits Jeff's criterion of covering an important proof technique (the probabilistic method), as well as some cool combinatorics. <BR/><BR/>Reed-Solomon codes.<BR/><BR/>Spend a day on Bloom filters. It's embarassing that they continue to escape our undergraduate textbooks; make sure your graduate students know them. (Concept: Hashing is good, very very good.)<BR/><BR/>I somehow always found IP=PSPACE to be a fundamentally compelling complexity result that also fits both the concepts/formal proof goal.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45795500945767156932008-07-17T10:45:00.000-05:002008-07-17T10:45:00.000-05:00Shouldn't any computer science graduate student be...<I>Shouldn't any computer science graduate student be comfortable with formal proofs?</I><BR/><BR/>Shouldn't any high school graduate be comfortable with formal proofs?<BR/><BR/>Of course, I guess it depends on what you mean by "comfortable". <BR/><BR/>The ability to write non-trivial formal proofs comes from high IQ. There's little to teach here.<BR/><BR/>But anyone can understand the concept of formal proofs and write simple ones. High school graduates should already have such skills.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41235811654255925602008-07-17T09:47:00.000-05:002008-07-17T09:47:00.000-05:00"I want to emphasize concepts and broad knowledge,..."I want to emphasize concepts and broad knowledge, not formal proofs or training students to do formal proofs."<BR/><BR/>Why? Are "concepts and broad knowledge" inconsistent with "formal proofs"? Shouldn't any computer science graduate student be comfortable with formal proofs? A course that covers a few important proof techniques (ie, ways of thinking) in depth seems much more interesting and useful than a laundry list of Very Important Results.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5356681929331166172008-07-17T08:47:00.000-05:002008-07-17T08:47:00.000-05:001) Public Key Crypto and Diffie Helman Key Exhange...1) Public Key Crypto and Diffie Helman Key Exhange.<BR/>Maybe do a mini history-of-crypto so that they see this solves a 2000 year old open problem.<BR/><BR/>2) The book THE TURING OMNIBUS has many topics that<BR/>may be good.<BR/><BR/>3) Communication Complexity results:<BR/>EQ requires n+1 bits deterministically, but can do with O(log n) if<BR/>allow rand and prob of error \le 1/n.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.com