tag:blogger.com,1999:blog-3722233.post5005316513630350871..comments2024-07-19T08:15:14.879-05:00Comments on Computational Complexity: What to teach in grad course in Comm Comp- some non-theorists in itLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-46780136497800968702008-08-29T18:47:00.000-05:002008-08-29T18:47:00.000-05:00Bill,Great comments--I especially like Nisan's cou...Bill,<BR/><BR/>Great comments--I especially like Nisan's course outline--so very little to add, other than this is a great course to teach!<BR/><BR/>One small comment: VLSI was NOT the origin of cc. It was an application of the theory.<BR/>The first paper was one by Abelson (FOCS 1978)--probably inspired somewhat by Minsky's comments on "Global vs. local in computation" and perhaps by Gentleman's work on distributed algorithms for Numerical Linear Algebra problems. Yao's paper was next: applications to VLSI followed.CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84495650611139608712008-08-28T13:46:00.000-05:002008-08-28T13:46:00.000-05:00THANKS for all of your advice,and THANKS to MiP-- ...THANKS for all of your advice,<BR/>and THANKS to MiP-- I<BR/>will look up some of the<BR/>references you point to,<BR/>including your own work.<BR/><BR/>bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45391889085666794982008-08-27T02:33:00.000-05:002008-08-27T02:33:00.000-05:00It's fun to suggest what someone else should teach...It's fun to suggest what someone else should teach, so here's my 2-cents...<BR/><BR/>In a theory course for non-theoreticians I prefer to concentrate on concepts, applications, and basic techniques, and avoid proofs with technical difficulty. In CC this can be done nicely I think:<BR/><BR/>(1) inside the CC model: several LB tecniques (I see no reason to leave out the easy rank LB), nondeterminism, randomness, and as you suggest the analogs of P!=NP, P!=RP, P=NP^coNP. <BR/><BR/>(2) applications:<BR/>a) Time-space for Turing-Machines <BR/>b) VLSI [using best-partition CC model]<BR/>c) streaming/sketching [using 1-way/simultaneous CC]<BR/>d) data structures [using asymmetric CC, and the "richness technique" rather than the hard round-eliminaion one, following the "modern" approach of Mihai.<BR/>e)My personal bias: economic applicaion for combinatorial auctions and relation to prices [a very easy writeup is in http://www.cs.huji.ac.il/~noam/NisanSegalExpo.ps]<BR/><BR/>I would give up both Karchmer-Wigderson and multiparty models due to the tecnical hardness of getting interesting results there. I think that the randomized LB for DISJ can be completely skipped this way, and if its wanted/needed then the sqrt(n) LB of BFS which is easy can be given.<BR/><BR/>I believe that this would give a very rich course without a single proof that has more than a single technical step in it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6452311494778544412008-08-27T01:10:00.000-05:002008-08-27T01:10:00.000-05:00Communication complexity is a tool, a bit like cal...Communication complexity is a tool, a bit like calculus; so it's important to illustrate its applications in a variety of contexts:<BR/><BR/>() VLSI<BR/>() Karchmer-Wigderson theorem (at least the easy direction, which makes cc a tool to show circuit depth lower bounds, one of the most important questions in complexity)<BR/>() data structure lower bounds<BR/>() data stream algorithm lower bounds<BR/><BR/>As for the fundamentals of cc:<BR/><BR/>() "the fundamental theorem of cc", the set of all input pairs that have the same transcript form a combinatorial rectangle (both proofs)<BR/><BR/>() fooling set<BR/><BR/>() rank method (this is just so pretty and low mess)<BR/><BR/>() I wouldn't mention "nondeterministic cc" but will include zero-covers and one-covers, and the theorem that Dcc(f) <= N0(f) N1(f) [if memory serves me right]<BR/><BR/>() Randomized CC is interesting only to the extent that it yields surprising upper bounds; randomized cc lower bounds are motivated by data stream algorithm problems (more on this later in the list).<BR/><BR/>() One-way and simultaneous models (these correspond loosely to streaming and sketching algorithms)<BR/><BR/>() The equivalence of public and private coin protocols (Newman's theorem) except in the simultaneous model (EQUALITY being the counterexample - simple proof due to Babai and Kimmel)<BR/><BR/>() Yao's minimax principle (if they haven't seen it elsewhere, this is a good opportunity to show at least the easy direction of this), and the equivalence of randomized and distributional cc -- randomized one-way cc lower bound for the indexing problem<BR/><BR/>() The notion of a reduction in cc lower bounds, and a lower bound, via reduction from indexing, for the problem of distinguishing Hamming distance < n/2 from Hamming distance > n/2 + sqrt(n) [this yields a nice 1/epsilon^2 lower bound for epsilon-approximation of the number of distinct elements in a data stream]<BR/><BR/>() Patrascu's lower bound on asymmetric set disjointness (detereministic version only - the randomized version is messy and doesn't add any intuitive value, esp. to non-theorists)<BR/><BR/>() Schulman's theorem on coding for communication (a stretch topic)<BR/><BR/>() Mention frontiers of the field: the work of Pranab Sen, Jaikumar Radhakrishnan, Rahul Jain, et al. on "message compression" as a form of producing "informationally-optimal protocols" (a form of Shannon's source-coding theorem for communication complexity, in my imprecise and intuitive way of thinking)<BR/><BR/>Some of the classics that I would leave out, but only because they are not that important to a general audience:<BR/>-- the result of Kalyanasundaram-Schnitger on the randomized cc of set disjointness<BR/>-- the discrepancy lower bound for inner product<BR/>-- Number-on-the-Forehead, Number-on-the-Rear, etc., including recent breakthroughs and connections to pseudorandom generatorsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35183158079388751042008-08-26T23:32:00.000-05:002008-08-26T23:32:00.000-05:00I would encourage you to explicitly devote a porti...I would encourage you to explicitly devote a portion of the class to a more "information theoretic" view of the world. Shannon theory and entropy are the foundation of what most of the "rest of the world" thinks about when they hear about communication complexity, and there are certainly connections (explicit and implicit) between that view of the subject and ours that would be worth covering -- particularly if there are non-theorists in the audience, who are arguably more likely to see that side of the subject in the future.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26449092813651595062008-08-26T19:47:00.000-05:002008-08-26T19:47:00.000-05:00Lucky you, getting to teach such a lovely topic!Fo...Lucky you, getting to teach such a lovely topic!<BR/><BR/>For the audience you describe, I would emphasize applications and leave out topics for which you can't get to applications within the course (e.g., nondeterministic communication). I would also definitely do the rank lower bound, which is just too cool to omit. Side note: non-theorists tend to relate better to the concept of "rank" than anything combinatorial like "fooling set".<BR/><BR/>It would be nice to get to the information theoretic methods that have arisen since Kushilevitz-Nisan (yes, my personal bias is showing)... it will take a little background-building, but it does give you the most intuitive proof of the randomized DISJOINTNESS lower bound, plus various round elimination lemmas.<BR/><BR/>-- Amit CAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78742455003391448782008-08-26T16:43:00.000-05:002008-08-26T16:43:00.000-05:00Hmm, Miltersen's survey is rather dated now, and t...Hmm, Miltersen's survey is rather dated now, and the bounds that you get by that old round elimination lemma are not very nice.<BR/><BR/>With the obvious personal bias, I think that if you want to teach a single topic at the intersection of cell probe and communication complexity, it should be my (Data) Structures paper. There are no complicated technical details, and the results are for very interesting problems (in the cell-probe world).<BR/><BR/>If you want round elimination, you can presumably teach the better version of Sen and Venkatesh [JCSS'08]. Or better yet, I have a self-contained and very clean proof (via deterministic round elimination). That will show up shortly in my PhD thesis.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19311227778959938522008-08-26T15:47:00.000-05:002008-08-26T15:47:00.000-05:00The rank lower bound takes almost no time to prove...The rank lower bound takes almost no time to prove and implies the fooling set lower bounds (which makes a nice guided exercise). Why would you skip it? <BR/><BR/>The biggest question if you are going to deal with the applications to MATCHING and streaming is that you will have to confront Set Disjointness for randomized algorithms. How you deal with that seems to be the biggest question. Do you just state the lower bound without proof? If you go through a proof, which one do you give? All the proofs have some significant subtlety that would be tough for this audience.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21946158367196837902008-08-26T15:25:00.000-05:002008-08-26T15:25:00.000-05:00Hope to do lower bound oncell probe model for PRED...Hope to do lower bound on<BR/>cell probe model for PRED<BR/>problem, the loglog n<BR/>lower bound. Will work out<BR/>of Peter Bro Miltersen's<BR/>survey and paper by<BR/>Miltersen, Nisan, Safra,<BR/>Wigderson. Not sure I'll<BR/>get that far.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47902639987295027722008-08-26T14:39:00.000-05:002008-08-26T14:39:00.000-05:00Just curious, what are you going to do in the asym...Just curious, what are you going to do in the asymmetric communication / cell-probe regime?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53084022482142642792008-08-26T14:38:00.000-05:002008-08-26T14:38:00.000-05:0015:20 ratio: Pardon, Imean 15 OUT OF 20 of thestud...15:20 ratio: Pardon, I<BR/>mean 15 OUT OF 20 of the<BR/>students are non-theorists.<BR/>15 NON theorists,<BR/>5 theorists.<BR/><BR/>And YES, I agree that<BR/>applications to data structures and VLSI are good. Also VLSI was the origin of the subject.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63333358096109758362008-08-26T13:49:00.000-05:002008-08-26T13:49:00.000-05:00I think it is important to motivate communication ...I think it is important to motivate communication complexity to non-theorists via some applications. Natural lower bound questions such as for data structures, VLSO and streaming algorithms are ideal. There are several neat results to pick from.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10106350549948731522008-08-26T13:36:00.000-05:002008-08-26T13:36:00.000-05:00How is a 15:20 nontheorist-to-theorist ratio "most...How is a 15:20 nontheorist-to-theorist ratio "mostly non-theorists"? Is there some kind of weighting factor that I missed?Anonymousnoreply@blogger.com