tag:blogger.com,1999:blog-6555947.post389935154675590065..comments2014-01-12T10:46:48.153-07:00Comments on The Geomblog: O() notation breeds lazinessSuresh Venkatasubramaniannoreply@blogger.comBlogger10125tag:blogger.com,1999:blog-6555947.post-45823409831398566032011-10-21T16:41:57.704-06:002011-10-21T16:41:57.704-06:00http://research.microsoft.com/en-us/um/newengland/...http://research.microsoft.com/en-us/um/newengland/events/itcs2012/accepted.htm<br /><br />As a community, when did we decide to let PC members submit to ITCS? Or if we did not decide, then who made this decision?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-74021433001721759322011-10-14T19:01:03.838-06:002011-10-14T19:01:03.838-06:00I'm not advocating for either approach, but wh...I'm not advocating for either approach, but when I teach undergraduate algorithms classes I try to get the students used to the fact that we can ignore the constants. For example, when calculating 1+2+...+n instead of using the arithmetic progression formula, and then saying it is theta(n^2), what I do is to show that it has n terms that are <= n and n/2 terms that are >= n/2, therefore getting the desired bound. The advantage of this kind of reasoning is that it often allows the students to solve problems most of them wouldn't be able to solve otherwise. For example, they can find that log(n!) is theta(n log n) without knowing Stirling formula. As another example, I can show that a random element of an array is a "1/4-approximate median" with 1/2 probability and use it to analyze quicksort and randomized selection.Guilhermehttp://www.uniriotec.br/~fonsecanoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-21150575196212602522011-10-13T11:04:43.118-06:002011-10-13T11:04:43.118-06:00Original announcement (taken from google cache):
...Original announcement (taken from google cache):<br /><br />(Aside: why can't this process be transparent and fair? Because private money is allowed to be untransparent and unfair? I posted this info (twice) to the Lance-Gasarch blog yesterday, but it was censored.)<br /><br /><br />Chicago Plan Chosen Among Final Three in Simons Foundation Search for Institute for the Theory of Computing<br /><br />The Simons Foundation informed us on September 28 that the University of Chicago/TTIC proposal for an Institute for the Theory of Computing has been selected to be one of the final three proposals that they will consider. Last December, after an initial "letter of intent" phase, seven major institutions and consortia across the country were invited to submit full proposals to host the new Institute, which will benefit from a $6M/year grant from the Simons Foundation. The other two finalists are Berkeley and the MIT/Harvard consortium. Enthusiatically supported by President Robert Zimmer and PSD Dean Robert Fefferman, the Chicago plan involves major institutional commitments. The plan has been spearheaded by CS faculty members Laszlo Babai, Alexander Razborov, Stuart Kurtz, and our former faculty member Lance Fortnow (Northwestern University).<br /><br />The Institute's mission will be to further the core intellectual agenda of the Theory of Computing, the mathematical study of the fundamental nature, power, and limitations of efficient computation, as well as the manifold interactions of this field with other disciplines, ranging from mathematics and statistics to the sciences and engineering.<br /><br />We expect to host a site visit before the end of November. The final decision is expected to be made in December.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-48426828524101140662011-10-13T10:51:50.689-06:002011-10-13T10:51:50.689-06:00For some reason, new version at cs.uchicago.edu do...For some reason, new version at cs.uchicago.edu does not mention that Berkeley and MIT/Harvard are the other finalists. <br /><br />You can find that info in Google Cache.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-46530975506323378852011-10-13T10:46:24.134-06:002011-10-13T10:46:24.134-06:00The really careful thing to do would be to sequent...The really careful thing to do would be to sequentially number your constants as Suresh suggests and write down all the inequalities they need to satisfy in an apendix. And of course make sure the system is feasible. :)<br /><br />On the other hand I like how Terry Tao uses non-standard analysis to achieve the same effect in some of his posts. Seems like that way most of the messy bookkeeping is still under the hood, but the rigor is there. For example this proof is fairly readable: http://terrytao.wordpress.com/2011/08/21/hilberts-seventh-problem-and-powers-of-2-and-3/. And it seems like quite a few constants would've been lying around if he didn't define "a polylogarithmic quantity" and "a quasipolynomial quantity".<br /><br />But I think I'm too lazy even for this.Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-82752571855357435772011-10-13T10:41:22.453-06:002011-10-13T10:41:22.453-06:00http://cs.uchicago.edu/
interesting news for TCS....http://cs.uchicago.edu/<br /><br />interesting news for TCS.<br /><br />Simons is an alum of MIT and Berkeley so one of them will probably end up with the center.<br /><br />I wonder if he could just have donated the money rather than host this competition. How much influence did the proposal really have on the choice of finalists and final choice?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-55021611993864978812011-10-12T21:35:20.881-06:002011-10-12T21:35:20.881-06:00Anon: your idea could be handled by declaring upf...Anon: your idea could be handled by declaring upfront that $c_i$ for any i will be used to denote constants that do not depend on X, Y, Z. Then you can use them with impunity. <br /><br />Andy D: saying "approx n^2 pairs" is truly lazy :)Sureshhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-49245549301440296882011-10-12T21:20:56.370-06:002011-10-12T21:20:56.370-06:00Pet peeve: When someone writes, "Run this for...Pet peeve: When someone writes, "Run this for O(log n) steps," when they mean Theta(log n) steps. Big difference. We really need a different notation, though, as shorthand for, "Let c be a sufficiently large constant, independent of X, Y and Z. Then run this for c log n steps."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-54530484713092271112011-10-12T21:20:32.233-06:002011-10-12T21:20:32.233-06:00... though I guess I'm not talking about quite...... though I guess I'm not talking about quite the same situation as you (n choose 2 vs. n^2). In such cases, when I don't want to write the exact expression, I have considered writing "the \approx n^2 pairs of objects".Andy Dnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-86020430023710276222011-10-12T21:17:13.763-06:002011-10-12T21:17:13.763-06:00I think in some cases, people are afraid to use a ...I think in some cases, people are afraid to use a specific constant when that constant could readily be improved with more careful work.<br /><br />My proposed solution, at least for online papers: choose a specific text color, say green, in which to write certain constants. Green numbers will be understood to mean "the statement is true with this value, which I haven't attempted to optimize."Andy Dhttp://people.csail.mit.edu/andyd/home.htmlnoreply@blogger.com