Lattice Problems, Gauge Functions and Parameterized Algorithms
| dc.creator | Arvind, V. | |
| dc.creator | Joglekar, Pushkar S. | |
| dc.date | 2008-04-30 | |
| dc.date.accessioned | 2026-07-07T09:36:00Z | |
| dc.date.available | 2026-07-07T09:36:00Z | |
| dc.description | 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+ε)$-approximation algorithm for parameterized SAP that runs in time 2^{O(n)}.(1/ε)^k, where the parameter k is the dimension of the subspace M. Thus, we obtain a 2^{O(n)} time algorithm for ε=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 Ω(2^n) lower bound on the query complexity of AKS sieving based exact algorithms for SVP that accesses the gauge function as oracle. | |
| dc.identifier | https://arxiv.org/abs/0804.4744 | |
| dc.identifier | http://arxiv.org/abs/0804.4744 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160025 | |
| dc.subject | Computational Complexity | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Lattice Problems, Gauge Functions and Parameterized Algorithms | |
| dc.type | text |