Approximating-CVP to within Almost-Polynomial Factors is NP-Hard

F
FOCS
1998
39th Annual Symposium on Foundations of Computer Science
Abstract - Approximating-CVP to within Almost-Polynomial Factors is NP-Hard

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by I. Dinur Articles by G. Kindler Articles by S. Safra

39th Annual Symposium on Foundations of Computer Science

Palo Alto, California

November 08-November 11

ISBN: 0-8186-9172-7

	ASCII Text	x
	I. Dinur, G. Kindler, S. Safra, "Approximating-CVP to within Almost-Polynomial Factors is NP-Hard," Foundations of Computer Science, IEEE Annual Symposium on, pp. 99, 39th Annual Symposium on Foundations of Computer Science, 1998.

	BibTex	x
	@article{ 10.1109/SFCS.1998.743433, author = {I. Dinur and G. Kindler and S. Safra}, title = {Approximating-CVP to within Almost-Polynomial Factors is NP-Hard}, journal ={Foundations of Computer Science, IEEE Annual Symposium on}, volume = {0}, year = {1998}, issn = {0272-5428}, pages = {99}, doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1998.743433}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Foundations of Computer Science, IEEE Annual Symposium on TI - Approximating-CVP to within Almost-Polynomial Factors is NP-Hard SN - 0272-5428 SP EP A1 - I. Dinur, A1 - G. Kindler, A1 - S. Safra, PY - 1998 KW - approximation KW - CVP KW - closest-vector KW - lattice. VL - 0 JA - Foundations of Computer Science, IEEE Annual Symposium on ER -

I. Dinur, Tel-Aviv University

G. Kindler, Tel-Aviv University

S. Safra, Tel-Aviv University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.1998.743433

This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to $2^{(\log{n})^{1-\epsilon}}$ where $\epsilon = (\log\log{n})^{-c} $ for any constant $c<{\frac{1}{2}}$.

Index Terms:

approximation, CVP, closest-vector, lattice.

Citation:

I. Dinur, G. Kindler, S. Safra, "Approximating-CVP to within Almost-Polynomial Factors is NP-Hard," focs, pp.99, 39th Annual Symposium on Foundations of Computer Science, 1998

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.