@inproceedings{fe34380b9217449d9899ff69c3f87156,

title = "The variant of remote set problem on lattices",

abstract = "In 2015, Haviv proposed the Remote Set Problem (RSP) on lattices and gave a deterministic algorithm to find a set containing a point which is O(√k/n) far from the lattice in ℓp norm for 2 ≤ p≤∞, where n is the lattice rank and k divides n. Inspired by it, we propose the variant of Remote Set Problem on Lattices (denoted by V-RSP) that only depends on parameter γ ≤ 1. We obtain that the complexity classes that V-RSP belong to with the change of parameter γ. Using some elementary tools, we can solve V-RSP that can find a set containing a point which is O(k/n) far from the lattice in any ℓp norm for 1 ≤ p≤∞. Furthermore, we also study relationships between ℓ2 distance from a point to a lattice L and covering radius (ρ(p)(L)), where ρ(p)(L) is defined with respect to the ℓp norm for 1 ≤ p ≤ ∞, here, for p = ∞, our proof does not rely on Koml{\`o}s Conjecture.",

keywords = "Equivalent norms, H{\"o}lder{\textquoteright}s inequality, Lattice, The variant of remote set problem",

author = "Wenwen Wang and Kewei Lv and Jianing Liu",

year = "2016",

doi = "10.1007/978-3-319-50011-9_10",

language = "English (US)",

isbn = "9783319500102",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "124--133",

editor = "Kwok-Yan Lam and Sihan Qing and Chi-Hung Chi",

booktitle = "Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings",

note = "18th International Conference on Information and Communications Security, ICICS 2016 ; Conference date: 29-11-2016 Through 02-12-2016",

}