On the Limits of Nonapproximability of Lattice Problems
- 1 June 2000
- journal article
- Published by Elsevier BV in Journal of Computer and System Sciences
- Vol. 60 (3), 540-563
- https://doi.org/10.1006/jcss.1999.1686
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- A relation of primal-dual lattices and the complexity of shortest lattice vector problemTheoretical Computer Science, 1998
- The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear EquationsJournal of Computer and System Sciences, 1997
- New bounds in some transference theorems in the geometry of numbersMathematische Annalen, 1993
- Randomness in interactive proofscomputational complexity, 1993
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- Does co-NP have short interactive proofs?Information Processing Letters, 1987
- On Lovász’ lattice reduction and the nearest lattice point problemCombinatorica, 1986
- The complexity of promise problems with applications to public-key cryptographyInformation and Control, 1984
- Probabilistic encryptionJournal of Computer and System Sciences, 1984