Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.

My questions are as follows. Suppose that, I restrict myself to the following optimization problem: $$ \min_{y\in\Lambda:y=Bx,x_i\in\{-1,1\}} \|y\|_2. $$ This is nothing but the shortest vector problem with $x$ restricted, and it is well-known that LLL algorithm approximates the shortest vector problem (in unconstrained setup) in polynomial time. Are there complexity results (in particular, average case complexity), for such problems that anyone is aware of?

A second question pertains a close cousin of this problem, namely, the closest vector problem. Suppose, I fix a vector $z$ with rational (or integer coefficients), and I am asking for the member of lattice $\Lambda$ that is closest to $z$, namely, $$ \min_{y\in \Lambda,y=Bx,x_i\in\{-1,1\}} \|y-z\|_2. $$ A similar question goes. Are there any average-case hardness results (or in general, any sort of hardness for this restricted scheme) that anyone is aware of?

  • $\begingroup$ One could experiment with LLL for a linear combination of $||y||^2_2$ and $||x||^2_2$. $\endgroup$ – Wilberd van der Kallen Dec 7 '18 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.