Tuesday, March 16, 2010
Repost on Turing and Wasserman- lets talk about...
One of the commenters on the post on the recent Turing Award and the Waterman award
pointed out that the context I gave lead to a discussion
that was NOT about the work of Chuck Thacker or Subhash Khot.
The commenter said:
Can you post this again without the additional context so that the community could write
some comments on their work
OKAY, consider it done.
Now, commenters, its up to you.
Subscribe to:
Post Comments (Atom)
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.
ReplyDeleteWhat 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.
ReplyDeleteAnon 2: UGC would imply that certain approximation algorithms can not be improved.
ReplyDeleteBroader impact depends on how important these algorithms are in practice.
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?
ReplyDeleteWhile 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? :)
ReplyDeleteIs 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?
ReplyDeleteThat 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.
dear anon 2.
ReplyDeletethere 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.
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).
if you ask me, even this specific example is a big deal.
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..
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.
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?
ReplyDeleteugc is a beautiful conjecture and the reductions from it are of no less importance as the reductions by karp to many problems from 3sat.
ReplyDeletethe primary difference is that 3 sat was provably a hard problem as a class of other problems reduced to it.
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.
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.
ReplyDeleteof course, for the same reason, i would like tim berners-lee to win the turing award too for conceptualizing the web.
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.
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.
btw, who did the first email? email is still by far the biggest use of the internet, far bigger than search.
matus, aren't you assuming that the conjecture is true?
ReplyDeleteExpander graphs are easy? Reference?
ReplyDeleteRay Tomlinson probably did the first network-based e-mail.
ReplyDeleteLen Kleinrock probably did the first personal-use text messaging live (to get his razor back).
matus--
ReplyDeleteI believe the algorithm you describe for Vertex Cover is actually a logn approximation.
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.
Anon responding to "matus", two errors in your comment:
ReplyDeleteMatus' 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.
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.
FractionalLP:
ReplyDeleteYou are right--I think if you follow Matus's algorithm and choose the vertices greedily (largest degree), then it is a log n approximation.
Give Matus and Kleinberg the Nobel prize, then.
ReplyDeleteoh 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.
ReplyDeleteMatus says ~"if UGC is true, then anyone who needs a vertex cover approx algorithm need look no further than the simple algorithm"~.
ReplyDeleteI 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.
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.
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.