Parameterized Inapproximability of the Minimum Distance Problem over All Fields
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a 48-minute lecture on the Minimum Distance Problem (MDP) for linear codes and the Shortest Vector Problem (SVP) on integer lattices. Delve into the proof of W[1]-hardness for MDP over all finite fields, addressing a longstanding open problem in parameterized complexity. Examine the extension of these results to SVP in various norms, resolving key questions in lattice theory. Learn about the inapproximability of these problems within any constant factor, and understand the implications for error-correcting codes and lattice-based cryptography. Gain insights from the collaborative work of Venkatesan Guruswami, Huck Bennett, Mahdi Cheraghchi, and João Ribeiro, presented at the Simons Institute as part of the "Advances in the Theory of Error-Correcting Codes" series.
Syllabus
Parameterized Inapproximability of the Minimum Distance Problem over all Fields...
Taught by
Simons Institute
Related Courses
A Parameterized Approximation Scheme for Min k-CutIEEE via YouTube Parameterized Complexity of Quantum Invariants of Knots
Applied Algebraic Topology Network via YouTube Sparse Integer Programming Is FPT
Hausdorff Center for Mathematics via YouTube Recent Hardness of Approximation Results in Parameterized Complexity
Hausdorff Center for Mathematics via YouTube Parametrized Algorithms and Possible Future Directions
Hausdorff Center for Mathematics via YouTube