tag:blogger.com,1999:blog-6555947.post6096230286221342974..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: A seminar on randomizationSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-6555947.post-70860450707105231722008-06-18T10:14:00.000-06:002008-06-18T10:14:00.000-06:00indeed I will. it will be at http://apollonius.cs....indeed I will. it will be at <BR/><BR/>http://apollonius.cs.utah.edu/mediawiki/index.php/Algorithms_SeminarSuresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-40855535397773912512008-06-18T08:55:00.000-06:002008-06-18T08:55:00.000-06:00Are you planning to maintain a webpage for the sem...Are you planning to maintain a webpage for the seminar?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-88934601423073611802008-06-12T05:44:00.000-06:002008-06-12T05:44:00.000-06:00I was also going to mention distributed computing ...I was also going to mention distributed computing as an area where randomized algorithms can do provably better than derandomized ones.<BR/><BR/>Also black-box polynomial identity testing. Along the same lines, you could probably cover some of the PCP theorem -- at least the proof that NP \in PCP(poly, 1).<BR/><BR/>Another example of where randomization "provably beats" determinism is with regard to existence of Nash equilibria!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-12010573141225729402008-06-11T17:37:00.000-06:002008-06-11T17:37:00.000-06:00I believe Valiant's randomized hypercube routing a...I believe Valiant's randomized hypercube routing algorithm is an example where randomness is provably better. In general, cryptography and theory of distributed computing are good sources of such examples.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-73704141383272905032008-06-09T10:16:00.000-06:002008-06-09T10:16:00.000-06:00Suresh, I will email you my notes soon. In respons...Suresh, I will email you my notes soon. In response to Chandra's post, while it is true that mixing the "algorithms" and "complexity" parts in such a course can be challenging, one way of quickly covering the latter is the following, in case you can only allot 5-8 classes for it:<BR/><BR/>1. BPP contained in P/poly, thus showing that explicit construction of (small sets of) "advice strings" is the main issue in derandomization.<BR/><BR/>2. k-wise independence, and how it leads to some types of explicit constructions for the above.<BR/><BR/>3. Blum-Micali and Yao (quick look if time is an issue), and a detailed study of Nisan-Wigderson.<BR/><BR/>4. Weak random sources: the models of von Neumann, Santha-Vazirani and Chor-Goldreich, and how they are all subsumed by the delta-sources of Zuckerman.<BR/><BR/>5. Extractors, and an exercise using the probabilistic method that good extractors *exist*.<BR/><BR/>6. Explicit construction of extractors: the simplest I can think of is Luca's "Extractors and Pseudorandom Generators", where the earlier study of Nisan-Wigderson will be useful.<BR/><BR/>If time is a problem, the method of conditional probabilities can be given as an exercise or in a handout.<BR/><BR/>Of course, the above is just one among several ways of covering the material.<BR/><BR/>AravindAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-45730791897118623002008-06-08T22:04:00.000-06:002008-06-08T22:04:00.000-06:00Almost certainly I'd want to cover fingerprinting ...Almost certainly I'd want to cover fingerprinting (and should have modified the 'applications' section properly. <BR/><BR/>As for shared randomness in communication complexity: this is a cool thing to talk about, but I wonder whether I can afford to fit it in. What I definitely want to have students review are examples (like in CC) of where randomization is provably better. <BR/><BR/>In fact, right now I can only think of deterministic vs randomized CC, and volume estimation for polytopes.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-2727740191062066352008-06-08T19:24:00.000-06:002008-06-08T19:24:00.000-06:00Would you cover fingerprinting in hashing? How abo...Would you cover fingerprinting in hashing? How about showing that randomness and shared randomness are necessary sometimes - say some lower bound from communication complexity?<BR/>sudiptoAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-85282820381373185202008-06-08T09:57:00.000-06:002008-06-08T09:57:00.000-06:00This list of topics would be thestarting point for...This list of topics would be the<BR/>starting point for me as well<BR/>if (and when) I teach a class<BR/>on randomization. However, I feel<BR/>that it will be difficult to do<BR/>justice to both algorithms and<BR/>complexity related topics such<BR/>as pseudo randomness and randomness<BR/>extraction in the same class unless<BR/>the students are already mature.<BR/>Maybe I am mistaken and more<BR/>experienced folk can correct me.Chandrahttps://www.blogger.com/profile/00057069075567569157noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-92033242224380427492008-06-08T07:23:00.000-06:002008-06-08T07:23:00.000-06:00Hi Aravind, That would be excellent. In fact I ha...Hi Aravind,<BR/> That would be excellent. In fact I had spied on your web page earlier when I was designing the content, but I didn't find anything (and now I know why :))<BR/><BR/>thanks !Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-59359794028467143802008-06-08T06:05:00.000-06:002008-06-08T06:05:00.000-06:00Suresh, if you like, I would be glad to email you ...Suresh, if you like, I would be glad to email you my class notes from a grad class on "Randomness and Computation". I am not making them available online yet since they are not fully polished.<BR/><BR/>Let me know, and wishing you fun with the course,<BR/>AravindAnonymousnoreply@blogger.com