We study the algorithmic complexity of lattice problems based on the sieving technique due to Ajtai, Kumar, and Sivakumar~\cite{aks}. Given a $k$-dimensional subspace $M\subseteq \R^n$ and a full rank integer lattice $\L\subseteq \Q^n$, the \emph{subspace avoiding problem} SAP, defined by Bl\"omer and Naewe \cite{blomer}, is to find a shortest vector in $\L\setminus M$. We first give a $2^{O(n+k \log k)}$ time algorithm to solve \emph{the subspace avoiding problem}. Applying this algorithm we obtain the following results. \begin{enumerate} \item We give a $2^{O(n)}$ time algorithm to compute $i^{th}$ successive minima of a full rank lattice $\L\subset \Q^n$ if $i$ is $O(\frac{n}{\log n})$. \item We give a $2^{O(n)}$ time algorithm to solve a restricted \emph{closest vector problem CVP} where the inputs fulfil a promise about the distance of the input vector from the lattice. \item We also show that unrestricted CVP has a $2^{O(n)}$ exact algorithm if there is a $2^{O(n)}$ time exact algorithm for solving CVP with additional input $v_i\in \L, 1\leq i\leq n$, where $\|v_i\|_p$ is the $i^{th}$ successive minima of $\L$ for each $i$. \end{enumerate} We also give a new approximation algorithm for SAP and the \emph{Convex Body Avoiding problem} which is a generalization of SAP. Several of our algorithms work for \emph{gauge} functions as metric, where the gauge function has a natural restriction and is accessed by an oracle.
@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2008.1738, author = {Arvind, V. and Joglekar, Pushkar S.}, title = {{Some Sieving Algorithms for Lattice Problems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {25--36}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1738}, URN = {urn:nbn:de:0030-drops-17380}, doi = {10.4230/LIPIcs.FSTTCS.2008.1738}, annote = {Keywords: Lattice problems, sieving algorithm, closest vector problem} }
Feedback for Dagstuhl Publishing