{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:33:53Z","timestamp":1750221233704,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF-UGC 1399\/14"},{"name":"ERC-CoG 772839"},{"name":"NSF CCF-1540685"},{"name":"NSF CCF-1740425"},{"name":"NSF CCF-1655215"},{"name":"I-CORE 4\/11"},{"name":"ISF 621\/12"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188896","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"1283-1296","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On the parameterized complexity of approximating dominating set"],"prefix":"10.1145","author":[{"given":"Karthik C.","family":"S.","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany \/ Shanghai University of Finance and Economics, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_1"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_1"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.12"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214074"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150334.1150336"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_10"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700375944"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9889-1"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9223-x"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.74"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_3_2_2_15_1","first-page":"16","volume-title":"APPROX","author":"Charikar M.","year":"2016"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.73"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_10"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.61"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_11"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_3_2_2_22_1","first-page":"1085","volume-title":"SODA","author":"Cormode G.","year":"2008"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_2_25_1","first-page":"128","article-title":"Mildly exponential reduction from gap 3SAT to polynomial-gap labelcover","volume":"23","author":"Dinur I","year":"2016","journal-title":"ECCC"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"e_1_3_2_2_28_1","first-page":"244","volume-title":"Parameterized Computational Feasibility","author":"Downey R. G.","year":"1995"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2568438"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_11"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.09.017"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48314-6_5"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"volume-title":"Counting $t$-cliques: Worst-case to average-case reductions and direct interactive proof systems. Electronic Colloquium on Computational Complexity (ECCC) 25","year":"2018","author":"Goldreich O.","key":"e_1_3_2_2_36_1"},{"key":"e_1_3_2_2_37_1","first-page":"19","volume-title":"9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018","author":"Goldreich O.","year":"2018"},{"volume-title":"The foundations of fixed parameter inapproximability. CoRR abs\/1310.2711","year":"2013","author":"Hajiaghayi M. T.","key":"e_1_3_2_2_38_1"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"volume-title":"On the parameterized complexity of approximating dominating set. CoRR abs\/1711.11029","year":"2017","author":"Karthik C. S.","key":"e_1_3_2_2_44_1"},{"volume-title":"On the parameterized complexity of approximating dominating set. Electronic Colloquium on Computational Complexity (ECCC) 24","year":"2017","author":"Karthik C. S.","key":"e_1_3_2_2_45_1"},{"volume-title":"Communication Complexity","year":"1997","author":"Kushilevitz E.","key":"e_1_3_2_2_46_1"},{"key":"e_1_3_2_2_47_1","first-page":"4","article-title":"Lower bounds in communication complexity","volume":"3","author":"Lee T.","year":"2009","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032229.2032260"},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722170"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"volume-title":"A birthday repetition theorem and complexity of approximating dense CSPs. CoRR abs\/1607.02986","year":"2016","author":"Manurangsi P.","key":"e_1_3_2_2_52_1"},{"key":"e_1_3_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"e_1_3_2_2_54_1","first-page":"315","volume-title":"Proceedings of \u00e2\u0102IJCombinatorics, Paul Erdos is Eighty","author":"Nisan N.","year":"1994"},{"key":"e_1_3_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_2_57_1","first-page":"1075","volume-title":"SODA","author":"Patrascu M.","year":"2010"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095158"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_3_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"volume-title":"Personal communication","year":"2017","author":"Rubinstein A.","key":"e_1_3_2_2_62_1"},{"key":"e_1_3_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237991"},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225138"},{"key":"e_1_3_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"e_1_3_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3078-3"},{"key":"e_1_3_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_88"},{"key":"e_1_3_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188896","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188896","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:07:10Z","timestamp":1750212430000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188896"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":69,"alternative-id":["10.1145\/3188745.3188896","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188896","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}