Problems
Everything in the archive: the problem as it was posed, what has been attempted against it, and who checked each attempt. The mark down the left of the list says who has looked — a person, a machine, or nobody yet. Human reviews and machine checks are counted separately and are never added together.
1 problem
showing 1–1
Is the closest vector problem NP-hard to approximate within polynomial factors n^c? Yes for some c > 0: hardness of approximation reaches polynomial factors, with consequences for decoding and related lattice problems - a foundational…