The hardness of approximate optima in lattices, codes, and systems of linear equations

DOI10.1006/jcss.1997.1472zbMath0877.68067OpenAlexW3144422206MaRDI QIDQ1356888

Z. Sweedyk, László Babai, Jacques Stern

Publication date: 8 December 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/286348b7a7342a72186f91430569f0a2503f46a7

zbMATH Keywords

binary codes nearest codeword problem nearest lattice vector problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (68)

Meta-heuristic approaches to solve shortest lattice vector problem ⋮ On regularity of Max-CSPs and Min-CSPs ⋮ Approximating multidimensional subset sum and Minkowski decomposition of polygons ⋮ When a Constant Classifier is as Good as Any Linear Classifier ⋮ Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ The inapproximability of lattice and coding problems with preprocessing ⋮ Matrix sparsification and the sparse null space problem ⋮ Sparse approximation is provably hard under coherent dictionaries ⋮ On the complexity of learning from drifting distributions ⋮ On generalizations of network design problems with degree bounds ⋮ NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ Intractability of assembly sequencing: Unit disks in the plane ⋮ Goal scoring, coherent loss and applications to machine learning ⋮ Positive-unlabeled classification under class-prior shift: a prior-invariant approach based on density ratio estimation ⋮ On the difficulty of approximately maximizing agreements. ⋮ Approximation and hardness results for label cut and related problems ⋮ Mathematics of computation through the lens of linear equations and lattices ⋮ Hardness results for homology localization ⋮ More on average case vs approximation complexity ⋮ Improved approximation algorithms for label cover problems ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ Sparse weighted voting classifier selection and its linear programming relaxations ⋮ Approximating the SVP to within a factor $(1+1/\dim^\varepsilon)$ is NP-hard under randomized reductions ⋮ On the adaptivity gap in two-stage robust linear optimization under uncertain packing constraints ⋮ Approximation algorithms for the Label-Cover$_{\text{MAX}}$ and Red-Blue Set Cover problems ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Minimum propositional proof length is NP-hard to linearly approximate ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over $\ell_\infty$ norm ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Approximability of Capacitated Network Design ⋮ On Tree-Constrained Matchings and Generalizations ⋮ A code-based group signature scheme ⋮ A semidefinite programming method for integer convex quadratic minimization ⋮ Approximating maximum satisfiable subsystems of linear equations of bounded width ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ On the maximum edge-pair embedding bipartite matching ⋮ On tree-constrained matchings and generalizations ⋮ Restricted parameter range promise set cover problems are easy ⋮ The Next Whisky Bar ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Hardness of approximating the shortest vector problem in high $\ell_{p}$ norms ⋮ Inapproximability results for equations over infinite groups ⋮ On the approximability of minmax (regret) network optimization problems ⋮ Training a Single Sigmoidal Neuron Is Hard ⋮ The checkpoint problem ⋮ Unnamed Item ⋮ The ordered covering problem ⋮ Algorithmic Problems for Metrics on Permutation Groups ⋮ The Diagonal Reduction Algorithm Using Fast Givens ⋮ Comment ⋮ New Results on the Complexity of the Max- and Min-Rep Problems ⋮ A theory of learning with similarity functions ⋮ The Geometry of Lattice Cryptography ⋮ Hardness of approximating the minimum solutions of linear Diophantine equations ⋮ On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ A note on the subadditive network design problem ⋮ Minimal distance of propositional models ⋮ On the limits of nonapproximability of lattice problems ⋮ On the hardness of approximating max-satisfy ⋮ On the hardness of approximating the min-hack problem ⋮ Derandomized graph products ⋮ A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. ⋮ On approximate learning by multi-layered feedforward circuits ⋮ A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor ⋮ Hardness results for neural network approximation problems ⋮ Approximating $SVP_{\infty}$ to within almost-polynomial factors is NP-hard

Cites Work

This page was built for publication: The hardness of approximate optima in lattices, codes, and systems of linear equations