tag:blogger.com,1999:blog-786333285568106173.post2269133418350801288..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: What is efficient?Mihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-786333285568106173.post-22842306289861060502009-09-12T10:51:29.521-04:002009-09-12T10:51:29.521-04:00While one agree or disagree with some of your obse...While one agree or disagree with some of your observations, the discussion about where TCS is going is valuable in itself. Arguably, at certain points in time AI and DB worked themselves into tight corners to the detriment of progress, jobs and funds there.<br /><br />We should routinely ask questions such:<br /><br />why are we doing complexity? <br />why algorithms? <br />why data structures? <br />why approximation algorithms? <br />why differential privacy?<br /><br />What is their connection to the real world: direct/indirect/none? <br /><br />Is the sub-field justified? if so are we asking the right questions, i.e., are we setting out a program which, if successful, will lead to big gains or are we mostly running around in circles proving irrelevant variations on results?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-26898573200482619392009-09-10T09:35:23.508-04:002009-09-10T09:35:23.508-04:00No offense meant, but I find arguments in your pos...<i>No offense meant, but I find arguments in your post somewhat shallow. In fact, I gave up reading the post after I was done reading about 70-75% of it...</i><br /><br />No offense meant, but writing that something is shallow, you didn't even read it, and you have nothing in particular to say about it --- that's quite the definition of shallow :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-71174435283005460812009-09-10T09:33:49.239-04:002009-09-10T09:33:49.239-04:00Maybe I am mathematical computer scientist, but I ...<i>Maybe I am mathematical computer scientist, but I think a work that reveals the structure of the problem (say ARV) is better than a paper containing an improvement from O(n log n) to O(n) for the problem of finding the longest multipermutation. My guess is that in the long run, the former would have much more impact on the real world than the former.</i><br /><br />The multipermutation problem is an <i>algorithmic exercise</i>, something that you may solve to keep your mind fresh. Nobody is promoting that as serious science.<br /><br />Sparsest cut is certainly an important problem. Since you bring that up: (1) approximating this problems makes much more sense than your average problem; (2) we still don't know an algorithm with theoretical guarantees that matches things like METIS; (3) if you are going to lay out chips at Intel, you are never going to afford a quadratic algorithm, making my point that you always want faster running times.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-71292542356518456532009-09-10T09:27:58.049-04:002009-09-10T09:27:58.049-04:00@daveagp:
I would be really interested to hear yo...@daveagp:<br /><br /><i>I would be really interested to hear your perspective on whether what I have seen also occurs in your area of expertise, whether a significant fraction of the best papers come out of carefully applying one simple new technique or a certain ordering of known techniques.</i><br /><br />The best papers are certainly the ones that have one crisp idea that makes everything possible. Other good papers rely on a combination of known ideas. This is often much harder to quantify, but in time (with examples) the way of putting things together becomes a technique in itself.<br /><br /><i>Also let indulge my inner troll and say that making claims on which theory subfield is the closest to applications is a little like millionaire rappers debating which one's the gangsta-est</i><br /><br />Your opinion is certainly common among young TCS folk. I've heard things like "this is a sport", "we're really mathematics with a better excuse for getting money" etc etc.<br /><br />The reason I prefer TCS over mathematics is that it is a deep theoretical study of something real. If we stopped caring about the connection to reality, (for me) it would be a disaster.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-48287238475674940292009-09-10T09:20:26.329-04:002009-09-10T09:20:26.329-04:00Mihai, I presume you grant that time is not the on...<i>Mihai, I presume you grant that time is not the only interesting algorithmic resource or objective?</i><br /><br />Sure. But you grant that some are less interesting and meaningful than others. (Eg, running time on a Turing machine is certainly an objective, but not one I will work on.)<br /><br />Judging based on my own understanding and taste of computation, focusing on approximation <i>often</i> (i.e. certainly not always) generates uninteresting computational questions. <br /><br />Look, half the questions there are "how much do we need to relax this before the space of solutions become convex?" <br /><br /><i>Well, the reason one can beat backtracking for some other problems (pick your favorite dynamic programming example) is that they do exhibit a lot of structure.</i><br /><br />For the record, I am a big fan of dynamic programming, and I'm disappointed that our community didn't have too much to say about it.<br /><br /><i>Isn't understanding these problems, their phase transitions and how one can solve them, part of the algorithms and complexity that we're "supposed to do"?</i><br /><br />I promise to return to this issue, but for now let me say that you can find algorithms and phase transitions everywhere. This doesn't make them all interesting or important.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-3598453370162745272009-09-06T08:15:48.403-04:002009-09-06T08:15:48.403-04:00Mihai,
No offense meant, but I find arguments in ...Mihai,<br /><br />No offense meant, but I find arguments in your post somewhat shallow. In fact, I gave up reading the post after I was done reading about 70-75% of it...<br /><br />It seemed to me that you ended up writing more text about a pre-formed opinion rather than a well-thought and conclusive argument about why thinking P as class of "efficient" algorithms is a bad philosophy. Once again, no offense meant, I do find quite a good fraction of your posts interesting :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-12936818906643593182009-09-05T18:13:59.766-04:002009-09-05T18:13:59.766-04:00(2) The most important *algorithmic* technique tha...<i>(2) The most important *algorithmic* technique that I teach my students is "understand the problem structure better".<br /><br />It's a great technique in geometry and graph theory, too :), and much work in approximation algorithm certainly uses it. Understanding the problem structure does not make an algorithm.<br /></i><br /><br />Actually, it does in many cases. In fact, it is imho, the only way to get a good algorithm. Think back about your favorite algorithms (matching? shortest paths? max flows?) and you would realize that understanding the structure is what leads to an interesting algorithm.<br /><br />Your remark is like saying that spinning cotton to make fabric does not make your boxers. It may be true in the literal sense: someone has to design those boxers, cut the garments, stitch them, etc.<br /><br />But then one can go a step further that designing a fast algorithm does not solve a problem. Someone has to code it up properly, and Intel has to make the chips that run that code without interference from cosmic rays, and Samsung has to make monitors to display the results, and I could go on and on.<br /><br />Maybe I am mathematical computer scientist, but I think a work that reveals the structure of the problem (say ARV) is better than a paper containing an improvement from O(n log n) to O(n) for the problem of finding the longest multipermutation. My guess is that in the long run, the former would have much more impact on the real world than the former.<br /><br />BTW, I am sympathetic to the argument that if everyone worked on making the fabric and no one knew how to make garments, it wouldn't be so good for the field. Maybe we are swinging too far to one side. But in approximation algorithms, the current time seems like a good time to be understanding structure and we may be right in concentrating our energies on that.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-48841258691243751572009-09-04T19:31:43.637-04:002009-09-04T19:31:43.637-04:00Also let indulge my inner troll and say that makin...Also let indulge my inner troll and say that making claims on which theory subfield is the closest to applications is a little like millionaire rappers debating which one's the gangsta-estAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-67172759167079904382009-09-04T19:11:06.124-04:002009-09-04T19:11:06.124-04:00Mihai, sure it is important to have diverse taste....Mihai, sure it is important to have diverse taste. Back in my frat days I did distributed algorithms, so I try to practice this in addition to preaching. I don't currently spend time following anything very closely outside approximation/LPs/combinatorial optimization though (depth/breadth tradeoff).<br /><br />I would be really interested to hear your perspective on whether what I have seen also occurs in your area of expertise, whether a significant fraction of the best papers come out of carefully applying one simple new technique or a certain ordering of known techniques.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-86671945432208352132009-09-04T18:28:11.666-04:002009-09-04T18:28:11.666-04:00Mihai, I presume you grant that time is not the on...Mihai, I presume you grant that time is not the only interesting algorithmic resource or objective? For example, space bounds are also interesting, right? <br /><br />If you like, as far as approximation goes, think of "solution quality" as just another objective function. One can ask for algorithms that run quickly, use small amounts of space, only a little randomness, a few rounds of communication, etc. People studying approximation are asking for algorithms that maximize solution quality, instead of minimizing time.<br /><br />And then there are tradeoffs between these objectives, such as between time and space. Does it not require an "understanding and appreciation of computation" to say that in quasi-polynomial time, I can give you an approximation scheme, in n^3 time, you can get a constant-factor approximation, and a linear-time greedy algorithm gives an O(log n) approximation?<br /><br />To second Noam's point, understanding problem structure is certainly algorithmically important. You said in the previous post that you found the question "Can you beat backtracking for the following list of problems?" fascinating. Well, the reason one can beat backtracking for some other problems (pick your favorite dynamic programming example) is that they <b><i>do</i></b> exhibit a lot of structure. Without understanding that, as you probably agree, one wouldn't be able to design good algorithms. <br /><br />And even the NP-complete problems have very different structures. Knapsack can be solved arbitrarily well, and Clique is basically hopeless in general graphs. A simple greedy algorithm gives a ln n approximation for Set Cover, and no polynomial time algorithm can do any better! Do you not think it interesting from an algorithmic perspective to know that some problems can be solved nearly optimally in close to linear time, while others can't be solved at all in n^10 time? <br /><br />In fact, I agree with your comment about interesting behavior occurring at phase transitions; that's exactly right! Phase transitions of this type occur all the time in approximation algorithms; it's just that the relevant variable is not always time. For instance, Set Cover has a very interesting transition around the ratio of ln n. A very simple algorithm gives a 2-approximation to Vertex Cover, but doing <i>any</i> better seems remarkably difficult. Knapsack, by contrast, exhibits no such transition, with a smooth tradeoff between time and solution quality. Isn't understanding these problems, their phase transitions and how one can solve them, part of the algorithms and complexity that we're "supposed to do"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-39984078742018673622009-09-04T13:25:14.192-04:002009-09-04T13:25:14.192-04:00Obelix, I love the term "mathematical compute...Obelix, I love the term "mathematical computer science." I would be much happier to classify, say, property testing as mathematical computer science than theoretical computer science.<br /><br />Dave, it is exactly people like you that I'm trying to change :) As you say yourself, you have little experience with the other fields, which leads to little appreaciation of algorithmic work in those fields.<br /><br />Membership in P is neither interesting nor useful for very many problems.<br /><br /><i>Also, approximation algorithms is reasonably close to real-life problems overall, </i><br /><br />It is much more removed from real life than exact algorithms. There are quite a few success stories of exact algorithms in real life. Most success stories of approximation algorithms come from the OR community, not us --- and they do a different flavor of work. <br /><br /><i>Also, randomly, Mihai, are you doing Code Jam this year?</i><br /><br />By doing code jam, do you mean compete? I haven't really taken part in any contests after high school, and I intend to keep it that way :) First of all, I am too old :) More importantly, contests beyond high school test coding too much --- I am a reasonable coder, but not a fast one. At IOI this was never a problem.<br /><br />I have and do participate in scientific committees though.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-85926457788647076232009-09-04T13:16:10.337-04:002009-09-04T13:16:10.337-04:00Not that clear, there are results showing that str...<i>Not that clear, there are results showing that strong hardness of SAT implies some hardness for problems that are in P.</i><br /><br />If you look at the very recent list of SODA accepted papers, you will notice that I am quite familiar with this direction :)Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-15487901970480759042009-09-04T12:06:57.366-04:002009-09-04T12:06:57.366-04:00No matter how liberally you interpret P vs NP, it&...<i>No matter how liberally you interpret P vs NP, it's not talking about computing max flows, or the edit distance, or reachability in dynamic graphs.</i><br /><br />Not that clear, there are results showing that strong (i.e. exponential) hardness of SAT implies some hardness for problems that are in P. (In particular I think peopled showed that then k-clique cannot be done in time n^{o(k)} ).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-39298578666036433362009-09-04T10:33:34.852-04:002009-09-04T10:33:34.852-04:00Noam:
(1) Most people working on the P=NP problem...Noam:<br /><br /><i>(1) Most people working on the P=NP problem don't take it literally as you seem to.</i><br /><br />I am probably missing the connection to what I wrote. No matter how liberally you interpret P vs NP, it's not talking about computing max flows, or the edit distance, or reachability in dynamic graphs.<br /><br /><i>(2) The most important *algorithmic* technique that I teach my students is "understand the problem structure better".</i><br /><br />It's a great technique in geometry and graph theory, too :), and much work in approximation algorithm certainly uses it. Understanding the problem structure does not make an algorithm.<br /><br /><i>(3) The point with approximation is to fix the *wrong* modeling of the word "solution" in the problem definition for algorithms: finding the "best" is usually the wrong formulation of what is desired -- "close to best" is more like it.</i><br /><br />I agree, but I think TCS is wrong in pushing this idea too much. Certainly, there's imprecision in the data and the modeling, so imprecision in the output is not a killer. But an exact solution never hurts anybody, if you can get it (it won't be an exact solution for your unmodelable real world problem, but it will be closer).<br /><br />And imprecision in the modeling is fine enough that Amazon is still happy about a 2% improvement (this is not wiped out by noise, presumably). On the other hand, you hear TCS people use this idea to justify a 2-approximation!<br /><br /><i>4) It's a bit strange to see Mechanism Design mentioned as a sub-branch of approximation algorithms. </i><br /><br />I yield to your opinion. I'm only repeating something that I heard from people in the area (that it often "feels" like approximation algorithms), though I perhaps misunderstood the connection.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-6698763642705324172009-09-04T10:22:18.585-04:002009-09-04T10:22:18.585-04:00Maybe I am picking the statements a bit out of con...<i>Maybe I am picking the statements a bit out of context but I hope you didn't tell the OR guy about your opinion on LP or SDP.</i><br /><br />Of course I did! Approximation people I've met do agree with this, though usually in a positive light ("that's exactly why papers like algorithmic developments like in the X paper are so exciting").<br /><br />Just to clarify, I think solving LP is a really cool problem. I'm just complaining about the unexciting algorithmic contents of many *applications* of LP.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-32970613597214229882009-09-04T01:36:13.357-04:002009-09-04T01:36:13.357-04:00If it's in P, it's good enough for me!
He...If it's in P, it's good enough for me!<br /><br />Here's part of my view on LP-based approximation algorithms, where I work mostly. A significant fraction of the best papers come out of carefully applying one simple new technique or a certain ordering of known techniques. Whether you think that is awesome or terrible is a matter of opinion. But from my perspective as a learner it is ideal, you are able to closely keep track of major developments, and build skills that complement each other. Maybe other sub-fields are the same way - I have little experience to speak of for any other one. <br /><br />Also, approximation algorithms is reasonably close to real-life problems overall, but that doesn't force the entire theoretical field to have practical running times.<br /><br />Also, randomly, Mihai, are you doing Code Jam this year? Have you found you are able to find enough time to do that stuff now that you have "a job" as they say?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-40535702346336746342009-09-04T01:24:29.701-04:002009-09-04T01:24:29.701-04:00...in which you can do fine without much understan...<i>...in which you can do fine without much understanding or appreciation of computation</i><br /><br />This is not just an issue with approximation algorithms but is the case in many other areas of TCS. <br /><br />Are we at a point where we could/should distinguish between "theoretical computer science" and "mathematical computer science"? Just like physicists distinguish between "theoretical physics" and "mathematical physics".Obelixnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-15627675717974486552009-09-04T00:48:30.366-04:002009-09-04T00:48:30.366-04:00A few comments:
(1) Most people working on the P=...A few comments:<br /><br />(1) Most people working on the P=NP problem don't take it literally as you seem to. The common interpretation is: "Either prove a super-linear lower bound or prove a sub-exponential upper bound (for circuits OR multi-tape TMs or RAMs in deterministic OR randomized OR quantum variants". The very very wide range that is open here is the point.<br /><br />(2) The most important *algorithmic* technique that I teach my students is "understand the problem structure better". This is what all these LP/SDP/rounding guys are doing. I don't see a reason to define this away from being algorithms. <br /><br />(3) The point with approximation is to fix the *wrong* modeling of the word "solution" in the problem definition for algorithms: finding the "best" is usually the wrong formulation of what is desired -- "close to best" is more like it. (The 2%-chasing OR friend should be an example.<br /><br />(4) It's a bit strange to see Mechanism Design mentioned as a sub-branch of approximation algorithms. Some MD papers use approximation, as does the rest of TCS, but beyond that there is no connection really.Noamhttp://agtb.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-9016524685339553972009-09-03T20:04:23.365-04:002009-09-03T20:04:23.365-04:00You can add that in the context of crypto going fr...You can add that in the context of crypto going from, say, a 2^n-time algorithm to a 2^{\sqrt{n}}-time algorithm for breaking a hard problem is a big deal...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-76833808459493556242009-09-03T18:50:47.942-04:002009-09-03T18:50:47.942-04:00"I am working with an OR guy, the kind of per..."I am working with an OR guy, the kind of person who teaches at Business School and spent significant time optimizing truck schedules for Amazon"<br /><br />"The only interesting algorithmic content is solving the LP or SDP, which few people really work on."<br /><br />Maybe I am picking the statements a bit out of context but I hope you didn't tell the OR guy about your opinion on LP or SDP.Anonymousnoreply@blogger.com