tag:blogger.com,1999:blog-786333285568106173.post6664611227764774383..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: Introducing TCS?Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-786333285568106173.post-37285642131452906642008-02-13T18:55:00.000-05:002008-02-13T18:55:00.000-05:00Hi folks, Just a clarification, in case someone w...Hi folks,<BR/><BR/> Just a clarification, in case someone will still read the last few comments: the (very neat) FOCS'07 "Smooth Histograms" paper addresses the "sliding window" model, where at any time, the output depends only on the last n elements in the stream. In contrast, our STOC'05 paper addresses the model where the output depends on the whole stream, and the stream is allowed to contain deletions. The two models are incomparable in general. <BR/><BR/>Cheers,Piotrhttps://www.blogger.com/profile/13283386044289655376noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-68373077403808704262008-02-07T05:57:00.000-05:002008-02-07T05:57:00.000-05:00Read "nifty" as "nasty" in my last post.OmkantRead "nifty" as "nasty" in my last post.<BR/><BR/>OmkantAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-84044471397514444052008-02-07T05:52:00.000-05:002008-02-07T05:52:00.000-05:00Hi Mihai,Just a note: in the norm estimation strea...Hi Mihai,<BR/><BR/>Just a note: in the norm estimation stream, the latest paper actually is --<BR/><BR/>"Smooth Histograms"<BR/>Vladimir Braverman, Rafi Ostrovsky.<BR/>FOCS 2007<BR/><BR/>It has a pretty interesting approach, and also improves the Indyk-Woodruff result.<BR/><BR/>PCPs could have been another interesting topic, but selecting what to talk about from that area would have been a challenging task, I reckon.<BR/><BR/>Given that I work in Cryptography, I can't stop myself from commening on the ZK stuff: You need to know a bit more about ZK. Recently Avi Wigderson presented a funtastic sereis of 3 lectures at UCLA, one of which included a significant part on ZK. The audience was simply amazed, and I got the impression that they truly enjoyed it (there was so much curiosity -- and there were no nifty tricks to explain!).<BR/><BR/>The audience was very much comparable to the one you had -- a lot of UCLA Math department faculty (inclduing Terrence Tao :) ), a good amount of CS Faculty from other areas, and a several students.<BR/><BR/>OmkantAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-16855353792576228652008-02-07T03:08:00.000-05:002008-02-07T03:08:00.000-05:00Primes in P might have exciting and new.Primes in P might have exciting and new.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-15515342574303881472008-02-06T06:32:00.000-05:002008-02-06T06:32:00.000-05:00Maybe you could have tried something more colorful...<I>Maybe you could have tried something more colorful like zero knowledge proofs for NP.</I><BR/><BR/>To the contrary, this would've been a disaster. You suggest telling CS people something like "we have this really nifty tricks which are really cool if you love theory, but there's not particular way in which they will affect what you do."<BR/><BR/>I was looking for stuff with real applications. Everybody was enthusiastic about the relation between SQL enginges and norm estimation. It is a clean theoretical problem which does something for the real world.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-42684207635053392602008-02-05T23:31:00.000-05:002008-02-05T23:31:00.000-05:00Maybe you could have tried something more colorful...Maybe you could have tried something more colorful like zero knowledge proofs for NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-80401445759995679782008-02-05T13:15:00.000-05:002008-02-05T13:15:00.000-05:00Indeed, I was not too clear on the level of the pa...Indeed, I was not too clear on the level of the participants. The all know CS kind of stuff, like NP-completeness, shortest paths etc. The goal was to teach them that TCS did something nontrivial in the last 20 years :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-45188612304871062192008-02-05T13:13:00.000-05:002008-02-05T13:13:00.000-05:00Seems a little esoteric for an *introduction* to T...Seems a little esoteric for an *introduction* to TCS. How about more basic things like NP-completeness and the power of randomization? Or more basic algorithms and data structures? Or had the audience already seen stuff like that elsewhere? (I would assume the average mathematician had not.)Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-15586728931798727142008-02-04T19:14:00.000-05:002008-02-04T19:14:00.000-05:00Optimization. One nice paper to talk about is the ...Optimization. One nice paper to talk about is the Edmonds paper giving the Blossom algorithm for finding maximum matching. The algorithm might be too hard to explain and you could stick to Hungarian method on bipartite graphs. It is easy to "digress" from here and mention that it is one of the first papers mentioning that there should be a difference between polytime algorithms and exponential time algorithms in any hierarchy. This later formally developed in to P vs NP question.<BR/><BR/>You can digress further and talk about approximation algorithms, both from positive and negative sides.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-19718113312723691102008-02-04T16:06:00.000-05:002008-02-04T16:06:00.000-05:00I think there is a better and simpler result than...I think there is a better and simpler result than the Speilman-Tang STOC 2004 paper now: check out:<BR/><BR/>Local graph partitioning using pagerank vectors,<BR/>FOCS 2006, R. Andersen, F. Chung, K. LangAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-38120617872807341362008-02-04T13:45:00.000-05:002008-02-04T13:45:00.000-05:00(Warning: selfish plug.)If you have database folks...(Warning: selfish plug.)<BR/><BR/>If you have database folks, they may enjoy this paper:<BR/><BR/><BR/>Kamel Aouiche and Daniel Lemire, A Comparison of Five Probabilistic View-Size Estimation Techniques in OLAP, DOLAP 2007, 2007. <BR/><BR/>http://arxiv.org/abs/cs.DB/0703058Anonymousnoreply@blogger.com