loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07)
Limits on the Hardness of Lattice Problems in \ell _p Norms
San Diego, California
June 13-March 16
ISBN: 0-7695-2780-9
ASCII Text
x 
 
Chris Peikert, "Limits on the Hardness of Lattice Problems in \ell _p Norms," Computational Complexity, Annual IEEE Conference on, pp. 333-346, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2007.12,
author = {Chris Peikert},
title = {Limits on the Hardness of Lattice Problems in \ell _p Norms},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2007},
issn = {1093-0159},
pages = {333-346},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2007.12},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Limits on the Hardness of Lattice Problems in \ell _p Norms
SN - 1093-0159
SP333
EP346
A1 - Chris Peikert,
PY - 2007
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
Chris Peikert, SRI International, MIT, USA
We show that several recent "positive" results for lattice problems in the \ell _2 norm also hold in \ell _p norms, for p \ge 2. In particular, for lattices of dimension n:

Approximating the shortest and closest vector in the \ell _p norm to within \tilde O (\sqrt n) factors is contained in coNP.

Approximating the length of the shortest vector in the \ell _p norm to within \tilde O(n) factors reduces to the average-case problems studied in related works (Ajtai, STOC 1996; Micciancio and Regev, FOCS 2004; Regev, STOC 2005).

These results improve upon prior understanding of \ell _p norms by up to \sqrt n factors. Taken together, they can be viewed as a partial converse to recent reductions from the \ell _2 norm to \ell _p norms (Regev and Rosen, STOC 2006).

One of our main technical contributions is a very general analysis of Gaussian distributions over lattices, which may be of independent interest. Our proofs employ analytical techniques of Banaszczyk which, to our knowledge, have yet to be exploited in computer science.

Citation:
Chris Peikert, "Limits on the Hardness of Lattice Problems in \ell _p Norms," ccc, pp.333-346, Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.