tag:blogger.com,1999:blog-3722233.post8153684617637338947..comments2023-03-29T09:38:56.563-05:00Comments on Computational Complexity: Conventional WisdomLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-3722233.post-55998297505983609852009-03-03T16:26:00.000-06:002009-03-03T16:26:00.000-06:00A proper definition has no scope of confusion and ...<I>A proper definition has no scope of confusion and does not need examples. How would we define TCS community? People like Karp, Fortnow etc? A person could actually be doing CS research without we, so called, TCS folks including Karp, Fortnow recognizing it. If that person finds some useful computational structure, that would be CS.</I><BR/><BR/>The definition that you quoted at the top has no examples. You might or might not agree with the definition, but teh definition is pretty well-defined (and I didn't have in mind FOCS or STOC when I wrote it). Defining a subject to be about everything under the sun is a sure guarantee for shallow research. Take your favorite mathematical discipline -- say real analysis or algebraic topology. While modern day papers on these topics would be absolutely incomprehensible to the founders of the field, it is not because these subjects have expanded their scope -- rather they have burrowed deep and discovered the jewels. The real analysts of today investigate the same real numbers as did Euler and Cauchy, not some new fangled sociological version of it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35146635546595513942009-03-03T12:02:00.000-06:002009-03-03T12:02:00.000-06:00>>> My definition of Theoretical CS woul...>>> <I> My definition of Theoretical CS would be the following. Theoretical CS is a part of mathematics which studies effective methods of computation, including models of computation, complexities of algorithms, lower bounds, as well those parts of logic which are related to computation such as recursive function theory. </I> <<<<BR/><BR/>This seems like the definition of the current focus of stoc/focs. With this definition, algorithms is already only half TCS and at this rate may cease to be called TCS in some future point.<BR/><BR/>The community changes, the conference agenda changes, but the broadest scope of the field remain the same. For an example, TCS did not have as much focus on game-theory as it is today. So it was not TCS earlier and now it is? I think at some point we will see computational aspects of sociology become TCS. The reason is that people have started using computers in their daily social lives.<BR/><BR/>A field is being pursued by another community does not redefine the field. During my high school, there were several chapters common to both physics and chemistry, and some were even common with biology.<BR/><BR/>A proper definition has no scope of confusion and does not need examples. How would we define TCS community? People like Karp, Fortnow etc? A person could actually be doing CS research without we, so called, TCS folks including Karp, Fortnow recognizing it. If that person finds some useful computational structure, that would be CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8974729982576876632009-03-03T09:51:00.000-06:002009-03-03T09:51:00.000-06:00and I doubt whether they would care too much about...<I>and I doubt whether they would care too much about what TCS has to say about computations.</I><BR/><BR/>They do so at their own peril. Time has shown that fields which neglect the tools of efficient algorithms are ripe for a take over by a more formal approach. I can think of at least three major fields who were in the dark ages until they started using algorithmic techniques (as defined by TCSers).<BR/><BR/><I>In any case they are closer to "algorithm research" than<BR/>most TCS people.</I><BR/><BR/>I don't necessarily disagree, but you have to keep in mind that this might be a reflection of the people you move around. In his blog, Muthu wrote that all his algorithms friends are motivated to a certain degree by applications. Lance here wrote nearly the exact opposite. Neither is wrong or right, it just reflects different flavors of research within TCS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38952147195202844512009-03-02T14:59:00.000-06:002009-03-02T14:59:00.000-06:00People who use algorithms to study "insect flights...<I>People who use algorithms to study "insect flights" define their field by the study of insects (entomology), so no, they are not algorithmicists.<BR/></I><BR/><BR/>Not at all. They are (and they call themselves) "computational mathematicians", and their goal is mainly to study and implement efficient algorithms for solving pdes, large scale eigen-value problems etc. They often apply their algorithms for understanding the real world. These researchers are mostly ignorant about TCS and I doubt whether they would care too much about what TCS has to say about computations. Sometimes (though rather rarely) these worlds intersect -- a case in point being the topic of semi-definite relaxations -- and then there are very interesting developments. But by and large these areas are insulated from each other. My point is that computational mathematicians rarely make bombastic claims about their field, though they are in a much better position to do so. In any case they are closer to "algorithm research" than <BR/>most TCS people.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20426768718488253322009-03-02T14:34:00.000-06:002009-03-02T14:34:00.000-06:00The theoretical CS community as we know it today d...<I>The theoretical CS community as we know it today developed from the discrete end of the optmizimation spectrum.</I><BR/><BR/>You are confusing the community with the subject of study. Where exactly people currently reside is a property of the community, what are the subjects of study is what defines the area.<BR/><BR/>TCS is the study algorithms & complexity & logic, wherever and whenever they appear. People who use algorithms to study "insect flights" define their field by the study of insects (entomology), so no, they are not algorithmicists. They do that on the side, as a means to an end. <BR/><BR/>TCS in contrast is the sole subject that claims the study of the processing of information by mechanical means.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75666051529114439912009-03-02T11:46:00.000-06:002009-03-02T11:46:00.000-06:00CS is exploration of the computational structure o...<I>CS is exploration of the computational structure of the real world, and TCS has an additional adjective "mathematics". </I><BR/><BR/>The people who actually try to understand the real world (or natural phenomena) through computations -- such as the atmospheric patterns, ocean currents, insect flights, blood flows in the heart, etc. -- are rarely in CS departments, leave alone theoretical CS. They publish in journals such as SIAM J. of Opt., Math Comp., Math Prog.,<BR/>FoCM etc. and their community is many times larger than theoretical CS. <BR/><BR/>The theoretical CS community as we know it today developed from the discrete end of the optmizimation spectrum. It has no doubt developed into an important subject with many interesting connections. But one cannot define TCS as it currently exists as "the study of the computational structure of the real world" without sounding ridiculous. In fact researchers who are in fact involved in such endeavours are only vaguely aware of TCS, and for most parts they do not consider it as important in their research.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24309572455558867362009-03-02T10:48:00.000-06:002009-03-02T10:48:00.000-06:00Propose your own definition, if you like discussio...<I>Propose your own definition, if you like discussion. Logic falls into mathematics. The proof of algorithms, fall into mathematics. </I><BR/><BR/>My definition of Theoretical CS would be the following. Theoretical CS is a part of mathematics which studies effective methods of computation, including models of computation, complexities of algorithms, lower bounds, as well those parts of logic which are related to computation such as recursive function theory.<BR/><BR/>Some of what is studied by theoretical computer scientists have potential applications and are used by practitioners in other areas. But these applications by themselves do not belong to the subject.<BR/><BR/>All aspects of algorithms (including complexities of algorithms and heuristic <BR/>algorithms) have been studied by mathematicians since anciemt times -- think Euclid, Archimedes, Gauss, Riemann, Hilbert, Tarski, Post, Markov, Godel et al. Thus, the study of algorithms as well as models of computation have been an intrinsic part of the interests of mathematicans. The new aspect introduced by theoretical CS might be the study of lower bounds, but here also mathematicians such as Godel<BR/>were interested in these questions long before TCS came into being. <BR/><BR/><I>An algorithm without proof (aka heauristic) does not fall into mathematics. </I><BR/><BR/>Not so. Heuristic algorithms have always been considered very important by mathematicans (such as Gauss, Riemann etc.) Otherwise, we won't have the Riemann hypothesis for instance. Currently, the journal "Experimental Mathematics" is devoted to investigations using heuristics.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22759237821859418282009-03-02T10:19:00.000-06:002009-03-02T10:19:00.000-06:00Logic etc are computations too and they are mathem...Logic etc are computations too and they are mathematical in nature. Algorithms are used by all branches of CS, whether threotical or not, but they become theoretical if they come with a theorem, that is a mathematical treatment with them.<BR/><BR/>I am not sure which high school you went too, but when our science class was divided into three different classes, physics, chemistry, and biology, the very first chapter/lecture was on the definition.<BR/><BR/>CS is exploration of the computational structure of the real world, and TCS has an additional adjective "mathematics". Honestly speaking, neither I have seen nor I can't think of a shorter and more appropriate definition of CS and TCS. Propose your own definition, if you like discussion. Logic falls into mathematics. The proof of algorithms, fall into mathematics. An algorithm without proof (aka heauristic) does not fall into mathematics. Most of the CS deals with algorithms, and we would be short minded if we do not recognize it. They have some level of mathematics too, but that's not a required component of CS.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75898204512235608522009-03-02T07:46:00.000-06:002009-03-02T07:46:00.000-06:00TCS is the mathematical exploration of the, comput...<I>TCS is the mathematical exploration of the, computational structure of the real world.</I><BR/><BR/>That's complexity. You are forgetting logic and algorithms. Algorithms is the study and <I> design</I> of computational methods. <BR/><BR/>For logic, I'll let a computational logician best describe it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61150907228699212132009-03-02T07:16:00.000-06:002009-03-02T07:16:00.000-06:00If we define TCS succintly, then I would say that,...<I>If we define TCS succintly, then I would say that, TCS is the mathematical exploration of the, computational structure of the real world.</I><BR/><BR/>This statement reminds me of my high school economics textbook which spent ten pages trying to justify why economics is a "science". I remember noting that my physics, chemistry, biology or math books had no need for such elaborate justifications. Such<BR/>vauntedexaggerated descriptions are typical of shallow disciplines -- are most often untrue and should not be made.<BR/><BR/>Theoretical computer science is a young developing sub-area of mathematics which has been the source of many interesting problems and connections with other areas of mathematics and science. It does not need (nor deserves) such exaggerated descriptions which devalues its intrinsic worth.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91931569198050857552009-03-02T03:56:00.000-06:002009-03-02T03:56:00.000-06:00Individual mathematics grants are typically smalle...<I>Individual mathematics grants are typically smaller than the standard CS grant, but is more than enough to support a research program in a pure topic such as P/NP.</I><BR/><BR/>If you are willing to take substantially less grad students that is. I've seen figures from other countries and there is a factor of two or more between TCS and math grants. <BR/><BR/><I>If you talk about great practical benefits, but the practitioners don't back you up when asked, then you'll get almost no funding. That's the situation TCS is in right now.</I><BR/><BR/>Yes, which is why we need more fanciful essays highlighting the applications of theory. We also should be welcoming of papers on "<I>novel</I> application of TCS in field X" even if the technical difficulty isn't that great (notice the emphasis on novel, though).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75747017399021352092009-03-01T22:34:00.000-06:002009-03-01T22:34:00.000-06:00I think TCS itself has a lot of applications, than...I think TCS itself has a lot of applications, thanks to Moore's law which seems to be applicable in many fields. The typical results in theory tend to hold for large numbers especially in the presence of unknown uncertainty (i.e., adversarial model). These days we get both the large numbers and uncertainty in many areas related to internet, computational biology, economics etc. Moore's law enabled us to do deal with the large number of objects, and therefore we need mathematical understanding behind the structures of these objects. Understanding these objects without the help of mathematical tools would be very hard.<BR/><BR/>So in some sense, we as a community need to sell the vision and ambitions of TCS at the highest level of budget allocations. Of course specific grants could explain further specific applications, but in an ideal world, specific grants should not be bending backwards in terms of explaining the applications. That should even more true with the papers. (I see this when a referee tries to be a better judge than authors in terms of visualizing the future applications.) <BR/><BR/>Most of the computer science explore the computational structure of the real world. If we define TCS succintly, then I would say that, TCS is the mathematical exploration of the computational structure of the real world.<BR/><BR/>When this is understood by NSF representatives, then we do not need to sell TCS every now and then. I would say that NP <> P is the most fundamental question in undertanding the computational mathematics of the real world (under classical mechanics and, so far, as well as under quantum mechanics). One need not ask for an immediate application of it. For an example, in case NP = P, even if the first algorithm is N^trillion, it is still useful since this trillion could potentially be brought down.<BR/><BR/>Similarly if NP != P, then also it is useful as people may likely to improve it to exponential running time, therefore potentially creating a provable security against adversaries, among various other potential applications.<BR/><BR/>Usually development in basic understanding of anything as broad as computation is likely to open the doors to revolutionary applications, which unfortunately we can't even dream about today. <BR/><BR/>Not many could have dreamed about what computers/internet would be used for today, 30 years ago. Nobody could have dreamed about the use of electricity before its invention. NP<>P has not yet proven because we do not yet understand what is a unit of computation. We only know it syntactically. So it is likely that instead of getting the applications from the theorem itself, irrespective of how it resolves, we get the applications from the proof. Because the proof is likely to explain something as fundamental as a unit of computation semantically.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10733341695595532532009-02-28T14:41:00.000-06:002009-02-28T14:41:00.000-06:00Not talking about the benefits to society is a sur...<I>Not talking about the benefits to society is a sure path to reduced funding. </I><BR/><BR/>Yes, but there's a local minimum in the middle. If you demonstrate real benefits today, you'll get a lot of funding. If you demonstrate no concrete benefits but talk about beauty and laying the foundations for future science, you'll get a little funding. If you talk about great practical benefits, but the practitioners don't back you up when asked, then you'll get almost no funding. That's the situation TCS is in right now.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67859278793422185992009-02-28T08:34:00.000-06:002009-02-28T08:34:00.000-06:00On the P vs NP question what our lack of progress ...<I>On the P vs NP question what our lack of progress might suggest most is the independence of the question. </I><BR/><BR/>Is there really any solid reason to believe in the independence of the question other than the lack of progress ?<BR/>I believe that people had speculated about such independence results for other famous number theoretic questions before the advent of new technologies led to their solutions. <BR/><BR/>Also as an "informed outsider" I have often wondered how well theoretical CS researchers understand the power of polynomial time algorithms (for instance, those that follow as <BR/>existence results from Robertson-Seymour graph minor theorems). Is there really any solid reason to believe the P \neq NP conjecture, when most (probably all) clever polynomial algorithms <I>designed </I> so far have complexity smaller than $O(n^{100})$ ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13375540700333193202009-02-28T07:48:00.000-06:002009-02-28T07:48:00.000-06:00Math collects a pittance in funding as compared ev...<I>Math collects a pittance in funding as compared even to TCS. </I><BR/><BR/>This is a common misperception. Most research active math faculty at R1 universities have NSF support, including those working in pure mathematics. Individual mathematics grants are typically smaller than the standard CS grant, but is more than enough to support a research program in a pure topic such as P/NP. NSF support in mathematics seems to be more equitably distributed, through funding postdocs, VIGRE, various math institutes meant to support the whole community. CS funding seems more individual oriented and superfically larger.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87938893670612591812009-02-28T03:07:00.000-06:002009-02-28T03:07:00.000-06:00Anon 3 is misguided. The only reason physicist cou...Anon 3 is misguided. The only reason physicist could ask in the past for billions of dollars in the quest of elusive particles was the potential applications for atomic weapons. When the cold war came to an end, the search for particles was hit the hardest among all sciences in terms of funding.<BR/><BR/>Math collects a pittance in funding as compared even to TCS. Not talking about the benefits to society is a sure path to reduced funding. <BR/><BR/>A principled stand about the intrinsic beauty and elegance of what we do might make us feel better but will not bring a red cent of funding to TCS. We need more not less "fanciful essays" explaining to the taxpayers who pay our bills why the should fund us instead of the millions of Ty'Sheoma Betheas out there.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26849531487059032162009-02-27T20:17:00.000-06:002009-02-27T20:17:00.000-06:00Richard Lipton's blog is great because it gives pe...Richard Lipton's blog is great because it gives perspectives on important problems of the field that used to be part of the mix of give and take but have been forgotten over the generations of researchers.<BR/><BR/>On the P vs NP question what our lack of progress might suggest most is the independence of the question. What if that is what we learn? Would it have been worth it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55755566320165522762009-02-27T18:24:00.000-06:002009-02-27T18:24:00.000-06:00But my main concern is that the most likely outcom...<I>But my main concern is that the most likely outcome of such a project would be no significant progress towards settling the P v. NP problem in either direction, potentially making some proclaim the project a "failure". We have a theory-friendly NSF now but that won't last forever and I would hate to hand future NSF leaders any ammunition against theory funding.</I><BR/><BR/>Lipton should be complimented for taking the unpopular stand that the research in the central questions of computer science should attract funding without having to write fanciful essays about the "benefits to society of TCS" that theoretical computer scientists are so fond of writing these days. Pure mathematicans are not reluctant to pursue programs central to their subject (Riemann Hyp, Hodge Conjecture, the Langlands program Poincare problem etc.), theoretical physicists can ask for billions to search for illusive particles. Why should theoretical CS people not be funded if they want to pursue the P/NP problem ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74918124588555829272009-02-27T12:00:00.000-06:002009-02-27T12:00:00.000-06:00which have we made more progress on- showing P=NPo...which have we made more progress on- showing P=NP<BR/>or showing P\ne NP?<BR/>There are some fast algorithms for problems we didn't think had fast algorithms (FPT stuff,<BR/>Holographic algorithms),<BR/>and some collapses of classes<BR/>(NL=co-NL and the PCP theorem). This could be progress towards P=NP.<BR/><BR/>Lower bounds on circuits<BR/>and time-space tradeoffs for<BR/>SAT- these could be progress towards P\ne NP.<BR/><BR/>So, we've made more progress towards P=NP.<BR/>To bad P\ne NP so that progress is for naught.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90422392720895860882009-02-27T06:29:00.000-06:002009-02-27T06:29:00.000-06:00Interesting...In a recent discussion on circuit lo...Interesting...In a recent discussion on circuit lower bounds a well-known researcher told me that he believes it is likely that NP is in P/poly, and part of the problem is a "groupthink" mentality where everyone is too focused on trying to prove the opposite.Anonymousnoreply@blogger.com