tag:blogger.com,1999:blog-3722233.post1413057789958410708..comments2024-02-21T12:19:43.948-06:00Comments on Computational Complexity: But This One Is Different...Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger66125tag:blogger.com,1999:blog-3722233.post-41805599992911647512010-08-19T06:50:16.779-05:002010-08-19T06:50:16.779-05:00Perhaps Tao and Gowers were more circumspect than ...Perhaps Tao and Gowers were more circumspect than others because neither Tao nor Gowers is an expert on the problem; at any rate neither has published anything about it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68792868645969815202010-08-18T10:08:56.662-05:002010-08-18T10:08:56.662-05:00Neither (most) TCS researchers, nor pure mathemati...<i><br />Neither (most) TCS researchers, nor pure mathematicians will agree with this statement. <br /></i><br />Sure, people might disagree with regard to what extend our efforts should be focused on "real-world"<br />questions (as opposed to just asking questions "for the fun of it", as in pure math), but no one can deny that the questions complexity tries to understand, such as P vs NP, are purely mathematical questions that are interesting in their own right. True, they have a much different flavour from, say, geometry (they're much more akin to combinatorics), but it's pure math nonetheless.<br /><br />As for publication habits, what you say is true but each field has its own conventions. As an<br />example of the opposite one could notice that most engineering disciplines use non-alphabetical author order anyway, whereas TCS sticks to the usual convention within mathematics. (Of course this doesn't indicate anything beyond that).<br /><br /><i> Most STOC/FOCS papers have very little to do with mathematics -- they use mathematical formalism, but so do most engineering disciplines.<br /></i><br />They're all about the mathematics of computation. Apart from the real-world applications these papers may or may not have, these are interesting purely mathematical questions by themselves. And most of<br />them are not inspired by real-world applications anyway, but as an effort to understand computation,<br />randomization, etc. <br /><br />Tell me what difference there is between this and pure (not applied) math. Of course if you define "math" as a list of fields that does not include TCS you can claim that most of TCS is not about math by definition, but this is pretty narrow-minded: the methodology and motivation<br />(with emphasis in undestanding and mathematical rigour rather than applicability) are the same in TCS as in other areas of math. We study different concepts that other areas, but in a purely mathematical way. On what grounds can one claim that these are not<br />interesting mathematical problems worthy of study? The fact that "they are about computation" is only a definition of the field of study. <br /><i><br />And yes "depth" is an important mathematical notion. Not all mathematical areas have the same depth<br /></i><br />I don't think that's what "depth" is understood to mean in phrases such as "deep insight" or "deep<br />theorem". But anyway, adopting your definition, most of combinatorics is not deep either. Does it mean it's easy or a applied math field? <br />Number theory was disregarded by many mathematicians for ages, and the same has happened with e.g. combinatorics. The reason being nothing else than the one you seem to advocate, namely that the questions studied have a different feel than questions in other "established" areas of math, or because little background is required to attack them and therefore are lacking in "depth".<br />Do you agree with them?<br /><br />As a matter of fact, all other things equal, depth (in your sense) should be a disadvantage. The most beautiful, captivating questions are precisely those<br />that are easy to state and understand and yet requiere non-obvious insightful ideas to solve, not those that require lots of background just to state.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39497191317766916932010-08-18T10:08:06.452-05:002010-08-18T10:08:06.452-05:00Neither (most) TCS researchers, nor pure mathemati...<i><br />Neither (most) TCS researchers, nor pure mathematicians will agree with this statement. <br /></i><br />Sure, people might disagree with regard to what extend our efforts should be focused on "real-world"<br />questions (as opposed to just asking questions "for the fun of it", as in pure math), but no one can deny that the questions complexity tries to understand, such as P vs NP, are purely mathematical questions that are interesting in their own right. True, they have a much different flavour from, say, geometry (they're much more akin to combinatorics), but it's pure math nonetheless.<br /><br />As for publication habits, what you say is true but each field has its own conventions. As an<br />example of the opposite one could notice that most engineering disciplines use non-alphabetical author order anyway, whereas TCS sticks to the usual convention within mathematics. (Of course this doesn't indicate anything beyond that).<br /><br /><i> Most STOC/FOCS papers have very little to do with mathematics -- they use mathematical formalism, but so do most engineering disciplines.<br /></i><br />They're all about the mathematics of computation. Apart from the real-world applications these papers may or may not have, these are interesting purely mathematical questions by themselves. And most of<br />them are not inspired by real-world applications anyway, but as an effort to understand computation,<br />randomization, etc. <br /><br />Tell me what difference there is between this and pure (not applied) math. Of course if you define "math" as a list of fields that does not include TCS you can claim that most of TCS is not about math by definition, but this is pretty narrow-minded: the methodology and motivation<br />(with emphasis in undestanding and mathematical rigour rather than applicability) are the same in TCS as in other areas of math. We study different concepts that other areas, but in a purely mathematical way. On what grounds can one claim that these are not<br />interesting mathematical problems worthy of study? The fact that "they are about computation" is only a definition of the field of study. <br /><i><br />And yes "depth" is an important mathematical notion. Not all mathematical areas have the same depth<br /></i><br />I don't think that's what "depth" is understood to mean in phrases such as "deep insight" or "deep<br />theorem". But anyway, adopting your definition, most of combinatorics is not deep either. Does it mean it's easy or a applied math field? <br />Number theory was disregarded by many mathematicians for ages, and the same has happened with e.g. combinatorics. The reason being nothing else than the one you seem to advocate, namely that the questions studied have a different feel than questions in other "established" areas of math, or because little background is required to attack them and therefore are lacking in "depth".<br />Do you agree with them?<br /><br />As a matter of fact, all other things equal, depth (in your sense) should be a disadvantage. The most beautiful, captivating questions are precisely those<br />that are easy to state and understand and yet requiere non-obvious insightful ideas to solve, not those that require lots of background just to state.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25375744253685801482010-08-18T08:27:29.459-05:002010-08-18T08:27:29.459-05:00TCS is just another branch of pure math
Neither ...<i><br />TCS is just another branch of pure math<br /></i><br /><br />Neither (most) TCS researchers, nor pure mathematicians will agree with this statement. Just ask around. In any case, if it were true then most TCS researchers would have had jobs in math departments. Moreover, most TCS researchers do not follow standard mathematical practices for publication either -- their practices are more closely aligned to engineering disciplines.<br /><br /> Most STOC/FOCS papers have very little to do with mathematics -- they use mathematical formalism, but so do most engineering disciplines. There are a<br />small subset of papers in these proceedings that has mathematical content, but most don't in any real sense.<br /><br />And yes "depth" is an important mathematical notion. Not all mathematical areas have the same depth. A somewhat arbitrary and rough measure of depth is the number of years it takes a graduate student to study before he/she can hope to understand current research. By this measure algebraic geometry is indeed a much deeper topic (number theory, areas of mathematical logic are probably even deeper). The mathematical parts of TCS are not particularly deep by this measure.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35163057533812065872010-08-18T03:38:30.214-05:002010-08-18T03:38:30.214-05:00Actually, the typical reading list for a graduate ...<i>Actually, the typical reading list for a graduate student in algebraic geometry has more mathematical depth and content (not to mention current research) than all STOC/FOCS proceedings taken together. </i><br />How can people write such bullshit?<br />It may require more background to start doing research in algebraic geometry, but that's about it. An average paper in algebraic geometry is no harder than an average TCS paper. And what do you mean by "depth" here?<br /><br /><i><br />Most FOCS/STOC papers have zero math content <br /></i><br />I'm at a loss to understand what this may mean, since TCS is just another branch of pure math, so of course every paper proving something in the area has positive math content.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79004534035073000732010-08-18T02:00:21.185-05:002010-08-18T02:00:21.185-05:00Why do people think that Vinay is reading all the ...Why do people think that Vinay is reading all the discussion and hence is aware of the errors found? It may also be that he has gotten trillion emails and decided to stop checking them while working on the manuscript.<br /><br />I just think that people should be given time. Perhaps he was on vacations short time after sending the manuscript :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87507440902101329312010-08-18T00:08:42.848-05:002010-08-18T00:08:42.848-05:00Oh, my previous comment was meant to
appear in &qu...Oh, my previous comment was meant to<br />appear in "My last post on the alleged P NE NP paper". Got a bit cofused, i'm not used to those<br />frequent updates of most computerscience blogs since last week ;-)Anonymous (!)noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-993611432475696392010-08-17T23:51:50.168-05:002010-08-17T23:51:50.168-05:00@blah
They still are several leagues higher than ...@blah<br /><br />They still are several leagues higher than most of us. And certainly high enough to be allowed to have their own way of deciding how serious a proof of the major conjecture in their area of expertise has to be taken.<br /><br />My irritation of point 13 still stands, though. I wondered if if my reaction to it was inapropiate. But<br />come on, why making fun of an anonymos internet comment? And no, it wasn't my comment :-)Anonymous (!)noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6424960096710082732010-08-17T23:15:23.414-05:002010-08-17T23:15:23.414-05:00"While Tao reached his conclusion after a len..."While Tao reached his conclusion after a lengthy (and public) rumination about the document, Fortnow and Aaronson apparently dismissed it outright (without even a hint where they suspected the problems lie). This generates a justified suspicion that their publicly expressed extremely quick reaction was not based on purely scientific grounds. It is very likely that future P/NP proofs will rely on mathematics which only "humble pure mathematicians" will have access to, and we will be spared this kind of unprofessional behavior."<br /><br />Fortnow and Aaronson aren't even in Tao's league either.<br /><br />Honestly, if Terrence Tao is humble, everyone should beblahhttps://www.blogger.com/profile/06484152750345714472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90493012504071073072010-08-17T13:14:50.083-05:002010-08-17T13:14:50.083-05:00Everyone reads with intent, and preconceptions, An...Everyone reads with intent, and preconceptions, Anon. If we're miscommunicating, I apologize for my side of it. I just observed a beautiful scientific week, and played a (very) small role in it. I'm in a great mood, even though I think the recent posts and comments here are kinda clueless. I wouldn't want to argue with you, even if I knew your real name. Going forward, I hope my own work can be as high quality as what I just witnessed, and I wish you the very best.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79138158711311014462010-08-17T13:12:31.570-05:002010-08-17T13:12:31.570-05:00Well, for me the discussion was very interesting a...Well, for me the discussion was very interesting and enjoyable - so I am glad Lipton,Regan, Tao et. al. were willing to take some time and look at the "proof."ali0482http://www.nrzee.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17956753015225914942010-08-17T12:55:46.513-05:002010-08-17T12:55:46.513-05:00@Aaron Sterling
"The empirical data do not s...@Aaron Sterling<br /><br />"The empirical data do not support you."<br /><br />Or maybe you didn't actually understand what I was saying.<br /><br />"But calling Lipton, Regan, Gowers, Tao, or anyone who contributed to the wiki "naive" is really missing the point."<br /><br />Yup. You clearly didn't read my statement for the purpose of understanding. You read it with intent. To claim I called any of those people "naive" is REALLY missing the point, not to mention simply wrong. Re-read the post then re-read Anon #9.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47369864446693469552010-08-17T11:46:14.523-05:002010-08-17T11:46:14.523-05:00If Noga Alon and Terry Tao see it worthwhile to pu...<i><br />If Noga Alon and Terry Tao see it worthwhile to publish in FOCS and STOC,<br /></i><br /><br />They do, as do several other mathematicians. But I doubt that they think of their FOCS/STOC papers as central to their research. In fact, mathematics departments typically do not count FOCS/STOC papers as publications (for purposes of annual evaluations, tenure etc.) .<br /><br />I agree that a few FOCS/STOC conference presentations adds a bit of jazz to a math cv (perhaps not so much as perhaps a PNAS or Nature publication but a little nevertheless) -- but they are certainly not treated equivalent to publication in a math journal.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35608267195072131682010-08-17T11:30:00.262-05:002010-08-17T11:30:00.262-05:00If Noga Alon and Terry Tao see it worthwhile to pu...If Noga Alon and Terry Tao see it worthwhile to publish in FOCS and STOC, I don't see how the opinions of various anonymice (including myself) has any bearing on the matter.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56278531728138041202010-08-17T11:25:19.281-05:002010-08-17T11:25:19.281-05:00If anything it's harder, in the sense that pro...<i>If anything it's harder, in the sense that problems solved in more abstract areas of math have<br />comparively trivial proofs (e.g. theorems in algebraic geometry are usually much simpler to prove, once their meaning have been deciphered, than in number theory or combinatorics).<br /></i><br /><br />I think the problem is that a typical TCS grad student (say) approaches problems of considerable mathematical difficulty without an adequate training in core mathematics (algebra, geometry, analysis, topolgy etc.). This puts him or her at a disadvantage compared to someone who has a sound undergraduate/graduate training in math. The subsequent struggle and often re-discovery of many mathematical concepts that happens is exemplary effort, but the mathematical advance made is not commensurable to the effort expended. At the same time it might look that mathematical research is comparatively easier -- but this is made possible because of the considerable background baggage that mathematicians carry with them all the time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35391905735175166812010-08-17T10:53:22.850-05:002010-08-17T10:53:22.850-05:00Actually, the typical reading list for a graduate ...<i>Actually, the typical reading list for a graduate student in algebraic geometry has more mathematical depth and content (not to mention current research) than all STOC/FOCS proceedings taken together.</i><br /><br />I'm sure I could conjure more hyperbole than anyone else in the entire history of the human race could ever match and that will ever come in the future even if the universe lasts for an infinite amount of time if I tried too.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12707612795180222512010-08-17T10:46:25.259-05:002010-08-17T10:46:25.259-05:00An average mathematician most probably woudln'...<i><br />An average mathematician most probably woudln't be able to get a paper at STOC after several months'<br />worth of research, even having the right background. <br /></i><br /><br />This is a completely pointless debate. Most authors of<br />STOC/FOCS papers do not consider themselves as mathematicians (most of them are not even in math departments). Similarly, for most mathematicians writing STOC/FOCS papers will seem a pointless exercise. Aside from questions of relevance and recognition, mathematicians write their papers when they think they have something substantial to say (not because a deadline is looming). Of the tiny fraction of FOCS/STOC that are relevant to mathematics, the quality is uneven. Some are publishable in good math journals, the others are not -- but this should not be a measure of quality of these conferences or papers presented there in the first place.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24217367658102239112010-08-17T10:19:59.403-05:002010-08-17T10:19:59.403-05:00theorems in algebraic geometry are usually much si...<i>theorems in algebraic geometry are usually much simpler to prove, once their meaning have been deciphered, <br /></i><br /><br />Ever try to read Hironaka's proof of resolution of singularities or for that matter the EGA and SGA. Actually, the typical reading list for a graduate student in algebraic geometry has more mathematical depth and content (not to mention current research) than all STOC/FOCS proceedings taken together. Moreover, the anon comment was referring to the "mathematical content" of the papers. Most FOCS/STOC papers have zero math content -- a few (probably less than 5%) have a positive amount. But outside a few outstanding examples most of them will get a very short shift in a (general) math journal of any repute. Just try submitting such a paper if you do not believe me.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45227188411457893582010-08-17T10:12:41.470-05:002010-08-17T10:12:41.470-05:00The problems that most TCS people go to mathematic...<i>The problems that most TCS people go to mathematicians for help involve questions that have been in all likelihood studied in much more generality by someone ages ago<br /></i>This is ridiculous. Do you have an example? Even if this is true, it means nothing that a healthy exchange of ideas from different<br />areas is helpful to solve problems. If you are an algebraic geometer and somehow need to solve a problem in number theory, tell it to a<br />number theorists and solves it right away, does it mean whatever work you're doing is trivial? This<br />is the same. Surely if you came up with an algorithmic or tcs-flavoured problem in your research,<br />CS people would solve it much more easily, due to different backgrounds. So what?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87081498523993557372010-08-17T10:09:39.635-05:002010-08-17T10:09:39.635-05:00Care to elaborate? The questiones tackled in TCS a...<i><br />Care to elaborate? The questiones tackled in TCS and the work done are every bit as deep and hard as in any other area of pure math.<br /></i><br /><br />Elabortion. I am in complete agreement with your statement. However, unlike pure mathematicians who actually grapple with their problems at hand making tiny, painful but at least positive progress, most (not all) TCS experts seem to veer off into "profitable" areas such as economics, markets and what not, and seem to use the deep problems in the field that you refer to, merely for cheap sensationalism (for generating funding perhaps). <br />Thats the major difference in my opinion.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59138128067002008792010-08-17T10:06:24.442-05:002010-08-17T10:06:24.442-05:00Most mathematicians would perhaps consider the typ...<i><br />Most mathematicians would perhaps consider the typical mathematical content of the top FOCS/STOC paper as an honest day's labor</i><br /><br /><br />This is an example of astonishing arrogance. You might be an algebraic geometrer (so what), but clearly have no idea what you're taling about. Claiming that a FOCS/STOC paper is an day's labour is totally absurd.<br /><br />Unless "most mathematicians" simply means "top-rate mathematicians", you're not making any sense. An average mathematician most probably woudln't be able to get a paper at STOC after several months'<br />worth of research, even having the right background. I suggest you learn some TCS before writing<br />such bullshit, some of the most beautiful pure mathematics is there, and it is in no way easier.<br />If anything it's harder, in the sense that problems solved in more abstract areas of math have<br />comparively trivial proofs (e.g. theorems in algebraic geometry are usually much simpler to prove, once their meaning have been deciphered, than in number theory or combinatorics).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66169089837575385802010-08-17T09:58:55.664-05:002010-08-17T09:58:55.664-05:00Completely agree with anonymous 21.
The posts and...Completely agree with anonymous 21.<br /><br />The posts and discussions at Lipton's blog were a pinnacle of complexity theory being discussed on the web. People were actually debating ideas and learning and educating each other about finite model theory, the space of solutions of random k-SAT, "polylog parametrizability", how to write better proofs, the future of peer review and many more interesting tangents.<br /><br />Meanwhile Aaronson was noticeably rude and dismissive, adding little of substance to the discussion but apparently having plenty of time to post several posts and dozens and dozens of comments defending his "bet."<br /><br />At least Fortnow had the decency to stay quiet until it was all over.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39393328353447116252010-08-17T09:51:13.976-05:002010-08-17T09:51:13.976-05:00Somehow, the pure mathematicians who grapple with ...<i>Somehow, the pure mathematicians who grapple with problems several orders of magnitude deeper, seem to have no shortage of time "</i><br /><br />Care to elaborate? The questiones tackled in TCS and the work done are every bit as deep and hard as in any other area of pure math.<br /><br />On the other hand, I don't understand the criticisms. A glance at the paper shows that it's not a seriously written paper, just some vage ideas stapled together with no proper definitions and proofs. Of course it is a wortwhile task to try to see if any of the ideas can be salvaged, but the fact still remains that the hype over this paper was unjustified. It was clear from the outset that it would not lead to a correct proof without major work.<br /><br /><i><br />In any case, the chances that the P/NP problem if solved will be solved by people outside the STOC/FOCS community (to which Fortnow and Aaronson belongs) seems to be a pretty good bet to me <br /></i><br />This is again nonsense, you seem to think as if the people in other areas of math were smarter, which is far from the truth. Sure, Tao and Gowers have been awarded Field medals and are insanely smart, but there are also incredibly bright people active in TCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27042873978789565842010-08-17T09:20:52.475-05:002010-08-17T09:20:52.475-05:00To be fair, Neil Immerman, Ken Regan and Lipton hi...<i>To be fair, Neil Immerman, Ken Regan and Lipton himself adhered to the level expected in an academic discussion. </i><br /><br />Of course. I wasn't talking about them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47988671170428574092010-08-17T09:10:06.301-05:002010-08-17T09:10:06.301-05:00I wonder how many of the commenters have actually ...<i>I wonder how many of the commenters have actually spent time in a math department - talking to the algebraic geometers, for example...<br /></i><br /><br />I have.<br /><br />Mathematicians (most of them in my experience) are in fact quite friendly and helpful provided you approach them with the right attitude. The problems that most TCS people go to mathematicians for help involve questions that have been in all likelihood studied in much more generality by someone ages ago (even if the particular statement one would like to have has not been stated and proved). So the main problem is understanding the theory and applying it to the specific situation. Mathematicians tend to get annoyed when such matters are then blown up and published with bombastic claims. Most mathematicians would perhaps consider the typical mathematical content of the top FOCS/STOC paper as an honest day's labor, but would not dream of making a paper out of it. This causes the friction which some TCS people interpret as "arrogance".Anonymousnoreply@blogger.com