tag:blogger.com,1999:blog-3722233.post164612220718208676..comments2019-11-15T07:39:48.651-05:00Comments on Computational Complexity: Why My Kids Trust WikipediaLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-3722233.post-88518684190421091972011-01-30T21:01:13.580-05:002011-01-30T21:01:13.580-05:00I can give an example of my opinion of Wikipedia. ...I can give an example of my opinion of Wikipedia. Around New Year's 2007 I noticed the <a href="http://en.wikipedia.org/wiki/Natural_proof" rel="nofollow">Natural Proof</a> page had a request for expert attention, so I answered it. The bulleted excerpt from the paper and most of the following text you see today were already there, so it was mainly a case of filling in detail and adding some references (they let a self-cite stand after I drew notice to it).<br /><br />However, I expressly stopped short of trying to achieve the level of a one-hour seminar lecture. I notice that someone last summer added a separate definition for natural <i>proof</i> as opposed to <i>property</i>, but that doesn't change the point. I impressed that point on my just-finished Fall 2006 intro-grad-theory class, who I thought did too much running away from my lecture notes and the Homer-Selman text to Wikipedia.KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19888928347193394862011-01-30T09:52:39.598-05:002011-01-30T09:52:39.598-05:00Your wish is my command, anonymous!
Under Lance&...Your wish is my command, <i>anonymous!</i> <br /><br />Under Lance's topic <a href="http://blog.computationalcomplexity.org/2011/01/ideal-conference.html" rel="nofollow"><i>The Ideal Conference</i></a> I have posted a brief roadmap-related question (it is #9) ... this question is adapted from a delightful essay by Scott Aaronson.<br /><br />Thoughtful responses from all (including <i>anonymous</i>) are welcome, needless to say.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56875474751373458362011-01-30T01:15:47.383-05:002011-01-30T01:15:47.383-05:00John Sidles; you write too much. focus on substanc...John Sidles; you write too much. focus on substance rather than length next time. what was your phd in ? literature or science fiction ?<br /><br />unless you have something great to tell, plz, shorten ur stuff.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10892812649650160132011-01-28T11:41:53.916-05:002011-01-28T11:41:53.916-05:00Anonymous asks: I am not sure what your point is ...Anonymous asks: <i> I am not sure what your point is ... have you looked at the ngram chart for just plain "breakthrough"?</i><br /><br />My lexical investigations of the word "breakthrough" were intended mainly to amuse ... hence the Mark Twain reference.<br /><br />The Google ngram incidence for "breakthrough" indeed is very interesting, and so is the chart for the even faster-increasing term "roadmap". Paging through the links that Google supplies to Google Books links, we see that "breakthrough" was once a mining and geologic term, that was embraced in WWII by military strategists, that was subsequently widely embraced by the whole STEM community.<br /><br />Now that we are all jaded by six decades of STEM breakthroughs, the new trendy term for STEM strategists is "roadmap"! :)<br /><br />A thoughtful, systematic abstraction of the generic elements of viable STEM roadmaps can be found in the International Roadmap Committee (IRC) <a href="http://www.itrs.net/Links/2010ITRS/IRC-ITRS-MtM-v2%203.pdf" rel="nofollow"><i>More than Moore White Paper</i></a> ... so these light-hearted investigations with Google ngrams can sometimes lead us to serious documents.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3569815155134747662011-01-28T10:31:57.998-05:002011-01-28T10:31:57.998-05:00Sidles, I am not sure what your point is, but have...Sidles, I am not sure what your point is, but have you looked at the ngram chart for just plain "breakthrough"? According to Google, the word didn't catch on until the 1940's and has experienced an almost exponential growth since then. Is the growth of the phrase "mathematical breakthrough" commiserate with the use of "breakthrough", or has "mathematical breakthrough" grown faster, or maybe even slower?<br /><br />It's always useful to compare a two-word phrase to the single-word baselines.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21924871979734806142011-01-25T22:32:07.109-05:002011-01-25T22:32:07.109-05:00You can use it to more easily find potentially cor...You can use it to more easily find potentially correct information and then more traditional references. I have seen and fixed a wide variety of errors on Wikipedia pages. Some have been reverted by others ruthlessly even though my correction was correct. While the pages there are often easy to find and use to "learn" something, if it is something that matters to you then you should go to the source which is referenced on the page. If no source is given, trust it as much as something you hear at a cocktail party.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58276532099672678882011-01-25T22:26:27.702-05:002011-01-25T22:26:27.702-05:00E is probably on to something! I bet that the girl...E is probably on to something! I bet that the girls just forgot the exact words of their comment. This proves that this post is true! Thanks, E.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6290331475088743642011-01-25T22:11:50.758-05:002011-01-25T22:11:50.758-05:00I don't see how you can NOT use Wikipedia, unl...I don't see how you can NOT use Wikipedia, unless you're willing to ignore one of the top five search results on almost any topic you care to name.Ben Fultonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24431188943711008132011-01-25T20:48:13.178-05:002011-01-25T20:48:13.178-05:00The details might not sound right but it is likely...The details might not sound right but it is likely (at least based on) a true story at a certain level. A very similar edit was made in September of 2009 from a computer apparently located in Illinois. What was actually added was "i like grapes. nerds are cows." and it was removed around two minutes later with a message of "The recent edit you made to the page Grape has been reverted, as it appears to be unconstructive."Enoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14746411599662659272011-01-25T19:03:02.811-05:002011-01-25T19:03:02.811-05:00Whenever I am drafting the introduction and/or dis...Whenever I am drafting the introduction and/or discussion sections of an article, I try out the ideas in the blogosphere ... so much of this prose gets recycled.<br /><br />At present our Quantum Systems Engineering (QSE) group is focussed on (1) simulating large-scale quantum dynamical systems and (2) experimentally verifying that the simulations work. To accelerate this "<a href="http://www.pnas.org/content/106/8/2477.full" rel="nofollow">virtuous circle</a>", our design and coding efforts draw heavily on recent advances in quantum information theory and complexity theory.<br /><br />You can expect our hardware-driven interest in QIT/CT to tail off in about eighteen more months ... `cuz by then we hope to understand quite a lot ... and to have experimentally verified our understanding ... and to be able to explain it fluently in several different mathematical languages ... including in particular the language of computational complexity. :)<br /><br />Of course, *lots* of mathematicians, scientists, and engineers have pursued this same dream---including von Neumann and Feynman---and it has always proved to be a humbling pursuit ... so maintaining sense of humor and proportion is an absolute necessity. <br /><br />Recent advances in complexity theory, quantum information theory, and category theory have provided powerful new mathematical tools that are speeding the pace and retiring the risk of this centuries-old pursuit ... for which our appreciation and gratitude as engineers and medical researchers is extended.<br /><br />The questions that Annie and Molly Fortnow are raising about "trusting Wikipedia", are partly about a world in which Feynman's and von Neumann's comprehensive dynamical and informatic visions are are beginning to come true ... that's why they're wonderful questions IMHO ... even though the answers can be discomfiting to contemplate.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82181866085738437812011-01-25T15:15:19.556-05:002011-01-25T15:15:19.556-05:00John Sidles, what is your profession ? are you a p...John Sidles, what is your profession ? are you a professional blogger? it seems that your comments are very long!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18045163046560429342011-01-25T09:42:04.991-05:002011-01-25T09:42:04.991-05:00GASARCH notes: When asking how reliable Wikipedia ...GASARCH notes: <i>When asking how reliable Wikipedia is one non-rhetorical question comes to mind- compared to what?</i><br /><br />As a case study, just yesterday, for a review article, I tried to track down a source text for the Wikipedia assertion that Saunders Mac Lane once said:<br /><br />---------------<br /> "I didn't invent categories to study functors; I invented them to study natural transformations."<br />---------------<br /><br />This quotation appears (verbatim) at least 46 times on the internet ... but it ain't easy to find a verifiable source for it in the mathematical literature.<br /><br />In their article <i>Categorification</i> (1998) Baex and Dolan assert "Mac Lane has said that categories were originally invented, not to study functors, but to study natural transformations!" ... but like Wikipedia, they provide no citation.<br /><br />Looking back further, with Baez and Dolan's version as a help, we find Mac Lane himself saying, in his article <i>The development and prospects for category theory:</i> (1996): “But I emphasize that the notions <i>category</i> and <i>functor</i> were not formulated or put in print until the idea of a <i>natural transformation</i> was also at hand.” (italics as in Mac Lane's original text).<br /><br />Is this the final word in the matter? Heck, don't ask me! We see that in this instance, Wikipedia supplied only a rough approximation to the facts of the case ... and the peer-reviewed literature wasn't much better.<br /><br />So perhaps Mark Twain said it best: "Truth is precious; let us economize it." Hey ... wait a second ... was that *really* <a href="http://books.google.com/books?id=FvQQAAAAYAAJ&pg=PA89" rel="nofollow">what Mark Twain actually said</a>? :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68653601291249092672011-01-25T09:05:57.084-05:002011-01-25T09:05:57.084-05:001) On a recent post I used Wikipedia to point to a...1) On a recent post I used Wikipedia to point to a result. I phrased it carefully saying<br />``According to Wikipedia...''<br />and gave the link. There were some comments that objected to the link to Wikipedpia, one of which demanded I remove the link. It would have made more send to demand I provide an additional link to the actual paper being referenced (which I did).<br />How did I find the link to the actual paper? You can guess.<br /><br />2) In a recent paper I wrote the ONLY source I could find for a proof was on Wikipedia. In the paper I referenced wikipedia but also provided the proof for completeness. The referee objected to even the reference to wikipedia.<br />But to NOT reference it would have been dishonest- that is where I found it. And I provided the proof so the paper is fine in that regard.<br /><br />3) Annie and Molly- do your teachers allow you to use WIkipedia?<br /><br />4) Parents- do you allow your kids to use it? Do your kids teachers allow them to use it?<br /><br />5) When asking how reliable Wikipedia is one non-rhetorical question comes to mind- compared to what?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64015717250428693992011-01-25T08:32:55.999-05:002011-01-25T08:32:55.999-05:00I would like to thank Annie and Molly Fortnow for ...I would like to thank Annie and Molly Fortnow for raising this wonderful question. It seems to me that they are getting to be mature enough to read and enjoy Mark Twain's description of the scientific process, that is in his book <i>Life on the Mississippi</i>, in the famous passage that begins <a href="http://books.google.com/books?id=Lh0RAAAAYAAJ&pg=PA136" rel="nofollow">"Any calm person, who is not blind or idiotic"</a> and concludes:<br /><br />--------------<br /> "There is something fascinating about science. One gets such wholesale returns of conjecture out of such a trifling investment of fact."<br />--------------<br /><br />Let us embrace Mark Twain's reasoning, in reflecting upon the number of AMS Math Reviews whose text contains the word "breakthrough. Here is the number of such reviews, arrayed in five-year bins:<br /><br />1951-1955: 000 AMS Math Review "breakthroughs" <br />1956-1960: 003 ...<br />1961-1965: 007 ...<br />1966-1970: 007 ...<br />1971-1975: 009 ...<br />1976-1980: 029 ...<br />1981-1985: 055 ...<br />1986-1990: 071 ...<br />1991-1995: 105 ...<br />1996-2000: 160 ...<br />2001-2005: 182 AMS Math Review "breakthroughs" <br /><br />Now, to adopt Mark Twain's language, any calm person, who is not blind or idiotic, can see that the doubling cadence for mathematical "breakthroughs" is 8.06 years, and that consequently, in the year 2100, there will be 127,495 "mathematical breakthroughs" cited in AMS Math Reviews. <br /><br />Which is to say that in year 2100, Math Reviews will be reporting a mathematical "breakthrough" about once every four minutes and seven seconds. <br /><br />Is this an unreasonably large number of mathematical breakthroughs? Definitely not! Because we are to consider, that on a happy, prosperous, free, and secure planet of 10^10 people (the kind of planet we all hope Annie and Molly will be living upon), we can anticipate that about one person in 1000 will choose a career in mathematics. In which case, the mean interval between breakthroughs, per living mathematician, will be 78 years.<br /><br />Thus we are justified in feeling optimism, that in the year 2100, achieving a mathematical "breakthrough" will be a once-in-a-lifetime dream ... that is reasonably accessible to every working mathematician, including Annie and Molly, and including <i>their</i> children, and including all young people who are inspired to do mathematics. <br /><br />Good! :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51151600376268255872011-01-25T02:26:21.031-05:002011-01-25T02:26:21.031-05:00I trust a wikipedia page on first reading about as...I trust a wikipedia page on first reading about as much as I trust a random textbook from the library. Which, to be honest, depends on what kind of deadline I'm working on.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47290790811808220552011-01-24T20:12:36.221-05:002011-01-24T20:12:36.221-05:00Lance, why the disclaimer? They didn't actual...Lance, why the disclaimer? They didn't actually do it. Was your disclaimer an attempt to make the lie seem real?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17799282626587201932011-01-24T19:55:28.763-05:002011-01-24T19:55:28.763-05:00There are two different problems (among many I wou...There are two different problems (among many I would guess) with Wikipedia.<br /><br />First, incorrect information can be slipped into a page (on purpose or not) and not be noticed for a while.<br /><br />Second, once incorrect information is in a page it is sometimes difficult to remove because ignorant white-knights keep restoring it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84671205603652218782011-01-24T19:47:13.048-05:002011-01-24T19:47:13.048-05:00The grapes page appears to be the victim of multip...The grapes page appears to be the victim of multiple attempts by vandals. Vandalized pages can often be auto-detected.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78997458742855364052011-01-24T18:56:01.961-05:002011-01-24T18:56:01.961-05:00@John Sidles
To be fair, the Google ngram viewer ...@John Sidles<br /><br />To be fair, the Google ngram viewer link you posted has been set to "smoothing of 3", which tells a very different story than "smoothing of 1." Taking either very seriously would of course presume that Google ngram viewer is a good way to view trends in this sort of data... I would have to suppose it is not.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18068075854783648722011-01-24T16:05:16.629-05:002011-01-24T16:05:16.629-05:00why should we believe your storywhy should we believe your storyAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11067348840626487572011-01-24T13:23:39.115-05:002011-01-24T13:23:39.115-05:00For the benefit of readers of Computational Comple...For the benefit of readers of <i>Computational Complexity</i> who don't have access to AMS' Math Review, appended is a link to a screenshot of the "Math Review breakthrough number."<br /><br />For maximal fun, please consider posting your prediction of the "Math Review breakthrough number" before <a href="http://faculty.washington.edu/sidles/misc/AMS_MathReview_breakthroughs.png" rel="nofollow">clicking to see the answer</a>.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68665235339164249022011-01-24T12:31:21.487-05:002011-01-24T12:31:21.487-05:00David asserts: Compared to the usual completely ne...David asserts: <i>Compared to the usual completely neutral and unevaluative tone of Math Review, "likely to be helpful" is strong praise.</i><br /><br />Lol ... David, your assertion inspired me to wonder: How many AMS Math Reviews contain the word "breakthrough" in the field "Review Text"?<br /><br />As a hint, here's Google ngram chart for the phrase "<a href="http://ngrams.googlelabs.com/graph?content=mathematical+breakthrough&year_start=1800&year_end=2000&corpus=0&smoothing=3" rel="nofollow">mathematical breakthrough</a>."<br /><br />Perhaps folks would care to guess the "breakthrough number" (without looking)?John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74336003622200147752011-01-24T11:10:05.807-05:002011-01-24T11:10:05.807-05:00Compared to the usual completely neutral and uneva...Compared to the usual completely neutral and unevaluative tone of Math Review, "likely to be helpful" is strong praise.David Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52402517843269211292011-01-24T10:47:21.633-05:002011-01-24T10:47:21.633-05:00Aha! So perhaps this post is a parable ... a foll...Aha! So perhaps this post is a parable ... a follow-up to the previous post <a href="https://www.blogger.com/comment.g?blogID=3722233&postID=4828575039148806480" rel="nofollow"><i>"What is a breakthrough? Lets have an intelligent discussion!"</i></a><br /><br />Pursuant to Lance and GASARCH's post, I've taken to looking up the MathSciNet reviews of seminal articles in mathematics ... and it's remarkable how commonly breakthroughs at first pass unrecognized even by the most august reviewers ... for example, the highest praise that Andre Weil could bring himself to offer regarding Samuel Eilenberg's and Saunders Mac Lane's <i>Natural isomorphisms in group theory</i> (1942, review 0007421 (4,134d)) was that their ideas were "likely to be helpful".<br /><br />Perhaps two take-home lessons, from *both* posts, are "think for oneself" and "trust, but verify" ... regardless of whether one is reading Wikipedia or the academic literature! :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22555745968122304582011-01-24T09:34:55.452-05:002011-01-24T09:34:55.452-05:00Wow, Anonymous, way to miss the joke. Go read the...Wow, Anonymous, way to miss the joke. Go read the last two sentences again.Anonymousnoreply@blogger.com