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òs Conjecture.
|Original language||English (US)|
|Title of host publication||Information and Communications Security - 18th International Conference, ICICS 2016, Proceedings|
|Editors||Kwok-Yan Lam, Sihan Qing, Chi-Hung Chi|
|Number of pages||10|
|State||Published - 2016|
|Event||18th International Conference on Information and Communications Security, ICICS 2016 - Singapore, Singapore|
Duration: Nov 29 2016 → Dec 2 2016
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Other||18th International Conference on Information and Communications Security, ICICS 2016|
|Period||11/29/16 → 12/2/16|
Bibliographical noteFunding Information:
This work was supported by National Natural Science Foundation of China (Grant No. 61272039).
© Springer International Publishing AG 2016.
- Equivalent norms
- Hölder’s inequality
- The variant of remote set problem