tag:blogger.com,1999:blog-3722233.post111986925595973118..comments2020-06-04T08:02:51.746-04:00Comments on Computational Complexity: The Unique Games ConjectureLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-82465995696418295792010-08-25T23:40:14.212-04:002010-08-25T23:40:14.212-04:00It is unnecessary to have i < j for permutation...It is unnecessary to have i < j for permutation pi_{i, j}Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119965271022796692005-06-28T09:27:00.000-04:002005-06-28T09:27:00.000-04:00One could also argue that these conjectures arise ...One could also argue that these conjectures arise organically while<BR/>trying to solve problems. Hence<BR/>they are part and parcel how <BR/>research is done. On the other<BR/>hand, we do need to pay attention<BR/>to the chain of reductions as it<BR/>gets longer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119944488040244942005-06-28T03:41:00.000-04:002005-06-28T03:41:00.000-04:00Well, the immportance of conjectures should not on...Well, the immportance of conjectures should not only be gauged by whether we can answer or not or even the number of implications it has. A big part of it is also the techniques and theory that get developed in an effort settle the conjecture. A good example would be FLT(Femat's Last Theorm). I don't know if the conjecture has any implication at all. However, algebraic number theory statred and developed in quest to settle it. And now when the cojecture is settled the field remains and we continue to discover interesting things. <BR/><BR/>I completely agree with Scott. Not only it(P!=NP conjecture) has simplified the field, it has also had tremendous impact on our field.<BR/>Much of complexity theory has been developed in quest of settling the P!=NP conjecture. Although we seem to be nowhere near to settle the conjecture but we atleast have settled some other questions. For instance, the work of Razborov in late 80s on monotone circuit lower bounds.<BR/><BR/>Another good thing about Unique Games, which has also been pointed out by others, is that we have reduced optimal inapproximability results for many optimization problems to one question. Hence it becomes a "meta question" for the whole field. I think theory is all about that, isn't it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119931920519202582005-06-28T00:12:00.000-04:002005-06-28T00:12:00.000-04:00Another comparison, within the same sub-field, is ...Another comparison, within the same sub-field, is with the assumption that "Max SNP is not contained in PTAS," that is, that Max 3SAT cannot be approximated arbitrarily well.<BR/><BR/>Papadimitriou and Yannakakis defined Max SNP in the late 1980s, and showed that the approximability of several optimization problems depended on the resolution of this question. (That is, various problems had an approximation scheme if and only if all of Max SNP admited an approximation scheme, because said problems were proved to be <B>complete</B> for Max SNP under approximation-preserving reductions.)<BR/><BR/>The PCP Theorem, of course, proved that indeed Max SNP is not contained in PTAS unless P=NP.<BR/><BR/>With Unique Games, unfortunately, we do not yet have completeness results. That is, if the Unique Games conjecture is proved, then we have all these inapproximability results (modulo P =/= NP), but if the Unique Games conjecture is disproved, then we are left almost empty-handed. Notice the "almost": in any event the unconditional integrality gap results will survive, and so will the new results about the Fourier analysis of Boolean functions motivated by unique games.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119922851294825152005-06-27T21:40:00.000-04:002005-06-27T21:40:00.000-04:00Well, one conjecture that similarly simplified a f...Well, one conjecture that similarly simplified a field was P!=NP.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119912230090776322005-06-27T18:43:00.000-04:002005-06-27T18:43:00.000-04:00Here is a meta-question: what other conjectures ar...Here is a meta-question: what other conjectures are out there that have been similarly applicable at simplifying a field? Are there similar conjectures that were eventually later proved to be true or false?<BR/><BR/>-David MolnarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1119890500329489882005-06-27T12:41:00.000-04:002005-06-27T12:41:00.000-04:00Very nice and breif description of unique-game con...Very nice and breif description of unique-game conjecture.Anonymousnoreply@blogger.com