\input zb-basic
\input zb-ioport
\iteman{io-port 06101541}
\itemau{Haviv, Ishay}
\itemti{The remote set problem on lattices.}
\itemso{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).}
\itemab
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).
\itemrv{~}
\itemcc{}
\itemut{lattices; covering radius; remote set problem}
\itemli{doi:10.1007/978-3-642-32512-0\_16}
\end