• DocumentCode
    2388594
  • Title

    Hardness of approximating the minimum distance of a linear code

  • Author

    Micciancio, Daniele ; Dumer, Ilya ; Sudan, Madhu

  • Author_Institution
    Dept. of Comput. Sci. & Eng., California Univ., San Diego, La Jolla, CA, USA
  • fYear
    2000
  • fDate
    2000
  • Firstpage
    252
  • Abstract
    We show that the minimum distance d of a linear code is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. In the process we show that it is hard to find the nearest codeword even if the number of errors exceeds d/2 by an arbitrarily small fraction εd
  • Keywords
    computational complexity; linear codes; polynomial approximation; NP-hardness; linear code; minimum distance; nearest codeword; random polynomial time; Computer science; Decoding; Educational institutions; Engineering profession; Lattices; Linear code; Polynomials; Quadratic programming; Random number generation; Vectors;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Information Theory, 2000. Proceedings. IEEE International Symposium on
  • Conference_Location
    Sorrento
  • Print_ISBN
    0-7803-5857-0
  • Type

    conf

  • DOI
    10.1109/ISIT.2000.866550
  • Filename
    866550
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2388594