tag:blogger.com,1999:blog-786333285568106173.post2360758504040554845..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Being Rich (I)Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-786333285568106173.post-6666459441663599192009-09-10T16:52:48.119-04:002009-09-10T16:52:48.119-04:00"Without disparaging this great paper, I must..."Without disparaging this great paper, I must say that the presentation is awful. ... (potentially, we may finally understand communication inside a marriage!). ... "<br /><br />Mihai, please tell me that the above text wasn't a referee comment that Miltersen received.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-25603769707811659332009-08-14T12:29:02.470-04:002009-08-14T12:29:02.470-04:00Awesomeness! I have to admit that before reading t...Awesomeness! I have to admit that before reading this MNSW 95 seemed to me a little hard to crack. <br />Thanks for the intuition your post is offering!дед морозnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-23408391070803363892008-05-26T13:05:00.000-04:002008-05-26T13:05:00.000-04:00Suresh, As Sudipto also said, the big application ...Suresh, <BR/><BR/>As Sudipto also said, the big application of asymmetric communication complexity is data structures, not streaming. I will explain in the next post why symmetric communication is useless for data structures.<BR/><BR/>[MNSW] also had some applications to "depth hierarchies for monotone AC0." But I think monotone AC0 is too "pathological" for most of us.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-78313578240134958382008-05-26T12:53:00.000-04:002008-05-26T12:53:00.000-04:00Anon, thank you for the suggestions. I implemented...Anon, thank you for the suggestions. I implemented them in the text (with a few exceptions).<BR/><BR/>I maintain that an Easter European high school student can follow this (with pencil and paper, sure). I'll ask some people in this class to see what they think :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-44192997331585783072008-05-25T14:21:00.000-04:002008-05-25T14:21:00.000-04:00Suresh, asymmetry has two components, the order in...Suresh, asymmetry has two components, the order in which the players speak and the number of bits each can speak. The former is used in streaming all over the place. However most reductions in streaming use reduction where all players have the same memory footprint, or otherwise speak the same number of bits. So you probably asked for the latter.<BR/><BR/>The latter (the restriction of bits spoken by each player) is best suited when the sides are unequal - say when we are ineracting with a data structure (as was the historical and more recent reason for the study of richness).<BR/>Other than data strucutures, even in streaming, maybe there is a result possible that "to solve problen X, and guaranteeing per input processing time y, we would need Z bits of space whereas X has a better algorithm which uses less than Z bits but <BR/>may take more time than y on a few inputs (and takes less amortized time, to make things interesting)". This really would be a <BR/>lower bound for updateable data strucutres, but at some point the distinctions are blurry.<BR/>sudipto.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-47626059397772687342008-05-25T04:05:00.000-04:002008-05-25T04:05:00.000-04:00Why is asymmetric CC interesting, apart from provi...Why is asymmetric CC interesting, apart from providing a higher-powered lens for the "asymmetric" case of Alice and Bob communication. For example, if we take streaming problems, where CC lower bounds are often used, is there any example of a problem that uses asymmetric CC in a nontrivial way ?Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-59826213810171702332008-05-24T17:53:00.000-04:002008-05-24T17:53:00.000-04:00Quite a good introduction to communication complex...Quite a good introduction to communication complexity. However, I do not think a highschool student would be able to digest all the material (well, maybe if (s)he spends several hours on it), because of the "mathematical maturity" needed.<BR/><BR/>I do have some suggestions:<BR/>- "... is [U,V]-rich if at least V columns have at least U one-entries" would be way clearer stated as "it contains at least V columns, each of which has at least U one-entries.".<BR/><BR/>- "a column of the truth table is a set T of, say, m=u/2 elements from the universe [u]" -- remind the reader m = \Theta(u) and thus you can have m \approx (u/k) for some constant k (and you suppose k=2 for brevity). Also, I think you should say "subset", not "set", because a column may represent a set of less than m elements.<BR/><BR/>- explicitly say choose has a lower priority of /, thus u/2 choose k is (u/2) choose k, not u/(2 choose k).<BR/><BR/>- when you say "Then (2) becomes (u/(2|S'|))^n < 2a", you mean "2^a" there.<BR/><BR/>- explain why the maximal size is (S' choose n) by (T' choose m=u/2).<BR/><BR/>- technically (A choose C)/(B choose C) >= (A/B)^C :D, not > (ok, ok, don't get too mad over this nitpicking)<BR/><BR/>- you should explain the last two implications, for those for whom calculus is not their mother tongue ;-)<BR/><BR/>That said, I think the presentation is very good and readable, even though to get through the last part I had to pull out the computer scientist's best tools: pen and paper.Anonymousnoreply@blogger.com