PARAMETERIZED INAPPROXIMABILITY OF THE MINIMUM DISTANCE PROBLEM OVER ALL FIELDS AND THE SHORTEST VECTOR PROBLEM IN ALL ℓ p NORMS

被引：0
作者：
Bennett, Huck [1 ]
Cheraghchi, Mahdi [2 ]
Guruswami, Venkatesan [3 ]
Ribeiro, Joao [4 ]
机构：
[1] Department of Computer Science, University of Colorado, Boulder, 80309, CO
[2] EECS Department, University of Michigan, Ann Arbor, 48109, MI
[3] Department of EECS, University of California Berkeley, Berkeley, 94720, CA
[4] NOVA LINCS, Department of Computer Science, NOVA School of Science and Technology, Universidade Nova de Lisboa, Caparica
来源：
SIAM Journal on Computing | 2024年 / 53卷 / 05期
基金：
美国国家科学基金会;
关键词：
approximation; minimum distance problem; parameterized hardness; shortest vector problem;
D O I：
10.1137/23M1573021
中图分类号：
学科分类号：
摘要：
We prove that the minimum distance problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is sansW [1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized shortest vector problem (SVP) on integer lattices. Specifically, we prove that the SVP in the ℓ p norm is sansW [1]-hard to approximate within any constant factor for any fixed p > 1 and sansW [1]-hard to approximate within a factor approaching 2 for p = 1. (We show hardness under randomized reductions in each case.) These results answer the main questions left open (and explicitly posed) by Bhattacharyya et al. [J. ACM, 68 (2021), 16] on the complexity of the parameterized MDP and SVP. For the MDP, they established similar hardness for binary linear codes and left the case of general fields open. For the SVP in ℓ p norms with p >1, they showed inapproximability within some constant factor (depending on p) and left open showing such hardness for arbitrary constant factors. They also left open showing sansW [1]-hardness even of the exact SVP in the ℓ 1 norm. © 2024 Society for Industrial and Applied Mathematics Publications. All rights reserved.
引用
收藏
页码：1439 / 1475
页数：36
相关论文
共 42 条
[1]  
Aggarwal D., Bennett H., Golovnev A., Stephens-Davidowitz N., Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else), Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1816-1835, (2021)
[2]  
Aggarwal D., Stephens-Davidowitz N., (Gap/S)ETH hardness of SVP, STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 228-238, (2018)
[3]  
Agrawal M., Kayal N., Saxena N., PRIMES is in P, Ann. Math, 160, pp. 781-793, (2004)
[4]  
Ajtai M., The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract), STOC '98: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 10-19, (1998)
[5]  
Arora S., Babai L., Stern J., Sweedyk Z., The hardness of approximate optima in lattices, codes, and systems of linear equations, J. Comput. Syst. Sci, 54, pp. 317-331, (1997)
[6]  
Austrin P., Khot S., A simple deterministic reduction for the gap minimum distance of code problem, IEEE Trans. Inform. Theory, 60, pp. 6636-6645, (2014)
[7]  
Bennett H., Cheraghchi M., Guruswami V., Ribeiro J., Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all ell p norms, Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pp. 553-566, (2023)
[8]  
Bennett H., Golovnev A., Stephens-Davidowitz N., On the quantitative hardness of CVP, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 13-24, (2017)
[9]  
Bennett H., Peikert C., Hardness of the (approximate) shortest vector problem: A simple proof via Reed-Solomon codes, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), (2023)
[10]  
Bennett H., Peikert C., Tang Y., Improved hardness of BDD and SVP under Gap-(S)ETH, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Leibniz International Proceedings in Informatics (LIPIcs), 215, pp. 19:1-19:12, (2022)
12345