Event Timing: May 17th, 14:30
Organization: DCC-FCUP

Abstract: Computational problems over linear codes and lattices have found a wide range of applications in computer science, including to robust communication, cryptography, and optimization. Two such central problems -- approximating the minimum distance of a linear code (the Minimum Distance Problem, or MDP) and approximating the ell_p norm of the shortest lattice vector (the Shortest Vector Problem, or SVP) -- have been the target of a particularly active line of work spanning several decades in an attempt to understand their complexity.
It has been known for more than 20 years that MDP and SVP are NP-hard over any finite field and in any ell_p norm, respectively, for any constant approximation factor. However, the parameterized hardness of these problems remained mysterious for much longer. In this setting, one attempts to rule out algorithms running in time T(k)*poly(n), where n is the input size, k is the parameter of interest (the target bound on the minimum distance or on the norm of the shortest vector), and T is an arbitrary function. The first dent on this question was only recently made by groundbreaking work of Bhattacharyya, Bonnet, Egri, Ghoshal, Karthik C. S., Lin, Manurangsi, and Marx (Journal of the ACM, 2021), who showed W[1]-hardness (the parameterized analogue of NP-hardness) of MDP over *binary* linear codes and of SVP in ell_p norms with p>1 for *some* small approximation factor.
In this talk, I will first survey previous progress on the complexity of MDP and SVP and the pitfalls encountered in the parameterized world. Then, I will discuss how to establish W[1]-hardness of (i) MDP for linear codes over *any* finite field, (ii) SVP in ell_p norms with p>1 for *any* constant approximation factor, and (iii) SVP in the ell_1 norm for some approximation factor, thereby answering the main questions posed by previous work and providing a nearly complete picture of the W[1]-hardness of these problems.
This talk is based on joint work with Huck Bennett (Oregon State U), Mahdi Cheraghchi (U Michigan, Ann Arbor), and Venkatesan Guruswami (UC Berkeley) to be presented at STOC 2023. (Available at arxiv.org/abs/2211.07900).