## Abstract

We present a new hardness of approximation result for the Shortest Vector Problem in ℓp norm (denoted by SVPp). Assuming NP ⊈ ZPP, we show that for every ε>0, there is a constant p(ε) such that for all integers p≥p(ε), the problem SVPp has no polynomial time approximation algorithm with approximation ratio p1-ε.

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

Pages (from-to) | 206-219 |

Number of pages | 14 |

Journal | Journal of Computer and System Sciences |

Volume | 72 |

Issue number | 2 |

DOIs | |

State | Published - Mar 2006 |

## Keywords

- Approximation algorithms
- Computational complexity
- Hardness of approximation
- Lattices
- Shortest vector problem

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'Hardness of approximating the Shortest Vector Problem in high ℓ_{p}norms'. Together they form a unique fingerprint.