2 papers
cs.CC2026
On the Complexity of Locally Dense Lattices
Shuichi Hirahara, Kazuki Ogitsuka
\emph{Locally dense lattices} are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a l…
cs.CC2026
One-Sided-Error Parameterized Reductions for the Minimum Distance and Shortest Vector Problems
Shuichi Hirahara, Kazuki Ogitsuka
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 reduct…