{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T03:21:51Z","timestamp":1767842511974,"version":"3.49.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T00:00:00Z","timestamp":1616371200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ramanujan Fellowship DSTO","award":["1358"],"award-info":[{"award-number":["1358"]}]},{"name":"Indo-US Joint Center for Pseudorandomness in Computer Science while at Indian Institute of Science","award":["MOE2019-T2-1-152"],"award-info":[{"award-number":["MOE2019-T2-1-152"]}]},{"name":"European Research Council","award":["725978"],"award-info":[{"award-number":["725978"]}]},{"name":"ERC-CoG","award":["772839"],"award-info":[{"award-number":["772839"]}]},{"name":"JSPS KAKENHI","award":["JP16H07409"],"award-info":[{"award-number":["JP16H07409"]}]},{"name":"JST ERATO","award":["JPMJER1201"],"award-info":[{"award-number":["JPMJER1201"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"\n The\n \n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -Even Set\n <\/jats:italic>\n problem is a parameterized variant of the\n Minimum Distance Problem<\/jats:italic>\n of linear codes over\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , which can be stated as follows: given a generator matrix\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and an integer\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , determine whether the code generated by\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has distance at most\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , or, in other words, whether there is a nonzero vector\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n such that\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has at most\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n nonzero coordinates. The question of whether\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -Even Set is fixed parameter tractable (FPT) parameterized by the distance\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -Even Set is\n W<\/jats:sans-serif>\n [1]-hard under randomized reductions.\n <\/jats:p>\n \n We also consider the parameterized\n \n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -Shortest Vector Problem (SVP)\n <\/jats:italic>\n , in which we are given a lattice whose basis vectors are integral and an integer\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , and the goal is to determine whether the norm of the shortest vector (in the\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n norm for some fixed\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) is at most\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Similar to\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -SVP is\n W<\/jats:sans-serif>\n [1]-hard to approximate (under randomized reductions) to some constant factor.\n <\/jats:p>","DOI":"10.1145\/3444942","type":"journal-article","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T16:22:02Z","timestamp":1616430122000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Parameterized Intractability of Even Set and Shortest Vector Problem"],"prefix":"10.1145","volume":"68","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c9douard","family":"Bonnet","sequence":"additional","affiliation":[{"name":"CNRS, ENS de Lyon, Universit\u00e9 Claude Bernard Lyon 1, LIP UMR5668, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L\u00e1szl\u00f3","family":"Egri","sequence":"additional","affiliation":[{"name":"Institute for Computer Science and Control, Hungarian Academy of Sciences, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suprovat","family":"Ghoshal","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"given":"Karthik C.","family":"S.","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bingkai","family":"Lin","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188840"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237838"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276705"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258604"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2340869"},{"key":"#cr-split#-e_1_2_1_7_1.1","doi-asserted-by":"crossref","unstructured":"Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2017. On the quantitative hardness of CVP. In FOCS. 13-24. DOI:https:\/\/doi.org\/10.1109\/FOCS.2017.11 10.1109\/FOCS.2017.11","DOI":"10.1109\/FOCS.2017.11"},{"key":"#cr-split#-e_1_2_1_7_1.2","doi-asserted-by":"crossref","unstructured":"Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2017. On the quantitative hardness of CVP. In FOCS. 13-24. DOI:https:\/\/doi.org\/10.1109\/FOCS.2017.11","DOI":"10.1109\/FOCS.2017.11"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055873"},{"key":"e_1_2_1_9_1","first-page":"1","article-title":"On the hardness of learning sparse parities","volume":"11","author":"Bhattacharyya Arnab","year":"2016","unstructured":"Arnab Bhattacharyya , Ameet Gadekar , Suprovat Ghoshal , and Rishi Saket . 2016 . On the hardness of learning sparse parities . In ESA. 11 : 1 \u2013 11 :17. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.11 10.4230\/LIPIcs.ESA.2016.11 Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket. 2016. On the hardness of learning sparse parities. In ESA. 11:1\u201311:17. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.11","journal-title":"ESA."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(60)90287-4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1649"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2209198"},{"key":"e_1_2_1_13_1","volume-title":"Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, and Saket Saurabh.","author":"Cygan Marek","year":"2014","unstructured":"Marek Cygan , Fedor Fomin , Bart MP Jansen , Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, and Saket Saurabh. 2014 . Open problems for FPT school 2014. Marek Cygan, Fedor Fomin, Bart MP Jansen, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, and Saket Saurabh. 2014. Open problems for FPT school 2014."},{"key":"e_1_2_1_14_1","first-page":"103","article-title":"Randomization in parameterized complexity (Dagstuhl seminar 17041)","volume":"7","author":"Cygan Marek","year":"2017","unstructured":"Marek Cygan , Fedor V. Fomin , Danny Hermelin , and Magnus Wahlstr\u00f6m . 2017 . Randomization in parameterized complexity (Dagstuhl seminar 17041) . Dagstuhl Reports 7 , 1 (2017), 103 \u2013 128 . DOI:https:\/\/doi.org\/10.4230\/DagRep.7.1.103 10.4230\/DagRep.7.1.103 Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlstr\u00f6m. 2017. Randomization in parameterized complexity (Dagstuhl seminar 17041). Dagstuhl Reports 7, 1 (2017), 103\u2013128. DOI:https:\/\/doi.org\/10.4230\/DagRep.7.1.103","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_2_1_16_1","first-page":"07","article-title":"07281 open problems\u2014Structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs","volume":"08","author":"Demaine Erik D.","year":"2007","unstructured":"Erik D. Demaine , Gregory Gutin , D\u00e1niel Marx , and Ulrike Stege . 2007 . 07281 open problems\u2014Structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs . In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs , 08 . 07 . - 13.07.2007. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2007\/1254 Erik D. Demaine, Gregory Gutin, D\u00e1niel Marx, and Ulrike Stege. 2007. 07281 open problems\u2014Structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07. - 13.07.2007. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2007\/1254","journal-title":"Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00290-0"},{"key":"e_1_2_1_18_1","first-page":"128","article-title":"Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover","volume":"23","author":"Dinur Irit","year":"2016","unstructured":"Irit Dinur . 2016 . Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover . ECCC 23 (2016), 128 . http:\/\/eccc.hpi-web.de\/report\/2016\/128 Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. ECCC 23 (2016), 128. http:\/\/eccc.hpi-web.de\/report\/2016\/128","journal-title":"ECCC"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0019-y"},{"key":"e_1_2_1_20_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer . DOI:https:\/\/doi.org\/10.1007\/978-1-4612-0515-9 10.1007\/978-1-4612-0515-9 Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer. DOI:https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2568438"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797323571"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.806118"},{"key":"e_1_2_1_24_1","first-page":"26","article-title":"Data reduction and problem kernels (Dagstuhl seminar 12241)","volume":"2","author":"Fellows Michael R.","year":"2012","unstructured":"Michael R. Fellows , Jiong Guo , D\u00e1niel Marx , and Saket Saurabh . 2012 . Data reduction and problem kernels (Dagstuhl seminar 12241) . Dagstuhl Reports 2 , 6 (2012), 26 \u2013 50 . DOI:https:\/\/doi.org\/10.4230\/DagRep.2.6.26 10.4230\/DagRep.2.6.26 Michael R. Fellows, Jiong Guo, D\u00e1niel Marx, and Saket Saurabh. 2012. Data reduction and problem kernels (Dagstuhl seminar 12241). Dagstuhl Reports 2, 6 (2012), 26\u201350. DOI:https:\/\/doi.org\/10.4230\/DagRep.2.6.26","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2344236.2344257"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2168303.2168315"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00083-6"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.11.012"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250859"},{"key":"e_1_2_1_30_1","volume-title":"Codes correcteurs d\u2019erreurs. Chiffres 2 (Sept","author":"Hocquenghem Alexis","year":"1959","unstructured":"Alexis Hocquenghem . 1959. Codes correcteurs d\u2019erreurs. Chiffres 2 (Sept . 1959 ), 147\u2013156. Alexis Hocquenghem. 1959. Codes correcteurs d\u2019erreurs. Chiffres 2 (Sept. 1959), 147\u2013156."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/114872.114874"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3325116"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089027"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212622"},{"key":"e_1_2_1_37_1","volume-title":"Parameterized complexity of CSP for infinite constraint languages. CoRR abs\/1706.10153","author":"Majdoddin Ruhollah","year":"2017","unstructured":"Ruhollah Majdoddin . 2017. Parameterized complexity of CSP for infinite constraint languages. CoRR abs\/1706.10153 ( 2017 ). arxiv:1706.10153 http:\/\/arxiv.org\/abs\/1706.10153 Ruhollah Majdoddin. 2017. Parameterized complexity of CSP for infinite constraint languages. CoRR abs\/1706.10153 (2017). arxiv:1706.10153 http:\/\/arxiv.org\/abs\/1706.10153"},{"key":"#cr-split#-e_1_2_1_38_1.1","doi-asserted-by":"crossref","unstructured":"Pasin Manurangsi. 2020. Tight running time lower bounds for strong inapproximability of maximum -coverage unique set cover and related problems (via -wise agreement testing theorem). In SODA. 62-81. DOI:https:\/\/doi.org\/10.1137\/1.9781611975994.5 10.1137\/1.9781611975994.5","DOI":"10.1137\/1.9781611975994.5"},{"key":"#cr-split#-e_1_2_1_38_1.2","doi-asserted-by":"crossref","unstructured":"Pasin Manurangsi. 2020. Tight running time lower bounds for strong inapproximability of maximum -coverage unique set cover and related problems (via -wise agreement testing theorem). In SODA. 62-81. DOI:https:\/\/doi.org\/10.1137\/1.9781611975994.5","DOI":"10.1137\/1.9781611975994.5"},{"key":"e_1_2_1_39_1","volume-title":"A birthday repetition theorem and complexity of approximating dense CSPs. CoRR abs\/1607.02986","author":"Manurangsi Pasin","year":"2016","unstructured":"Pasin Manurangsi and Prasad Raghavendra . 2016. A birthday repetition theorem and complexity of approximating dense CSPs. CoRR abs\/1607.02986 ( 2016 ). http:\/\/arxiv.org\/abs\/1607.02986 Pasin Manurangsi and Prasad Raghavendra. 2016. A birthday repetition theorem and complexity of approximating dense CSPs. CoRR abs\/1607.02986 (2016). http:\/\/arxiv.org\/abs\/1607.02986"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700373039"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.915688"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a022"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.17"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/560443"},{"key":"e_1_2_1_45_1","volume-title":"Post-quantum Cryptography","author":"Micciancio Daniele","unstructured":"Daniele Micciancio and Oded Regev . 2009. Lattice-based cryptography . In Post-quantum Cryptography . Springer , 147\u2013191. Daniele Micciancio and Oded Regev. 2009. Lattice-based cryptography. In Post-quantum Cryptography. Springer, 147\u2013191."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796315"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1721900"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780603"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_8"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.26"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132581"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/646028.677029"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258559"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.641542"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3444942","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3444942","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:13Z","timestamp":1750195693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3444942"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3444942"],"URL":"https:\/\/doi.org\/10.1145\/3444942","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,22]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}