loading...
Hardness of the Covering Radius Problem on Lattices
Prague, Czech Republic July 16-July 20
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2006.2321st Annual IEEE Conference on Compu ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Ishay Haviv, Oded Regev, "Hardness of the Covering Radius Problem on Lattices," Computational Complexity, Annual IEEE Conference on, pp. 145-158, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2006.23,
author = {Ishay Haviv and Oded Regev},
title = {Hardness of the Covering Radius Problem on Lattices},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2006},
issn = {1093-0159},
pages = {145-158},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.23},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Hardness of the Covering Radius Problem on Lattices
SN - 1093-0159
SP145
EP158
A1 - Ishay Haviv,
A1 - Oded Regev,
PY - 2006
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Ishay Haviv, Tel Aviv University, Israel
Oded Regev, Tel Aviv University, Israel
We provide the first hardness result for the Covering Radius Problem on lattices (CRP). Namely, we show that for any large enough p \leqslant \infty there exists a constant cp gt 1 such that CRP in the \ell \rho norm is \Pi?_2-hard to approximate to within any constant less than c_p.
Citation:
Ishay Haviv, Oded Regev, "Hardness of the Covering Radius Problem on Lattices," ccc, pp.145-158, 21st Annual IEEE Conference on Computational Complexity (CCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.