06101541

a

06101541 Haviv, Ishay The remote set problem on lattices. Gupta, Anupam (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 15th international workshop, APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge, MA, USA, August 15--17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32511-3/pbk). Lecture Notes in Computer Science 7408, 182-193 (2012). 2012 Berlin: Springer EN lattices covering radius remote set problem

doi:10.1007/978-3-642-32512-0_16

Summary: We initiate studying the Remote Set Problem (RSP) on lattices, which given a lattice asks to find a set of points containing a point which is far from the lattice. We show a polynomial-time deterministic algorithm that on rank $n$ lattice ${\mathcal L}$ outputs a set of points at least one of which is $\sqrt{\log n / n} \cdot \rho({\mathcal L})$-far from ${\mathcal L}$, where $\rho({\mathcal L})$ stands for the covering radius of ${\mathcal L}$ (i.e., the maximum possible distance of a point in space from ${\mathcal L}$). As an application, we show that the Covering Radius Problem with approximation factor $\sqrt{n /\log n}$ lies in the complexity class NP, improving a result of Guruswami, Micciancio and Regev by a factor of $\sqrt{\log n}$ (Computational Complexity, 2005). Our results apply to any $\ell _{p }$ norm for $2 \leq p \leq \infty $ with the same approximation factors (except a loss of $\sqrt{\log \log n}$ for $p = \infty )$. In addition, we show that the output of our algorithm for RSP contains a point whose $\ell _{2}$ distance from ${\mathcal L}$ is at least $(\log n / n)^{1/p} \cdot \rho^{(p)}({\mathcal L})$, where $\rho^{(p)}({\mathcal L})$ is the covering radius of ${\mathcal L}$ measured with respect to the $\ell _{p }$ norm. The proof technique involves a theorem on balancing vectors due to Banaszczyk (Random Struct. Alg., 1998) and the `six standard deviations' theorem of Spencer (Trans. AMS, 1985).