• DocumentCode
    2142525
  • Title

    Approximating the SVP to within a factor (1-1/dimϵ) is NP-hard under randomized conditions

  • Author

    Cai, Jin-Yi ; Nerurkar, Ajay

  • Author_Institution
    Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
  • fYear
    1998
  • fDate
    15-18 Jun 1998
  • Firstpage
    46
  • Lastpage
    55
  • Abstract
    Recently M. Ajtai showed that to approximate the shortest lattice vector in the l2-norm within a factor (1+2(-dimk)), for a sufficiently large constant k, is NP-hard under randomized reductions. We improve this result to show that to approximate a shortest lattice vector within a factor (1+dim-ε), for any ε>0, is NP-hard under randomized reductions. Our proof also works for arbitrary lp-norms, 1⩽p<∞
  • Keywords
    computational complexity; randomised algorithms; NP-hard; randomized conditions; shortest lattice vector; Computer science; Gaussian processes; Geometry; History; Lagrangian functions; Lattices; Polynomials; Public key cryptography; Radio access networks; Vectors;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 1998. Proceedings. Thirteenth Annual IEEE Conference on
  • Conference_Location
    Buffalo, NY
  • ISSN
    1093-0159
  • Print_ISBN
    0-8186-8395-3
  • Type

    conf

  • DOI
    10.1109/CCC.1998.694590
  • Filename
    694590
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2142525