tag:blogger.com,1999:blog-3722233.post113430625702525223..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: UG-HardLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-1134504405229338632005-12-13T14:06:00.000-06:002005-12-13T14:06:00.000-06:00I suggest calling it the Unique Games Hypothesis, ...<I>I suggest calling it the Unique Games Hypothesis, and therefore refer to <BR/>UGH-hard and UGH-complete problems.</I><BR/><BR/>This is exactly the kind of thing that Lance's proposal is meant to avoid. There is no 'hypothesis' needed.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134432377913851732005-12-12T18:06:00.000-06:002005-12-12T18:06:00.000-06:00I suggest calling it the Unique Games Hypothesis, ...I suggest calling it the Unique Games Hypothesis, and therefore refer to <BR/>UGH-hard and UGH-complete problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134405104579917562005-12-12T10:31:00.000-06:002005-12-12T10:31:00.000-06:00"UG-hard" is good terminology; moreover, it natura..."UG-hard" is good terminology; moreover, it naturally raises a question that the current UG-hardness results don't address: Which of these UG-hard problems are UG-complete?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134339856102640132005-12-11T16:24:00.000-06:002005-12-11T16:24:00.000-06:00People have a variety of opinions about the conjec...People have a variety of opinions about the conjecture and because of this the term "unique games-hard" is already in somewhat common usage. Muli Safra has staked money on the problem lying strictly between P and NPC.<BR/><BR/>Others have suggested that perhaps unique games captures the complexity of the semi-definite programming model, which is why the hardness techniques always relate very closely to an integrality gap for some SDP.<BR/><BR/>This is also why the Khot-Vishnoi paper was so nice; the story is almost more important than the result. Proving UG-hardness for sparsest cut led to an unconditional integrality gap example which suggests that the UG problem is capturing something substantial.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134337961198160442005-12-11T15:52:00.000-06:002005-12-11T15:52:00.000-06:00Oh yes, and we can tell undergrads that UG stands ...Oh yes, and we can tell undergrads that UG stands for undergraduates. This should motivate them to solve the problem :)<BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134337551000013152005-12-11T15:45:00.000-06:002005-12-11T15:45:00.000-06:00I like the "UG-hard" name. It is compatible with n...I like the "UG-hard" name. It is compatible with naming convention used elsewhere, such as "3SUM-hardness". <BR/><BR/>PiotrAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134334784708686572005-12-11T14:59:00.000-06:002005-12-11T14:59:00.000-06:00Lance, The UnderGrads in my place have classified ...Lance, <BR/><BR/>The UnderGrads in my place have classified many problems as UG-Hard. So, can you please suggest some other name:)?<BR/><BR/>It seems that Knuth once asked the theorists of that time, a name for what we now call as NP-C problems. Someone (I think Larry Stockmeyer) suggested that we call them as <I>HardAsS problems </I>: for Hard As SAT.<BR/><BR/>AmarAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1134328653735630602005-12-11T13:17:00.000-06:002005-12-11T13:17:00.000-06:00Am I the only one who simply doesn't believe that ...Am I the only one who simply doesn't believe that graph isomorphism is hard?Anonymousnoreply@blogger.com