On the limits of nonapproximability of lattice problems
type: Item
instance of: scholarly article
title: On the limits of nonapproximability of lattice problems
zbMATH Open document ID: 0961.68122
author: Oded Goldreich
author: Shafi Goldwasser
published in: Journal of Computer and System Sciences
publication date: 2001-05-28T00:00:00Z
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 1497376
zbMATH Keywords: computational problems in integer lattices
zbMATH Keywords: interactive proof systems
MaRDI profile type: Publication
OpenAlex ID: W2169690324
cites work: Q4228459
cites work: Q4542515
cites work: Q4526993
cites work: Q5577281
cites work: The hardness of approximate optima in lattices, codes, and systems of linear equations
cites work: On Lovász' lattice reduction and the nearest lattice point problem
cites work: New bounds in some transference theorems in the geometry of numbers
cites work: Randomness in interactive proofs
cites work: An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information
cites work: Does co-NP have short interactive proofs ?
cites work: A relation of primal--dual lattices and the complexity of shortest lattice vector problem
cites work: A random polynomial-time algorithm for approximating the volume of convex bodies
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Q4228484
cites work: Q4364546
cites work: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
cites work: Q4542558
cites work: Probabilistic encryption
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: Geometric algorithms and combinatorial optimization
cites work: Dual vectors and lower bounds for the nearest lattice point problem
cites work: Q4526964
cites work: Q5585020
cites work: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
cites work: Factoring polynomials with rational coefficients
cites work: Integer Programming with a Fixed Number of Variables
cites work: Q4228522
cites work: A hierarchy of polynomial time lattice basis reduction algorithms
DOI: 10.1006/JCSS.1999.1686
description: scientific article; zbMATH DE number 1497376