### Abstract

We present reductions from lattice problems in the ℓ_{2} norm to the corresponding problems in other norms such as ℓ_{1}, ℓ_{∞} (and in fact in any other ℓ_{p} norm where 1 ≤ p ≤ ∞). We consider lattice problems such as the Shortest Vector Problem, Shortest Independent Vector Problem, Closest Vector Problem and the Closest Vector Problem with Preprocessing. Most reductions are simple and follow from known constructions of embeddings of normed spaces. Among other things, our reductions imply that the Shortest Vector Problem in the ℓ_{1} norm and the Closest Vector Problem with Preprocessing in the ℓ_{∞} norm are hard to approximate to within any constant (and beyond). Previously, the former problem was known to be hard to approximate to within 2 - ε, while no hardness result was known for the latter problem.

Original language | English (US) |
---|---|

Title of host publication | STOC'06 |

Subtitle of host publication | Proceedings of the 38th Annual ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery (ACM) |

Pages | 447-456 |

Number of pages | 10 |

ISBN (Print) | 1595931341, 9781595931344 |

DOIs | |

State | Published - 2006 |

Event | 38th Annual ACM Symposium on Theory of Computing, STOC'06 - Seattle, WA, United States Duration: May 21 2006 → May 23 2006 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 2006 |

ISSN (Print) | 0737-8017 |

### Other

Other | 38th Annual ACM Symposium on Theory of Computing, STOC'06 |
---|---|

Country | United States |

City | Seattle, WA |

Period | 5/21/06 → 5/23/06 |

### Keywords

- Embedding
- Hardness of Approximation
- Lattices
- Norms

### ASJC Scopus subject areas

- Software

## Fingerprint Dive into the research topics of 'Lattice problems and norm embeddings'. Together they form a unique fingerprint.

## Cite this

*STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing*(pp. 447-456). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 2006). Association for Computing Machinery (ACM). https://doi.org/10.1145/1132516.1132581