Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > GAUSSIAN MEASURES:
Reports tagged with Gaussian measures:
TR06-148 | 4th December 2006
Chris Peikert

#### Limits on the Hardness of Lattice Problems in $\ell_p$ Norms

Revisions: 1

We show that for any $p \geq 2$, lattice problems in the $\ell_p$
norm are subject to all the same limits on hardness as are known
for the $\ell_2$ norm. In particular, for lattices of dimension
$n$:

* Approximating the shortest and closest vector in ... more >>>

ISSN 1433-8092 | Imprint