Parameterized Inapproximability of the Minimum Distance Problem over All Fields

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.

Parameterized Inapproximability of the Minimum Distance Problem over all Fields...