あとで読む (uSVP関連)

某所で頂いたコメントより.

  • R. Kumar, D. Sivakumar "On the unique shortest lattice vector problem" (TCS 2001)
    • uSVPのexact versionのNP-hardnessについて.
  • A. Frieze "On the Lagariaz-Odlyzko algorithm for the subset-sum problem" (SIAM J. of Comp. 1986)
    • uSVPの近似度が小さい場合が解けるなら, 低密度のsubset sumのaverage-caseが解ける. SVPじゃなくって, uSVPってのは面白い.