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

on YouTube ↗48m

" summary

Proves the Minimum Distance Problem parameterized by the distance bound is W[1]-hard under randomized reductions over every fixed finite field, with no FPT algorithm that even approximates within any constant factor; extends the same parameterized inapproximability to Shortest Vector Problem in Lp for p>1. Reduction builds FPT-preserving gadgets using BCH and Reed–Solomon constructions, randomized subcode sampling and tensoring to amplify gaps, and outputs explicit generator/parity matrices and distance thresholds that witness the hardness.

AI-written summary · about

" chapters (7)

1. 0:00Minimum distance problem intro
2. 8:55Parameterized complexity basics
3. 17:31Prior hardness results
4. 29:49Challenges in reductions
5. 36:17New approach with BCH codes
6. 37:04Lattice results and L1 limits
7. 42:22Summary and open problems

" related talks

• 01h 06mHardness of the Shortest Vector Problem: A Simplified Proof and a SurveyHuck Bennett · Quantum and Lattices Joint Reunion Workshop
• 34mHigh-entropy dual functions and locally decodable codesFarrokh Labib, Jop Briet · ITCS 2021
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 59mNew Reductions and Algorithms for Ideal Lattices via Arakelov Random WalksBenjamin Wesolowski, Léo Ducas · Lattices: Geometry, Algorithms and Hardness 2020
• 36mBounded indistinguishability for simple sourcesYuval Ishai, Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Avi Kaplan, Akshayaram Srinivasan · ITCS 2022
• 01h 07mSomething about new average-case hard problems?Tselil Schramm · Obfuscation
• 29mOn Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box ReductionsMikito Nanashima · ITCS 2021
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025