Infoscience

Journal article

Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n). © 2014 Society for Industrial and Applied Mathematics.

    Reference

    Record created on 2015-09-16, modified on 2017-07-25

Fulltext

Related material

Contacts

EPFL authors