May 17th, at 14:30, Room FC6 1.40 (S2), Department of Computer Science, FCUP
Please register: https://forms.gle/m4Q9QDDaniHVunge9
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).
Short biography
João Ribeiro is an Assistant Professor in the Department of Computer Science of Universidade Nova de Lisboa and a researcher at NOVA LINCS. Previously, he was a Post Doctoral Fellow in the Computer Science Department of Carnegie Mellon University, hosted jointly by Vipul Goyal and Venkatesan Guruswami. João received his PhD from the Department of Computing of Imperial College London, where he was advised by Mahdi Cheraghchi. Before that, he received an MSc in Computer Science from ETH Zurich and a BSc in Applied Mathematics and Computation from Instituto Superior Técnico.
He has broad interests within theoretical computer science, with special emphasis on pseudorandomness, coding theory, and cryptography (plus the connections between these areas).
More details can be found at https://sites.google.com/site/joaorib94/.
About Talks@DCC :
The mission of the Talks@DCC seminars is to bring together researchers and students, to foster discussions and promote scientific awareness and collaboration. Participate: attend and propose your talk.