Improved Inapproximability of Lattice and Coding Problems with Preprocessing

CC
CCC
2003
18th Annual IEEE Conference on Computational Complexity (CCC'03)
Abstract - Improved Inapproximability of Lattice and Coding Problems with Preprocessing

	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 Oded Regev

18th Annual IEEE Conference on Computational Complexity (CCC'03)

Aarhus, Denmark

July 07-July 10

ISBN: 0-7695-1879-6

	ASCII Text	x
	Oded Regev, "Improved Inapproximability of Lattice and Coding Problems with Preprocessing," Computational Complexity, Annual IEEE Conference on, pp. 363, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003.

	BibTex	x
	@article{ 10.1109/CCC.2003.1214435, author = {Oded Regev}, title = {Improved Inapproximability of Lattice and Coding Problems with Preprocessing}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2003}, issn = {1093-0159}, pages = {363}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214435}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Improved Inapproximability of Lattice and Coding Problems with Preprocessing SN - 1093-0159 SP EP A1 - Oded Regev, PY - 2003 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Oded Regev, Institute for Advanced Study

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214435

We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within \sqrt {3 - \varepsilon } for any \varepsilon > 0. In addition, we show that the nearest codeword problem with preprocessing (NCPP) is NP-hard to approximate to within 3 -\varepsilon . These results improve the results of Feige and Micciancio in [10]. We also present the first Inapproximability result for the relatively nearest codeword problem with preprocessing (RNCP). Finally, we describe an n-approximation algorithm to CVPP.

Citation:

Oded Regev, "Improved Inapproximability of Lattice and Coding Problems with Preprocessing," ccc, pp.363, 18th Annual IEEE Conference on Computational Complexity (CCC'03), 2003

Peer Review Notice | Give Us Feedback

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