tag:blogger.com,1999:blog-3722233.post2139918960277303111..comments2022-12-02T17:41:58.702-06:00Comments on Computational Complexity: Repost on Turing and Wasserman- lets talk about...Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-89042183832486328082010-03-20T14:59:18.287-05:002010-03-20T14:59:18.287-05:00Matus says ~"if UGC is true, then anyone who ...Matus says ~"if UGC is true, then anyone who needs a vertex cover approx algorithm need look no further than the simple algorithm"~.<br /><br />I don't buy it at all. It may be that there is no better algorithm whose worst-case approximation ratio is at most 2 in all cases. But there may well be algorithms that perform better on many graphs seen in practice.<br /><br />Think of SAT. There may be no general polynomial time algorithm, but there are still SAT solvers that work well on many formulas seen in practice, and they are incredibly important.<br /><br />I see this as one reason why people deride complexity theorists as disconnected from practice. I find it is common to over-state the practical relevance of these kind of theoretical results.AnonCSProfnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86481363099708778812010-03-18T00:27:02.432-05:002010-03-18T00:27:02.432-05:00oh goodness, i gave the algorithm wrong; select an...oh goodness, i gave the algorithm wrong; select any EDGE, put both endpoints into the cover, throw out every edge connected to those endpoints. This is a 2-apx because for any edge selected, optimal must have selected at least one endpoint, whereas this method took both.matusnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45686051574010318662010-03-17T11:17:39.873-05:002010-03-17T11:17:39.873-05:00Give Matus and Kleinberg the Nobel prize, then.Give Matus and Kleinberg the Nobel prize, then.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27625217835962320722010-03-16T22:40:42.548-05:002010-03-16T22:40:42.548-05:00FractionalLP:
You are right--I think if you follo...FractionalLP:<br /><br />You are right--I think if you follow Matus's algorithm and choose the vertices greedily (largest degree), then it is a log n approximation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86085412891209481852010-03-16T22:34:22.611-05:002010-03-16T22:34:22.611-05:00Anon responding to "matus", two errors i...Anon responding to "matus", two errors in your comment:<br /><br />Matus' algorithm is not a log n approximation, e.g., if the graph is a star with one central vertex and n-1 peripheral vertices (hub-and-spokes), and if the algorithm always picks a peripheral vertex, the ratio of alg. to optimal is n-1, not logn.<br /><br />In the matching-based algorithm you describe, you need to pick both endpoints of all edges in a maximal matching. This is clearly a vertex cover since an uncovered edge would contradict the maximality of the matching. The size of this vertex cover is no more than twice the best possible, since you need at least one vertex per matched edge.FractionalLPnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90570626008855537322010-03-16T21:50:15.489-05:002010-03-16T21:50:15.489-05:00matus--
I believe the algorithm you describe for ...matus--<br /><br />I believe the algorithm you describe for Vertex Cover is actually a logn approximation.<br /><br />To get a 2-approximation, one can find a maximal matching and take one vertex from each edge. Note that this is not what you are doing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32204186892425284162010-03-16T21:28:13.043-05:002010-03-16T21:28:13.043-05:00Ray Tomlinson probably did the first network-based...Ray Tomlinson probably did the first network-based e-mail.<br /><br />Len Kleinrock probably did the first personal-use text messaging live (to get his razor back).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85152728998295954762010-03-16T21:21:15.940-05:002010-03-16T21:21:15.940-05:00Expander graphs are easy? Reference?Expander graphs are easy? Reference?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2437624738506651822010-03-16T21:17:26.861-05:002010-03-16T21:17:26.861-05:00matus, aren't you assuming that the conjecture...matus, aren't you assuming that the conjecture is true?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60251535126917333712010-03-16T20:39:17.917-05:002010-03-16T20:39:17.917-05:00the concept of a modern pc is quite an achievement...the concept of a modern pc is quite an achievement and any single person whose scientific contribution has increased the chance of us having a computer age deserve the award.<br /><br />of course, for the same reason, i would like tim berners-lee to win the turing award too for conceptualizing the web.<br /><br />if we would like to be ahead of the curve, i think we should also consider awarding the first person or team who conceptualized a smart phone. this technology would turn out to be very important in the near future.<br /><br />i am not sure how much is the importance of page rank in search, but if it is significant then even the google folks should get the award. jon kleinberg got an award though his accomplishment was not even in the same league. if jon deserves nevalina then google folks deserve turing.<br /><br />btw, who did the first email? email is still by far the biggest use of the internet, far bigger than search.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-309067137553676392010-03-16T20:26:02.558-05:002010-03-16T20:26:02.558-05:00ugc is a beautiful conjecture and the reductions f...ugc is a beautiful conjecture and the reductions from it are of no less importance as the reductions by karp to many problems from 3sat.<br /><br />the primary difference is that 3 sat was provably a hard problem as a class of other problems reduced to it.<br /><br />ug on the other hand is provably an easy problem, as it reduces to many problems. for an example, ug is easier than finding a strictly better than factor 2 algorithm for vertex cover.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83426710384424239182010-03-16T19:28:06.735-05:002010-03-16T19:28:06.735-05:00A question: Isn't the hardness of expander gra...A question: Isn't the hardness of expander graphs were the main reason that people believed in UGC, now that we know it is not hard why would one in UGC?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1982540806702402722010-03-16T18:31:24.163-05:002010-03-16T18:31:24.163-05:00dear anon 2.
there is a simple 2-approx for vertex...dear anon 2.<br />there is a simple 2-approx for vertex cover: iteratively grab a vertex, and remove all attached edges from the graph. repeat until all edges are removed.<br /><br />under UGC, this is the optimal algorithm. thus, if someone ever needs a vertex cover, they know they don't have to look any farther than this simple algorithm. (there's also an LP relaxation with factor 2, and something else that gets 2-o(1), but asymptotically 2 has not been beaten ie ugc still open).<br /><br />if you ask me, even this specific example is a big deal.<br /><br />add to that the general importance of the results, what they say about combinatorial optimization (that for CSPs, integrality gap = inapproximability), all this crazy stuff..<br /><br />finally, an expert should weigh in here, but it seems to be one of the biggest single steps in the p=/=np relationship since the development of pcp. and p=/=np is our big problem/embarrasment.matusnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27004986792593433052010-03-16T18:31:05.857-05:002010-03-16T18:31:05.857-05:00Is awarding this the same as awarding a Nobel Peac...<i>Is awarding this the same as awarding a Nobel Peace Prize to a man who had been President for days and hadn't actually done anything but talk big?</i><br /><br />That is nothing compared to awarding the Nobel Peace Prize to unrepentant murderers such as Kissinger, Arafat (or a literary fraud such as Rigoberta Menchu), but for some reason American academic circles seem obsessed with the latest Nobel prize gaffe, which frankly pales by comparison.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27499763467726840712010-03-16T17:56:24.946-05:002010-03-16T17:56:24.946-05:00While on the topic of awards: the SIGACT Goedel aw...While on the topic of awards: the SIGACT Goedel award page is still requesting nominations for the 2008 award! Can we request the SIGACT chair to press on the relevant people? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31752959492928156202010-03-16T15:07:24.231-05:002010-03-16T15:07:24.231-05:00This is for a conjecture and further work on "...This is for a conjecture and further work on "if it happens to be true, then _______" questions? It could be false. Is awarding this the same as awarding a Nobel Peace Prize to a man who had been President for days and hadn't actually done anything but talk big?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30019810023859198092010-03-16T14:24:26.869-05:002010-03-16T14:24:26.869-05:00Anon 2: UGC would imply that certain approximation...Anon 2: UGC would imply that certain approximation algorithms can not be improved.<br /><br />Broader impact depends on how important these algorithms are in practice.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17841329490662421362010-03-16T14:11:33.570-05:002010-03-16T14:11:33.570-05:00What would you say is the impact of the "Uniq...What would you say is the impact of the "Unique Game Conjecture" on the world of computing? To an outsider it looks like a fair bit of mental masturbation.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14489925104919353172010-03-16T12:08:22.887-05:002010-03-16T12:08:22.887-05:00The first modern PC? You mean something with a mo...The first modern PC? You mean something with a mouse, hypertext, object addressing, dynamic file linking, multiple users communicating using networked A/V and sharing documents live? Wait, no, that was the "oN-Line System" in the 1960s.Anonymousnoreply@blogger.com