{"id":1958,"date":"2014-08-16T20:51:21","date_gmt":"2014-08-17T00:51:21","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=1958"},"modified":"2017-01-13T07:00:54","modified_gmt":"2017-01-13T12:00:54","slug":"subhash-khots-prizewinning-research","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=1958","title":{"rendered":"Subhash Khot’s prizewinning research"},"content":{"rendered":"

I already congratulated Subhash Khot<\/a> in my last post for winning the Nevanlinna Award<\/a>, but this really deserves a separate post. \u00a0Khot won theoretical computer science’s highest award largely\u00a0for introducing and exploring the\u00a0Unique Games Conjecture (UGC)<\/a>, which says (in one sentence) that a large number of the\u00a0approximation\u00a0problems that no one has been able to prove NP-hard, really are<\/em> NP-hard. \u00a0In particular, if the UGC is true, then for MAX-CUT<\/a> and dozens of other important optimization\u00a0problems,\u00a0no polynomial-time algorithm can always get you closer to the optimal solution than some semidefinite-programming-based algorithm gets you, unless P=NP. \u00a0The UGC might or might not be true—unlike with (say) P\u2260NP itself, there’s no firm consensus around it—but even if it’s false, the effort to prove or disprove it has by now\u00a0had a huge impact on theoretical computer science research, leading to connections with geometry, tiling, analysis of Boolean functions, quantum entanglement, and more.<\/p>\n

There are a few features\u00a0that make the UGC interesting, compared to most other questions considered in complexity theory. \u00a0Firstly, the problem that the UGC asserts is NP-hard—basically,\u00a0given a list of linear equations in 2 variables each, to satisfy as many of the equations as you can—is a problem with “imperfect completeness.” \u00a0This means that, if you just wanted to know whether all<\/em> the linear equations were simultaneously satisfiable, the question would be trivial\u00a0to answer, using Gaussian elimination. \u00a0So the problem only becomes interesting once you’re told that the equations are not<\/em> simultaneously satisfiable, but you’d like to know (say) whether it’s possible to satisfy 99% of the equations or only 1%. \u00a0A second feature is that, because of the 2010 work<\/a> of Arora, Barak, and Steurer, we know that there is<\/em> an algorithm that solves the unique games problem in “subexponential time”: specifically, in time exp(npoly(\u03b4)<\/sup>),\u00a0where \u03b4 is the completeness error (that is, the fraction of linear equations that are unsatisfiable, in the case that most of them are satisfiable). \u00a0This doesn’t mean that the unique games problem can’t be NP-hard: it just means that, if there is<\/em>\u00a0an NP-hardness proof, then the reduction will need to blow up the instance sizes by an npoly(1\/\u03b4)<\/sup>\u00a0factor.<\/p>\n

To be clear, neither of the above features is unique<\/em> (har, har) to unique games: we’ve long known NP-complete problems, like MAX-2SAT<\/a>, that have the imperfect completeness feature, and we also know NP-hardness reductions that blow up the instance size by an npoly(1\/\u03b4)<\/sup>\u00a0factor for inherent reasons (for example, for the Set Cover<\/a> problem). \u00a0But perhaps nothing points as clearly as UGC at the directions that researchers in hardness of approximation and probabilistically checkable proofs (PCP) would like to be able to go. \u00a0A proof of the Unique Games Conjecture would basically be a PCP theorem on steroids. \u00a0(Or, since we already have “PCP theorems on steroids,” maybe a PCP theorem on PCP<\/a>?)<\/p>\n

It’s important to understand that, between the UGC being true and the unique games problem being solvable in polynomial time, there’s a wide range of intermediate possibilities, many of which are being actively investigated. \u00a0For example, the unique games problem could be “NP-hard,” but via a reduction that itself takes subexponential time (i.e., it could be hard assuming the Exponential-Time Hypothesis). \u00a0It could be solvable much faster than Arora-Barak-Steurer but still not in P. \u00a0Or, even if the problem weren’t solvable any faster\u00a0than is\u00a0currently known, it could be “hard without being NP-hard,” having a similar status to factoring or graph isomorphism. \u00a0Much current research into the UGC is focused on a particular algorithm called the Sum-of-Squares algorithm (i.e., the Laserre hierarchy). \u00a0Some researchers suspect that, if any<\/em> algorithm will solve the unique games problem in polynomial time (or close to that), it will be Sum-of-Squares; conversely, if one could show that Sum-of-Squares failed, one would’ve taken a major step toward proving the UGC.<\/p>\n

For more, I recommend this Quanta<\/em> magazine article<\/a>, or Luca Trevisan’s survey<\/a>, or Subhash’s own survey<\/a>.\u00a0 Or those pressed for time can simply check out\u00a0this video interview with Subhash<\/a>. \u00a0If you’d like to try my wife Dana’s puzzle games inspired by PCP, which Subhash uses 2 minutes into the video to explain\u00a0what he works on, see here<\/a>. \u00a0Online, interactive versions of these\u00a0puzzle games are currently under development. \u00a0Also,\u00a0if you have questions about the UGC or Subhash’s work, go ahead and ask: I’ll answer if I can, and otherwise rely on in-house expertise.<\/p>\n

Congratulations again to Subhash!<\/p>\n","protected":false},"excerpt":{"rendered":"

I already congratulated Subhash Khot in my last post for winning the Nevanlinna Award, but this really deserves a separate post. \u00a0Khot won theoretical computer science’s highest award largely\u00a0for introducing and exploring the\u00a0Unique Games Conjecture (UGC), which says (in one sentence) that a large number of the\u00a0approximation\u00a0problems that no one has been able to prove […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[31,5],"tags":[],"class_list":["post-1958","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1958","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1958"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1958\/revisions"}],"predecessor-version":[{"id":1962,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/1958\/revisions\/1962"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1958"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1958"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1958"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}