{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T04:10:40Z","timestamp":1649218240796},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Ramanujan Fellowship DSTO","award":["1358"]},{"name":"Indo-US Joint Center for Pseudorandomness in Computer Science while at Indian Institute of Science","award":["MOE2019-T2-1-152"]},{"name":"European Research Council","award":["725978"]},{"name":"ERC-CoG","award":["772839"]},{"name":"JSPS KAKENHI","award":["JP16H07409"]},{"name":"JST ERATO","award":["JPMJER1201"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,3,17]]},"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","source":"Crossref","is-referenced-by-count":2,"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"}]},{"given":"\u00c9douard","family":"Bonnet","sequence":"additional","affiliation":[{"name":"CNRS, ENS de Lyon, Universit\u00e9 Claude Bernard Lyon 1, LIP UMR5668, France"}]},{"given":"L\u00e1szl\u00f3","family":"Egri","sequence":"additional","affiliation":[{"name":"Institute for Computer Science and Control, Hungarian Academy of Sciences, Hungary"}]},{"given":"Suprovat","family":"Ghoshal","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-9105-364X","authenticated-orcid":false,"given":"Karthik C.","family":"S.","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}]},{"given":"Bingkai","family":"Lin","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Germany"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Divesh Aggarwal and Noah Stephens-Davidowitz. 2018. (Gap\/S)ETH hardness of SVP. In STOC. 228\u2013238. DOI:https:\/\/doi.org\/10.1145\/3188745.3188840 Divesh Aggarwal and Noah Stephens-Davidowitz. 2018. (Gap\/S)ETH hardness of SVP. In STOC. 228\u2013238. DOI:https:\/\/doi.org\/10.1145\/3188745.3188840","DOI":"10.1145\/3188745.3188840"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai. 1996. Generating hard instances of lattice problems (extended abstract). In STOC. 99\u2013108. DOI:https:\/\/doi.org\/10.1145\/237814.237838 Mikl\u00f3s Ajtai. 1996. Generating hard instances of lattice problems (extended abstract). In STOC. 99\u2013108. DOI:https:\/\/doi.org\/10.1145\/237814.237838","DOI":"10.1145\/237814.237838"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai. 1998. The shortest vector problem in is NP-hard for randomized reductions (extended abstract). In STOC. 10\u201319. DOI:https:\/\/doi.org\/10.1145\/276698.276705 Mikl\u00f3s Ajtai. 1998. The shortest vector problem in is NP-hard for randomized reductions (extended abstract). In STOC. 10\u201319. DOI:https:\/\/doi.org\/10.1145\/276698.276705","DOI":"10.1145\/276698.276705"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Mikl\u00f3s Ajtai and Cynthia Dwork. 1997. A public-key cryptosystem with worst-case\/average-case equivalence. In STOC. 284\u2013293. DOI:https:\/\/doi.org\/10.1145\/258533.258604 Mikl\u00f3s Ajtai and Cynthia Dwork. 1997. A public-key cryptosystem with worst-case\/average-case equivalence. In STOC. 284\u2013293. DOI:https:\/\/doi.org\/10.1145\/258533.258604","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":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2017. On the quantitative hardness of CVP. In FOCS. 13\u201324. DOI:https:\/\/doi.org\/10.1109\/FOCS.2017.11 Huck Bennett Alexander Golovnev and Noah Stephens-Davidowitz. 2017. On the quantitative hardness of CVP. In FOCS. 13\u201324. 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","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":"crossref","first-page":"221","DOI":"10.1006\/jcss.1999.1649","article-title":"Approximating the SVP to within a factor Is NP-hard under randomized reductions","volume":"59","author":"Ajay Nerurkar Cai","year":"1999","journal-title":"J. Comput. Syst. Sci."},{"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"},{"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","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_15_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek"},{"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","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","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"},{"key":"e_1_2_1_21_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013"},{"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","journal-title":"Dagstuhl Reports"},{"key":"e_1_2_1_25_1","volume-title":"Fomin and D\u00e1niel Marx","author":"Fedor","year":"2012"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1007\/11685654_12","article-title":"On promise problems: A survey","author":"Goldreich Oded","year":"2006","journal-title":"Theoretical Computer Science, Essays in Memory of Shimon Even."},{"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":"crossref","unstructured":"Ishay Haviv and Oded Regev. 2007. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In STOC. 469\u2013477. DOI:https:\/\/doi.org\/10.1145\/1250790.1250859 Ishay Haviv and Oded Regev. 2007. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In STOC. 469\u2013477. DOI:https:\/\/doi.org\/10.1145\/1250790.1250859","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"},{"key":"e_1_2_1_31_1","volume-title":"Handbook of theoretical computer science","author":"Johnson D. S."},{"key":"e_1_2_1_32_1","article-title":"On the parameterized complexity of approximating dominating set","volume":"66","author":"Bundit Laekhanukit Karthik C. S.","year":"2019","journal-title":"J. ACM"},{"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","article-title":"The parameterized complexity of the k-biclique problem","volume":"65","author":"Lin Bingkai","year":"2018","journal-title":"J. ACM"},{"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"},{"key":"e_1_2_1_38_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\u201381. DOI:https:\/\/doi.org\/10.1137\/1.9781611975994.5 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\u201381. 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"},{"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":"crossref","unstructured":"Daniele Micciancio. 2014. Locally dense codes. In CCC. 90\u201397. DOI:https:\/\/doi.org\/10.1109\/CCC.2014.17 Daniele Micciancio. 2014. Locally dense codes. In CCC. 90\u201397. DOI:https:\/\/doi.org\/10.1109\/CCC.2014.17","DOI":"10.1109\/CCC.2014.17"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","volume-title":"Complexity of Lattice Problems: A Cryptographic Perspective","author":"Micciancio Daniele","DOI":"10.1007\/978-1-4615-0897-7"},{"key":"e_1_2_1_45_1","volume-title":"Post-quantum Cryptography","author":"Micciancio Daniele"},{"key":"e_1_2_1_46_1","volume-title":"36th Annual Symposium on Foundations of Computer Science","author":"Naor Moni","year":"1995"},{"key":"e_1_2_1_47_1","volume-title":"Nguyen and Brigitte Vall\u00e9e (Eds.)","author":"Phong","year":"2010"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Oded Regev. 2003. New lattice based cryptographic constructions. In STOC. 407\u2013416. DOI:https:\/\/doi.org\/10.1145\/780542.780603 Oded Regev. 2003. New lattice based cryptographic constructions. In STOC. 407\u2013416. DOI:https:\/\/doi.org\/10.1145\/780542.780603","DOI":"10.1145\/780542.780603"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Oded Regev. 2005. On lattices learning with errors random linear codes and cryptography. In STOC. 84\u201393. DOI:https:\/\/doi.org\/10.1145\/1060590.1060603 Oded Regev. 2005. On lattices learning with errors random linear codes and cryptography. In STOC. 84\u201393. DOI:https:\/\/doi.org\/10.1145\/1060590.1060603","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Oded Regev. 2006. Lattice-based cryptography. In CRYPTO. 131\u2013141. DOI:https:\/\/doi.org\/10.1007\/11818175_8 Oded Regev. 2006. Lattice-based cryptography. In CRYPTO. 131\u2013141. DOI:https:\/\/doi.org\/10.1007\/11818175_8","DOI":"10.1007\/11818175_8"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Oded Regev. 2010. The learning with errors problem (invited survey). In CCC. 191\u2013204. DOI:https:\/\/doi.org\/10.1109\/CCC.2010.26 Oded Regev. 2010. The learning with errors problem (invited survey). In CCC. 191\u2013204. DOI:https:\/\/doi.org\/10.1109\/CCC.2010.26","DOI":"10.1109\/CCC.2010.26"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Oded Regev and Ricky Rosen. 2006. Lattice problems and norm embeddings. In STOC. 447\u2013456. DOI:https:\/\/doi.org\/10.1145\/1132516.1132581 Oded Regev and Ricky Rosen. 2006. Lattice problems and norm embeddings. In STOC. 447\u2013456. DOI:https:\/\/doi.org\/10.1145\/1132516.1132581","DOI":"10.1145\/1132516.1132581"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Jacques Stern. 1993. Approximating the number of error locations within a constant ratio is NP-complete. In AAECC. 325\u2013331. DOI:https:\/\/doi.org\/10.1007\/3-540-56686-4_54 Jacques Stern. 1993. Approximating the number of error locations within a constant ratio is NP-complete. In AAECC. 325\u2013331. DOI:https:\/\/doi.org\/10.1007\/3-540-56686-4_54","DOI":"10.1007\/3-540-56686-4_54"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","unstructured":"Alexander Vardy. 1997. Algorithmic complexity in coding theory and the minimum distance problem. In STOC. 92\u2013109. DOI:https:\/\/doi.org\/10.1145\/258533.258559 Alexander Vardy. 1997. Algorithmic complexity in coding theory and the minimum distance problem. In STOC. 92\u2013109. DOI:https:\/\/doi.org\/10.1145\/258533.258559","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\/pdf\/10.1145\/3444942","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T16:28:26Z","timestamp":1616430506000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3444942"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,17]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3,17]]}},"alternative-id":["10.1145\/3444942"],"URL":"http:\/\/dx.doi.org\/10.1145\/3444942","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2021,3,17]]}}}