Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ p Norms
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓ p Norms
复制标题
全域最小距离问题和全-p范数中最短向量问题的参数化不可逼近性
DOI：
10.1145/3564246.3585214
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Ribeiro, João
中科院分区：
文献类型：
--
作者：
Bennett, Huck;Cheraghchi, Mahdi;Guruswami, Venkatesan;Ribeiro, João
证明了线性码在任意固定有限域上的最小距离问题（MDP）难以在任意常数因子内近似。我们还证明了整数格上参数化最短向量问题的类似结果。具体地说，我们证明了对于任意固定的p - [1]， SVP在任意常数因子内难以近似，对于任意固定的p - [1]， w -[1]在接近2的因子内难以近似，对于p=1。（我们在每种情况下都显示了随机减少的硬度。）这些结果回答了Bhattacharyya、Bonnet、Egri、Ghoshal、Karthik C. S、Lin、Manurangsi和Marx （ACM Journal of the ACM, 2021）关于参数化MDP和SVP复杂性的主要问题（并明确提出）。对于MDP，他们为二进制线性码建立了类似的硬度，并保留了一般字段的情况。对于p为> 1的p范数中的SVP，它们在某些常数因子（取决于p）内显示出不逼近性，并且对任意常数因子显示出这种硬度。他们也留下了开放的W[1]-硬度，甚至在1范数下精确的SVP。
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound isW[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 SVP in the ℓpnorm isW[1]-hard to approximate within any constant factor for any fixedp>1 andW[1]-hard to approximate within a factor approaching 2 forp=1. (We show hardness under randomized reductions in each case.)These results answer the main questions left open (and explicitly posed) by Bhattacharyya, Bonnet, Egri, Ghoshal, Karthik C. S., Lin, Manurangsi, and Marx (Journal of the ACM, 2021) on the complexity of parameterized MDP and SVP. For MDP, they established similar hardness for binary linear codes and left the case of general fields open. For SVP in ℓpnorms withp> 1, they showed inapproximability within some constant factor (depending onp) and left open showing such hardness for arbitrary constant factors. They also left open showing W[1]-hardness even of exact SVP in the ℓ1norm.