Solving the Closest Vector Problem with respect to Lp Norms

J. Blömer, S. Naewe, ArXiv:1104.3720 (2011).

Preprint
Author
Blömer, JohannesLibreCat; Naewe, Stefanie
Abstract
In this paper, we present a deterministic algorithm for the closest vector problem for all l_p-norms, 1 < p < \infty, and all polyhedral norms, especially for the l_1-norm and the l_{\infty}-norm. We achieve our results by introducing a new lattice problem, the lattice membership problem. We describe a deterministic algorithm for the lattice membership problem, which is a generalization of Lenstra's algorithm for integer programming. We also describe a polynomial time reduction from the closest vector problem to the lattice membership problem. This approach leads to a deterministic algorithm that solves the closest vector problem for all l_p-norms, 1 < p < \infty, in time p log_2 (r)^{O (1)} n^{(5/2+o(1))n} and for all polyhedral norms in time (s log_2 (r))^{O (1)} n^{(2+o(1))n}, where s is the number of constraints defining the polytope and r is an upper bound on the coefficients used to describe the convex body.
Publishing Year
Journal Title
arXiv:1104.3720
LibreCat-ID

Cite this

Blömer J, Naewe S. Solving the Closest Vector Problem with respect to Lp Norms. arXiv:11043720. 2011.
Blömer, J., & Naewe, S. (2011). Solving the Closest Vector Problem with respect to Lp Norms. ArXiv:1104.3720.
@article{Blömer_Naewe_2011, title={Solving the Closest Vector Problem with respect to Lp Norms}, journal={arXiv:1104.3720}, author={Blömer, Johannes and Naewe, Stefanie}, year={2011} }
Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem with Respect to Lp Norms.” ArXiv:1104.3720, 2011.
J. Blömer and S. Naewe, “Solving the Closest Vector Problem with respect to Lp Norms,” arXiv:1104.3720. 2011.
Blömer, Johannes, and Stefanie Naewe. “Solving the Closest Vector Problem with Respect to Lp Norms.” ArXiv:1104.3720, 2011.

Export

Marked Publications

Open Data LibreCat
{"ft_lang_label":"__label__en","ft_lang_prob":0.7810059,"math_prob":0.6172649,"size":1973,"snap":"2022-05-2022-21","text_gpt3_token_len":610,"char_repetition_ratio":0.14271204,"word_repetition_ratio":0.24561404,"special_character_ratio":0.28028384,"punctuation_ratio":0.18987341,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9615606,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-01-23T21:14:55Z\",\"WARC-Record-ID\":\"<urn:uuid:0e3a9f15-ebe8-4fd5-811d-dad4716580f0>\",\"Content-Length\":\"24082\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b178bf7f-790f-4288-a7e8-98e785f57bcd>\",\"WARC-Concurrent-To\":\"<urn:uuid:59b8e9b4-9916-47b5-93e5-259f844fb727>\",\"WARC-IP-Address\":\"131.234.9.110\",\"WARC-Target-URI\":\"https://ris.uni-paderborn.de/record/2987\",\"WARC-Payload-Digest\":\"sha1:XIHOHFUXZ4EAVMPVTCFWRQW4AJW4UPVJ\",\"WARC-Block-Digest\":\"sha1:RZSBYFQRPELGISFRZL2BR6AXNHUWRXFF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-05/CC-MAIN-2022-05_segments_1642320304309.59_warc_CC-MAIN-20220123202547-20220123232547-00202.warc.gz\"}"}