The Projection Games Conjecture and the hardness of approximation of super-SAT and related problems

摘要

The Super-SAT (SSAT) problem was introduced in [1], [2] to prove the NP-hardness of approximation of two popular lattice problems - Shortest Vector Problem and Closest Vector Problem. SSAT is conjectured to be NP-hard to approximate to within a factor of nc (c is positive constant, n is the size of the SSAT instance). In this paper we prove this conjecture assuming the Projection Games Conjecture (PGC) [3]. This implies hardness of approximation of these lattice problems within polynomial factors, assuming PGC. We also reduce SSAT to the Nearest Codeword Problem and Learning Halfspace Problem [4]. This proves that both these problems are NP-hard to approximate within a factor of Nc′/log⁡log⁡n (c′ is positive constant, N is the size of the instances of the respective problems). Assuming PGC these problems are proved to be NP-hard to approximate within polynomial factors.