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 n c (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 N c ′ / 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. [ABSTRACT FROM AUTHOR]