Document Open Access Logo

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

Authors Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.17.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Arnab Bhattacharyya
  • Indian Institute of Science, Bangalore, India
Suprovat Ghoshal
  • Indian Institute of Science, Bangalore, India
Karthik C. S.
  • Weizmann Institute of Science, Rehovot, Israel
Pasin Manurangsi
  • University of California, Berkeley, USA

Funding

  • Bhattacharyya, Arnab: This work was supported by Ramanujan Fellowship DSTO 1358.
  • C. S., Karthik: This work was supported by Irit Dinur’s ERC-CoG grant 772839.
  • Manurangsi, Pasin: Some part of this work was done while the author was visiting Indian Institute of Science and supported by the Indo-US Joint Center for Pseudorandomness in Computer Science.

Cite AsGet BibTex

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.17

Abstract

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F_2, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k. Here, k is the parameter of the problem. The question of whether k-Even Set is fixed parameter tractable (FPT) has been repeatedly raised in literature and has earned its place in Downey and Fellows' book (2013) as one of the "most infamous" open problems in the field of Parameterized Complexity. In this work, we show that k-Even Set does not admit FPT algorithms under the (randomized) Gap Exponential Time Hypothesis (Gap-ETH) [Dinur'16, Manurangsi-Raghavendra'16]. In fact, our result rules out not only exact FPT algorithms, but also any constant factor FPT approximation algorithms for the problem. Furthermore, our result holds even under the following weaker assumption, which is also known as the Parameterized Inapproximability Hypothesis (PIH) [Lokshtanov et al.'17]: no (randomized) FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only 0.99-satisfiable (where the parameter is the number of variables). We also consider the parameterized k-Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the l_p norm for some fixed p) is at most k. Similar to k-Even Set, this problem is also a long-standing open problem in the field of Parameterized Complexity. We show that, for any p > 1, k-SVP is hard to approximate (in FPT time) to some constant factor, assuming PIH. Furthermore, for the case of p = 2, the inapproximability factor can be amplified to any constant.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Inapproximability
  • Even Set
  • Minimum Distance Problem
  • Shortest Vector Problem
  • Gap-ETH

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Divesh Aggarwal and Noah Stephens-Davidowitz. (gap/s)eth hardness of SVP. CoRR, abs/1712.00942, 2017. URL: http://arxiv.org/abs/1712.00942.
  2. Miklós Ajtai. Generating hard instances of lattice problems (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 99-108, 1996. URL: http://dx.doi.org/10.1145/237814.237838.
  3. Miklós Ajtai. The shortest vector problem in 𝓁₂ is NP-hard for randomized reductions (extended abstract). In STOC, pages 10-19, 1998. URL: http://dx.doi.org/10.1145/276698.276705.
  4. Miklós Ajtai and Cynthia Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In STOC, pages 284-293, 1997. URL: http://dx.doi.org/10.1145/258533.258604.
  5. Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. J. Comput. Syst. Sci., 54(2):317-331, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1472.
  6. Per Austrin and Subhash Khot. A simple deterministic reduction for the gap minimum distance of code problem. IEEE Trans. Information Theory, 60(10):6636-6645, 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2340869.
  7. Huck Bennett, Alexander Golovnev, and Noah Stephens-Davidowitz. On the quantitative hardness of CVP. In FOCS, pages 13-24, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.11.
  8. Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Information Theory, 24(3):384-386, 1978. URL: http://dx.doi.org/10.1109/TIT.1978.1055873.
  9. Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket. On the hardness of learning sparse parities. In ESA, pages 11:1-11:17, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.11.
  10. Jin-yi Cai and Ajay Nerurkar. Approximating the SVP to within a factor (1+1/dim^ξ) is NP-hard under randomized reductions. J. Comput. Syst. Sci., 59(2):221-239, 1999. URL: http://dx.doi.org/10.1006/jcss.1999.1649.
  11. Qi Cheng and Daqing Wan. A deterministic reduction for the gap minimum distance problem. IEEE Trans. Information Theory, 58(11):6935-6941, 2012. URL: http://dx.doi.org/10.1109/TIT.2012.2209198.
  12. Marek Cygan, Fedor Fomin, Bart MP Jansen, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, and Saket Saurabh. Open problems for fpt school 2014, 2014. Google Scholar
  13. Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlström. Randomization in parameterized complexity (dagstuhl seminar 17041). Dagstuhl Reports, 7(1):103-128, 2017. URL: http://dx.doi.org/10.4230/DagRep.7.1.103.
  14. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  15. Erik D. Demaine, Gregory Gutin, Dániel Marx, and Ulrike Stege. 07281 open problems - structure theory and FPT algorithmcs for graphs, digraphs and hypergraphs. In Erik D. Demaine, Gregory Z. Gutin, Dániel Marx, and Ulrike Stege, editors, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, 08.07. - 13.07.2007, volume 07281 of Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2007. URL: http://drops.dagstuhl.de/opus/volltexte/2007/1254.
  16. Irit Dinur. Approximating SVP_∞ to within almost-polynomial factors is NP-hard. Theor. Comput. Sci., 285(1):55-71, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00290-0.
  17. Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. ECCC, 23:128, 2016. URL: http://eccc.hpi-web.de/report/2016/128.
  18. Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra. Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205-243, 2003. URL: http://dx.doi.org/10.1007/s00493-003-0019-y.
  19. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0515-9.
  20. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  21. Rodney G. Downey, Michael R. Fellows, Alexander Vardy, and Geoff Whittle. The parametrized complexity of some fundamental problems in coding theory. SIAM J. Comput., 29(2):545-570, 1999. URL: http://dx.doi.org/10.1137/S0097539797323571.
  22. Ilya Dumer, Daniele Micciancio, and Madhu Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Information Theory, 49(1):22-37, 2003. URL: http://dx.doi.org/10.1109/TIT.2002.806118.
  23. Michael R. Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh. Data reduction and problem kernels (dagstuhl seminar 12241). Dagstuhl Reports, 2(6):26-50, 2012. URL: http://dx.doi.org/10.4230/DagRep.2.6.26.
  24. Oded Goldreich, Daniele Micciancio, Shmuel Safra, and Jean-Pierre Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inf. Process. Lett., 71(2):55-61, 1999. URL: http://dx.doi.org/10.1016/S0020-0190(99)00083-6.
  25. Petr A. Golovach, Jan Kratochvíl, and Ondrej Suchý. Parameterized complexity of generalized domination problems. Discrete Applied Mathematics, 160(6):780-792, 2012. URL: http://dx.doi.org/10.1016/j.dam.2010.11.012.
  26. Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. In STOC, pages 469-477, 2007. URL: http://dx.doi.org/10.1145/1250790.1250859.
  27. Subhash Khot. Hardness of approximating the shortest vector problem in lattices. J. ACM, 52(5):789-808, 2005. Google Scholar
  28. Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515-534, 1982. Google Scholar
  29. Hendrik Willem Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548, 1983. URL: http://dx.doi.org/10.1287/moor.8.4.538.
  30. Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Parameterized complexity and approximability of directed odd cycle transversal. CoRR, abs/1704.04249, 2017. URL: http://arxiv.org/abs/1704.04249.
  31. Ruhollah Majdoddin. Parameterized complexity of CSP for infinite constraint languages. CoRR, abs/1706.10153, 2017. URL: http://arxiv.org/abs/1706.10153.
  32. Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense CSPs. CoRR, abs/1607.02986, 2016. URL: http://arxiv.org/abs/1607.02986,
  33. Daniele Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. SIAM J. Comput., 30(6):2008-2035, 2000. URL: http://dx.doi.org/10.1137/S0097539700373039.
  34. Daniele Micciancio. The hardness of the closest vector problem with preprocessing. IEEE Trans. Information Theory, 47(3):1212-1215, 2001. URL: http://dx.doi.org/10.1109/18.915688.
  35. Daniele Micciancio. Inapproximability of the shortest vector problem: Toward a deterministic reduction. Theory of Computing, 8(1):487-512, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a022.
  36. Daniele Micciancio. Locally dense codes. In CCC, pages 90-97. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/CCC.2014.17.
  37. Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Post-quantum cryptography, pages 147-191. Springer, 2009. Google Scholar
  38. Phong Q. Nguyen and Brigitte Vallée, editors. The LLL Algorithm - Survey and Applications. Information Security and Cryptography. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-02295-1.
  39. Oded Regev. New lattice based cryptographic constructions. In Lawrence L. Larmore and Michel X. Goemans, editors, STOC, pages 407-416. ACM, 2003. URL: http://dx.doi.org/10.1145/780542.780603.
  40. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In STOC, pages 84-93, 2005. URL: http://dx.doi.org/10.1145/1060590.1060603.
  41. Oded Regev. Lattice-based cryptography. In Cynthia Dwork, editor, CRYPTO, volume 4117 of Lecture Notes in Computer Science, pages 131-141. Springer, 2006. URL: http://dx.doi.org/10.1007/11818175_8.
  42. Oded Regev. The learning with errors problem (invited survey). In CCC, pages 191-204, 2010. URL: http://dx.doi.org/10.1109/CCC.2010.26.
  43. Oded Regev and Ricky Rosen. Lattice problems and norm embeddings. In STOC, pages 447-456, 2006. URL: http://dx.doi.org/10.1145/1132516.1132581.
  44. Jacques Stern. Approximating the number of error locations within a constant ratio is NP-complete. In Gérard D. Cohen, Teo Mora, and Oscar Moreno, editors, AAECC, volume 673 of Lecture Notes in Computer Science, pages 325-331. Springer, 1993. URL: http://dx.doi.org/10.1007/3-540-56686-4_54.
  45. Peter van Emde-Boas. Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Report. Department of Mathematics. University of Amsterdam. Department, Univ., 1981. Google Scholar
  46. Alexander Vardy. Algorithmic complexity in coding theory and the minimum distance problem. In STOC, pages 92-109, 1997. URL: http://dx.doi.org/10.1145/258533.258559.
  47. Alexander Vardy. The intractability of computing the minimum distance of a code. IEEE Trans. Information Theory, 43(6):1757-1766, 1997. URL: http://dx.doi.org/10.1109/18.641542.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact