tag:blogger.com,1999:blog-3722233.post2438403555632598333..comments2023-02-04T09:02:15.330-06:00Comments on Computational Complexity: Scooped by 400 yearsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-69735686035512206232011-07-19T04:40:37.593-05:002011-07-19T04:40:37.593-05:00Major domains of human activity, like transportati...Major domains of human activity, like transportation, communication, software,... have their own infrastructure.<br />But we lack an "infrastructure" for mathematics (and theoretical computer science), by which I mean a digital formal (logical) library of almost all the interlinked definitions and theorems we have, supplemented with a proof checker, and people be compelled to add their results to it.<br />There are experimental implementations: http://us.metamath.org/<br />This is well comparable with the extensive software libraries.<br />Our library can be enhanced by a (a little smart) search engine that given the formal form of a conjecture or definition, can search for similar results.<br />Such a facility can improve our overall performance by 30%, if nothing.Majdodinhttps://www.blogger.com/profile/06638299762577890471noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68795379598410193242011-07-09T11:49:27.625-05:002011-07-09T11:49:27.625-05:00Bill asked: "What if it (your result) truly i...Bill asked: "What if it (your result) truly is independent?"<br /><br />This is indeed a subtle issue. I faced it right now when finishing my book on circuit complexity. People from Moscow university supplied me with a lot of papers (in Russian, I can read them) with results that were obtained years and years ago, and then were re-discovered in the West. So what? Are these "re-discovers" results? I think they are. Because for people in the West these results do not existed at all! But this is a very special case. "Rediscovering" and publishing results that *could* be accessed with a little effort is just a crime. <br /><br />Bill also asked: "What if your proof is cleaner but essentially the same?"<br /><br />Cleaner and simpler proofs also make a *real* contribution, I think. Especially when they use some less fancy mathematics than original ones. One of my favorite examples is Razborov's proof of Hastad's Switching Lemma. There are many more.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32870517775336055032011-07-09T07:28:20.573-05:002011-07-09T07:28:20.573-05:00Count me as an optimist:
The fact that human know...Count me as an optimist:<br /><br />The fact that human knowledge may be expanding at an exponential rate is probably a good thing.<br /><br />Organizing and searching the emerging database should keep many a post-doc gainfully employed.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71815063939451031382011-07-08T12:19:48.834-05:002011-07-08T12:19:48.834-05:00It is paradoxical that pessimists regard GASARCH&#...It is paradoxical that pessimists regard GASARCH's questions optimistically, while optimists regard GASARCH's questions pessimistically.<br /><br />-------------<br /><br /><b>Pessimist:</b> Research funding is flat, resources are are short, and the planet is overheating. In consequence, there will never be substantially more STEM professionals than there are now, and so all of GASARCH's issues are self-limiting. Problem solved.<br /><br /><b>Optimist:</b> On a secure, prosperous and healthy 21st century Earth of 10^10 people, at least three percent of those people will be STEM professionals, and at least three percent of those STEM professionals will work in research-level CSE. If each of these professionals publishes three CSE articles per year, the resulting publication rate will be one article per second ... and so all of GASARCH's issues are utterly intractable.<br /><br />-------------<br /><br />Although I am myself a committed optimist, it appears that many (most?) readers of <i>Computational Complexity</i> belong to the pessimist faction ... is this assessment correct? :)John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54331684599982231972011-07-07T23:01:56.471-05:002011-07-07T23:01:56.471-05:00FYI, all of Ron Graham's papers can be found h...FYI, all of Ron Graham's papers can be found here: http://www.math.ucsd.edu/~ronspubs/<br />(The link originally given only covers through 2008)Andy Parrishhttp://www.math.ucsd.edu/~atparris/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68894678858118426172011-07-07T20:54:15.562-05:002011-07-07T20:54:15.562-05:00If commercial journals have their way, point numbe...If commercial journals have their way, point number 3 will be nullified: at least for people who don't have a top notch academic library, most science published in the last century is hidden behind ridiculously overpriced paywalls.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4224342672473615442011-07-07T16:57:37.250-05:002011-07-07T16:57:37.250-05:00This article was written in 1994. The online disc...This article was written in 1994. The online discussions of it date back at least 5 years. Why not keep it until April 1st?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15070031901091291022011-07-07T16:51:26.619-05:002011-07-07T16:51:26.619-05:00How did enough people not take Calculus and yet en...How did enough people not take Calculus and yet end up in this area of the medical profession that this got written, reviewed, and published?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5260370473192883012011-07-07T15:05:05.804-05:002011-07-07T15:05:05.804-05:00@Anon#4: The role of research is to "advance ...@Anon#4: The role of research is to "advance human's knowledge". How does a paper about something known for 400 years (actually, more than 2200 thousand year as Archimede used this method) advance anything? Not to mention that this method is actually taught in high schools. How would one claim to be a scientist if one don't know something any one from a creditable high school would know?<br /><br />The fact that the paper is published in a Diabetes journal only make it worse. Are you gonna trust someone without (slightly advance) high school knowledge to design your next drug?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29276774648992429512011-07-07T13:36:38.359-05:002011-07-07T13:36:38.359-05:00If you are still looking for that list of secret s...If you are still looking for that list of secret sharing papers, it may have been Stinson's (outdated) Secret Sharing Bibliography: http://www.cacr.math.uwaterloo.ca/~dstinson/ssbib.htmlZachnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52346185321107098352011-07-07T13:36:18.238-05:002011-07-07T13:36:18.238-05:00My reaction was pretty much the opposite of the co...My reaction was pretty much the opposite of the consensus: So what?<br /><br />This was published in a DIABETES journal, it is pretty understandable if applied people in different fields end up "re-inventing the wheel" occasionally since they have no real interest or expectation of being mathematically original - they just want to solve their problem.<br /><br />It would of course be quite different if a "scooped" math research was published in Annals of Math or something like that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-40982021582985256662011-07-07T13:24:47.760-05:002011-07-07T13:24:47.760-05:00I agree with the fact that it can be hard to find ...I agree with the fact that it can be hard to find what was already proved given the number of papers published nowadays. But the example is of completely different nature to my mind. As stated in the title of the article, the authors aims at giving a mathematical method for doing whatever. As a non-mathematician, he should have asked a mathematician about this! If I am going to work on, say, biology, I begin by asking some people knowing the field to know whether I am mistaking or not!B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2416062885237836482011-07-07T12:18:14.735-05:002011-07-07T12:18:14.735-05:00That just show how far math from real science.That just show how far math from real science.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83609209861089283302011-07-07T12:07:27.989-05:002011-07-07T12:07:27.989-05:00For my own amusement, I once searched the pre-WWII...For my own amusement, I once searched the pre-WWII physics literature to find out how much literature John von Neumann had to read to keep current on quantum measurement theory -- it turns out that JvN had to read (at most) two articles per month. Nowadays that number is several articles per day ... very roughly 100X greater. <br /><br />Are we thereby 100X smarter than JvN, either individually or collectively? Few would say so ... and yet this flood of literature *does* have advantages.<br /><br />Consider for example this month's <i>Bull. AMS</i> survey by Pelayo and Ngoc titled "Symplectic theory of completely integrable Hamiltonian systems" (2011). This article deals with classic topics like the dynamics of a pair of interacting spins ... topics that have been discussed in literally thousands of articles spanning more than a century ... all the way back to Moriarty's <i>Dynamics of an asteroid</i> (1902). Yet Pelayo and Ngoc find plenty of new things to say in their wonderfully interesting survey. What's more, the <i>Bull. AMS</i> publishes comparably interesting articles pretty much every month. Bravo! This flood of integrated understanding is both the glory and the curse of our 21st century.<br /><br />That is why (IMHO) we are all of us living in a golden era for mathematics, for science, and (most of all) for engineering. JvN of course was all three ... I often wish that he could have lived to enjoy the abundant opportunities of the present era.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.com