2026-09-10T09:44:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27763 2026-09-09T12:19:37Z ddc:004 open_access

One-Sided-Error Parameterized Reductions for the Minimum Distance and Shortest Vector Problems Hirahara, Shuichi Ogitsuka, Kazuki Codes Lattices Minimum Distance Problem Shortest Vector Problem Parameterized complexity derandomization It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error randomized reductions, Bennett, Cheraghchi, Guruswami, and Ribeiro (STOC 2023) proved parameterized hardness of approximation for these problems. We partially derandomize their reductions and present one-sided-error randomized reductions: MDP is W[1]-hard to approximate within an arbitrary constant factor under FPT many-one one-sided-error randomized reductions; For every fixed p ≥ 1, SVP in the 𝓁_p norm is W[1]-hard to approximate within an arbitrary constant factor below 2^{1/p}. We demonstrate the usefulness of one-sided-error randomized reductions by showing that they can be conditionally derandomized when the target problem has an OR function. Under a standard hardness-vs-randomness assumption, namely a plausible lower-bound assumption against nondeterministic circuits, we prove a general theorem formalizing this derandomization. Here, an OR function combines several instances into one instance that preserves their disjunction. We construct such OR functions for the relevant MDP and SVP gap problems, and thereby obtain deterministic W[1]-hardness for approximating MDP over every fixed finite field within every constant factor, and for approximating SVP in 𝓁_p norms for every fixed integer p within every factor below 2^{1/p}. Applying the same framework to Micciancio’s one-sided-error randomized reduction (ToC 2012) yields, under the same circuit lower-bound assumption, deterministic polynomial-time NP-hardness of approximating Euclidean SVP within every constant factor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuichi Hirahara and Kazuki Ogitsuka 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.46 urn:nbn:de:0030-drops-277637 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.46 eng https://creativecommons.org/licenses/by/4.0/legalcode