Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if we let $A$ be a matrix with columns consisting of a basis for the nullspace of $\vec v^T$, can we find the smallest element of $\mathbb Z^n$ in the image of $A$?
I would also be interested in approximation algorithms, which perhaps do not give the smallest such vector but the vector $\vec w'$ they give satisfies $\|\vec w'\|_\infty/\|\vec w\|_\infty < C$ for some $C$ which does not depend of $\vec v$ (but may depend on $n$). For example an algorithm which minimizes the $\ell_2$ norm would suffice.