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, Sanjeev Arora, 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

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