Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Parameterized Inapproximability of the Minimum Distance Problem over All Fields

Simons Institute via YouTube

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

Reviews

Start your review of Parameterized Inapproximability of the Minimum Distance Problem over All Fields

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.