Computer Science – Computational Complexity
Scientific paper
2008-04-30
Computer Science
Computational Complexity
Scientific paper
Given a k-dimensional subspace M\subseteq \R^n and a full rank integer lattice L\subseteq \R^n, the \emph{subspace avoiding problem} SAP is to find a shortest vector in L\setminus M. Treating k as a parameter, we obtain new parameterized approximation and exact algorithms for SAP based on the AKS sieving technique. More precisely, we give a randomized $(1+\epsilon)$-approximation algorithm for parameterized SAP that runs in time 2^{O(n)}.(1/\epsilon)^k, where the parameter k is the dimension of the subspace M. Thus, we obtain a 2^{O(n)} time algorithm for \epsilon=2^{-O(n/k)}. We also give a 2^{O(n+k\log k)} exact algorithm for the parameterized SAP for any \ell_p norm. Several of our algorithms work for all gauge functions as metric with some natural restrictions, in particular for all \ell_p norms. We also prove an \Omega(2^n) lower bound on the query complexity of AKS sieving based exact algorithms for SVP that accesses the gauge function as oracle.
Arvind Vikraman
Joglekar Pushkar S.
No associations
LandOfFree
Lattice Problems, Gauge Functions and Parameterized Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lattice Problems, Gauge Functions and Parameterized Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lattice Problems, Gauge Functions and Parameterized Algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-576675