The hardness of approximate optima in lattices, codes, and systems of linear equations
type: Item
instance of: scholarly article
title: The hardness of approximate optima in lattices, codes, and systems of linear equations
zbMATH Open document ID: 0877.68067
author: László Babai
author: Jacques Stern
author: Z. Sweedyk
author: Sanjeev Arora
published in: Journal of Computer and System Sciences
publication date: 1997-12-08T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1022057
zbMATH Keywords: nearest lattice vector problem
zbMATH Keywords: nearest codeword problem
zbMATH Keywords: binary codes
MaRDI profile type: Publication
OpenAlex ID: W3144422206
cites work: The complexity and approximability of finding maximum feasible subsystems of linear relations
cites work: Q3002852
cites work: Q4230322
cites work: Q4230321
cites work: On Lovász' lattice reduction and the nearest lattice point problem
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: Efficient probabilistically checkable proofs and applications to approximations
cites work: On the inherent intractability of certain coding problems (Corresp.)
cites work: Designing programs that check their work
cites work: Self-testing/correcting with applications to numerical problems
cites work: Q3726125
cites work: The hardness of decoding linear codes with preprocessing
cites work: The complexity of the max word problem and the power of one-way interactive proof systems
cites work: Q4198056
cites work: The densest hemisphere problem
cites work: Minkowski's Convex Body Theorem and Integer Programming
cites work: Q4142699
cites work: Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
cites work: Solving low-density subset sum problems
cites work: Factoring polynomials with rational coefficients
cites work: On the hardness of approximating minimization problems
cites work: Optimization, approximation, and complexity classes
cites work: Q3770590
cites work: Q4279529
DOI: 10.1006/JCSS.1997.1472
description: scientific article; zbMATH DE number 1022057