We show that the Closest Vector
Problem with Preprocessing over infty Norm
is NP-hard to approximate to within a factor of $(\log
n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their
reductions are based on norm embeddings. However, our ... more >>>

We show that the NP-Complete language 3Sat has a PCP
verifier that makes two queries to a proof of almost-linear size
and achieves sub-constant probability of error $o(1)$. The
verifier performs only projection tests, meaning that the answer
to the first query determines at most one accepting answer to the
more >>>

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>