tag:blogger.com,1999:blog-3722233.post113110389476575453..comments2022-12-07T07:34:35.444-06:00Comments on Computational Complexity: Whither to CompeteLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1131417358416436842005-11-07T20:35:00.000-06:002005-11-07T20:35:00.000-06:00Most of the arguments here are about using worst-c...Most of the arguments here are about using worst-case analysis to evaluate approximation algorithms. I think another issue with the field of approximation algorithms is the fixation on the notion of "approximation factor". One example is spectral algorithms for finding a cut, which find cuts that are "close" to the optimal in the worst case (Cheeger's inequality), and are also known to perform well in practice, but are often ignored in any approximation algorithms course/textbook, just because they don't have a good approximation ratio (while at the same time, algorithms of approximation ratio sqrt{n} are sometimes taught in classes).Mohammad Mahdianhttps://www.blogger.com/profile/08220570157337874429noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131158463082607712005-11-04T20:41:00.000-06:002005-11-04T20:41:00.000-06:00Darn! I guess my submission on the stochastic dyn...Darn! I guess my submission on the stochastic dynamic traveling dog and pony problem with piecewise linear costs isn't getting into STOC.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131146138759946352005-11-04T17:15:00.000-06:002005-11-04T17:15:00.000-06:00Yes, nice post. I would like to mention another cr...Yes, nice post. <BR/><BR/>I would like to mention another criterion that is often used in this context.<BR/><BR/>5. Historical argument. Many central problems in approximation algorithms (clique, coloring, maxcut) have been investigated for quite a while in TCS/CS. Actually, these are often the same problems that were mentioned to score high on criterion (1), so one can conjecture some causality here. <BR/><BR/>However, there is also the "algorithmic" question: how to <EM>test</EM> if a problem satisfies (1)..(5). <BR/><BR/>1. Beauty: It has been argued here that this one is easy to test case by case. <BR/><BR/>2. Classification/fine distinction: either a classification is known or not. Literature search should resolve the issue.<BR/><BR/>3. Real need to deal with ignorance about the input: not as easy due to our ignorance ;) Still, if more detailed models are widely accepted, one should be able to find them.<BR/><BR/>5. Problem age: lower bounds easy to get.<BR/><BR/>Now we are left with:<BR/><BR/>4. Beneficial spin-off.<BR/><BR/>This is, in my opinion, a heck of a problem. It essentially asks about the potential of an indirect future impact. And that is not an easy thing to estimate. <BR/><BR/>One can use heuristics, such as:<BR/><BR/>- beauty/originality (as in (1) )<BR/><BR/>- does the method overcome a significant obstacle<BR/><BR/>- past record of this line of research<BR/><BR/>- connections: the more, the merrier<BR/><BR/>and probably more. But in the end I think it is a judgement call. <BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131113424185982482005-11-04T08:10:00.000-06:002005-11-04T08:10:00.000-06:00"Stochastic" is out when mathematical beauty is th..."Stochastic" is out when mathematical beauty is the criterion? I am not so sure. It all depends on what is proved and how, and on what is revealed by the work.<BR/><BR/>Isn't it strange that mathematical beauty is so elusive to define, yet so easy to agree on on a case-by-case basis? We all recognise it when we see it, and I can't remember ever having arguments about it on any specific instance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131109291953280182005-11-04T07:01:00.000-06:002005-11-04T07:01:00.000-06:00Yes a nice post. There are severalpeople who engag...Yes a nice post. There are several<BR/>people who engage in competitive<BR/>analysis including myself who<BR/>are sceptical of the the export<BR/>business on game theory. One often<BR/>feels that known results from the past<BR/>are dressed up as new high impact results.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1131108690334245332005-11-04T06:51:00.000-06:002005-11-04T06:51:00.000-06:00Nice post!Nice post!Michael Mitzenmacherhttps://www.blogger.com/profile/00458446293652845258noreply@blogger.com