2008/04/30 by V. Arvind, Arvind, V., Pushkar S. Joglekar +1
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.0804.4744
arxiv created 2008/04/30 · openalex publication_date 2008/04/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a k-dimensional subspace M⊆ \Rn and a full rank integer lattice L⊆ \Rn, the subspace avoiding problem SAP is to find a shortest vector in L∖ 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 2O(n).(1/ε)k, where the parameter k is the dimension of the subspace M. Thus, we obtain a 2O(n) time algorithm for ε=2-O(n/k). We also give a 2O(n+klog k) exact algorithm for the parameterized SAP for any ℓp norm. Several of our algorithms work for all gauge functions as metric with some natural restrictions, in particular for all ℓp norms. We also prove an Ω(2n) lower bound on the query complexity of AKS sieving based exact algorithms for SVP that accesses the gauge function as oracle.