{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T21:13:43Z","timestamp":1784236423100,"version":"3.55.0"},"reference-count":64,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["2015-04659"],"award-info":[{"award-number":["2015-04659"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["No 677651"],"award-info":[{"award-number":["No 677651"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["715672"],"award-info":[{"award-number":["715672"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["621\/12"],"award-info":[{"award-number":["621\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1218620"],"award-info":[{"award-number":["1218620"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1540547"],"award-info":[{"award-number":["1540547"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1540685"],"award-info":[{"award-number":["CCF 1540685"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1655215"],"award-info":[{"award-number":["CCF 1655215"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1740425"],"award-info":[{"award-number":["CCF 1740425"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1137\/18m1166869","type":"journal-article","created":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T14:26:22Z","timestamp":1595341582000},"page":"772-810","source":"Crossref","is-referenced-by-count":20,"title":["From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More"],"prefix":"10.1137","volume":"49","author":[{"given":"Parinya","family":"Chalermsook","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marek","family":"Cygan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4476-8914","authenticated-orcid":true,"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4468-2675","authenticated-orcid":true,"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luca","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,7,21]]},"reference":[{"key":"atypb1","first-page":"44","author":"Aaronson S.","year":"2014","journal-title":"NJ"},{"key":"atypb2","first-page":"25","author":"Abboud A.","year":"2017","journal-title":"NJ"},{"key":"atypb3","first-page":"689","author":"Allen S. R.","year":"2015","journal-title":"NJ"},{"key":"atypb5","first-page":"836","author":"Applebaum B.","year":"2017","journal-title":"NJ"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"atypb9","first-page":"294","author":"Bellare M.","year":"1993","journal-title":"New York"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90056-L"},{"key":"atypb12","first-page":"10","volume":"6","author":"Bhangale A.","year":"2016","journal-title":"Germany"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9889-1"},{"key":"atypb16","first-page":"22","author":"Bonnet \u00c9.","year":"2016","journal-title":"Germany"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90275-F"},{"key":"atypb19","first-page":"1557","author":"Chalermsook P.","year":"2013","journal-title":"New York"},{"key":"atypb20","first-page":"370","author":"Chalermsook P.","year":"2013","journal-title":"NJ"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9464-3"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-7137-6"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"atypb25","first-page":"109","author":"Chen Y.","year":"2006","journal-title":"Berlin"},{"key":"atypb27","first-page":"505","author":"Chen Y.","year":"2016","journal-title":"NJ"},{"key":"atypb28","first-page":"110","author":"Chitnis R. H.","year":"2013","journal-title":"Switzerland"},{"key":"atypb29","first-page":"900","author":"Chlamt\u00e1\u010d E.","year":"2017","journal-title":"Philadelphia"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"atypb33","first-page":"624","volume":"2014","author":"Dinur I.","year":"2014","journal-title":"STOC"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.09.017"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.05.001"},{"key":"atypb37","first-page":"1210","author":"Elbassioni K.","year":"2009","journal-title":"Philadelphia"},{"key":"atypb38","first-page":"2","author":"Engebretsen L.","year":"2000","journal-title":"Berlin"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb40","first-page":"534","author":"Feige U.","year":"2002","journal-title":"New York"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797325375"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"atypb46","first-page":"26","volume":"2","author":"Fellows M. R.","year":"2012","journal-title":"Dagstuhl Rep."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"atypb48","first-page":"363","author":"Grohe M.","year":"2007","journal-title":"Berlin"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"atypb59","first-page":"226","author":"Khot S.","year":"2006","journal-title":"Berlin"},{"key":"atypb60","first-page":"137","author":"Khot S.","year":"2000","journal-title":"Berlin"},{"key":"atypb61","first-page":"37","author":"Khot S.","year":"2016","journal-title":"New York"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"atypb66","first-page":"605","author":"Lin B.","year":"2015","journal-title":"Philadelphia"},{"key":"atypb67","first-page":"40","author":"Lund C.","year":"1993","journal-title":"Berlin"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"atypb70","first-page":"954","author":"Manurangsi P.","year":"2017","journal-title":"New York"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"atypb74","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.09.001"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.07.011"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"atypb77","first-page":"1065","author":"P\u01cetrascu M.","year":"2010","journal-title":"New York"},{"key":"atypb78","first-page":"245","author":"Raghavendra P.","year":"2008","journal-title":"New York"},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"atypb81","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90077-1"},{"key":"atypb82","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"atypb84","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266407"},{"key":"atypb85","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940870"},{"key":"atypb86","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/18M1166869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,31]],"date-time":"2020-08-31T15:31:40Z","timestamp":1598887900000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/18M1166869"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":64,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/18M1166869"],"URL":"https:\/\/doi.org\/10.1137\/18m1166869","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}