A relation of primal--dual lattices and the complexity of shortest lattice vector problem
type: Item
instance of: scholarly article
title: A relation of primal--dual lattices and the complexity of shortest lattice vector problem
zbMATH Open document ID: 0926.11047
DOI: 10.1016/S0304-3975(98)00058-9
published in: Theoretical Computer Science
publication date: 1999-01-12T00:00:00Z
Mathematics Subject Classification ID: 11H55
Mathematics Subject Classification ID: 11H06
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11H50
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 1238733
zbMATH Keywords: lattice
zbMATH Keywords: shortest vector problem
zbMATH Keywords: interactive proofs
zbMATH Keywords: NP-hardness
author: Jin-Yi Cai
MaRDI profile type: Publication
cites work: Q4228459
cites work: Q4542515
cites work: Q4526993
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: Q4258570
cites work: Q4542514
cites work: Collision-Free Hashing from Lattice Problems
cites work: Q4364546
cites work: Geometric algorithms and combinatorial optimization
cites work: Q3142504
cites work: Q3751649
cites work: Dual vectors and lower bounds for the nearest lattice point problem
cites work: The Computational Complexity of Simultaneous Diophantine Approximation Problems
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: Q3745276
cites work: Q4043127
cites work: Q3770590
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Q4095873
full work available at URL: s0304-3975(98)00058-9
OpenAlex ID: W2030170158
description: scientific article; zbMATH DE number 1238733