A Deterministic Reduction for the Gap Minimum Distance Problem

No abstract is available for this paper.

• Publication year

  2009

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2009-05-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1536414.1536421
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

  2010cited by this paper
• Complexity of Decoding Positive-Rate Reed-Solomon Codes

  2008cited by this paper
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors

  2007cited by this paper
• On the List and Bounded Distance Decodability of Reed-Solomon Codes

  2007cited by this paper
• Hardness of approximating the shortest vector problem in lattices

  2004cited by this paper
• Hardness of approximating the minimum distance of a linear code

  2000cited by this paper
• Approximating the SVP to within a Factor (1+1/dimxi) Is NP-Hard under Randomized Reductions

  1999cited by this paper
• Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions

  1998cited by this paper
• The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)

  1998influential reference
• The shortest vector in a lattice is hard to approximate to within some constant

  1998cited by this paper
• Generators and irreducible polynomials over finite fields

  1997cited by this paper
• The intractability of computing the minimum distance of a code

  1997influential reference
• Approximating the SVP to within a factor (1 + 1/dimepsilon) is NP-hard under randomized reductions

  1997cited by this paper
• The hardness of approximate optima in lattices, codes, and systems of linear equations

  1993cited by this paper
• New algorithms for finding irreducible polynomials over finite fields

  1988cited by this paper
• On the inherent intractability of certain coding problems (Corresp.)

  1978cited by this paper
• The complexity of theorem-proving procedures

  1971influential reference

• PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

  2025cites this paper
• On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

  2025cites this paper
• On the hardness of approximating minimum distances of quantum codes

  2025cites this paper
• Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices

  2024cites this paper
• Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH

  2024cites this paper
• Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

  2024cites this paper
• Subset sums over Galois rings II

  2023cites this paper
• The Complexity of the Shortest Vector Problem

  2023cites this paper
• Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon Codes

  2022cites this paper
• Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms

  2022influential citation
• On Succinct Arguments and Witness Encryption from Groups

  2020cites this paper
• Distance Distribution in Reed-Solomon Codes

  2020cites this paper
• Hardness of Successive-Cancellation Decoding of Linear Codes

  2020cites this paper
• Subset sums over Galois rings

  2019cites this paper
• SETH-Hardness of Coding Problems

  2019influential citation
• Approximation and Hardness: Beyond P and NP

  2019cites this paper
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)

  2019cites this paper
• Parameterized Intractability of Even Set and Shortest Vector Problem

  2019cites this paper
• Distance Distribution to Received Words in Reed-Solomon Codes

  2018cites this paper
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

  2018cites this paper
• Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

  2018cites this paper
• Counting polynomials with distinct zeros in finite fields

  2017cites this paper
• Title Distance Verification for Classical and Quantum LDPC Codes Permalink

  2016cites this paper
• On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes

  2016cites this paper
• Bi-Covering: Covering Edges with Two Small Subsets of Vertices

  2016cites this paper
• Hardness of Bipartite Expansion

  2016cites this paper
• Distance verification for LDPC codes

  2016cites this paper
• Distance Verification for Classical and Quantum LDPC Codes

  2016cites this paper
• On the minimum distance of elliptic curve codes

  2015cites this paper
• On the hardness of learning sparse parities

  2015cites this paper
• Solving Linear Equations Parameterized by Hamming Weight

  2014cites this paper
• Résultants de polynômes de Ore et Cryptosystèmes de McEliece sur des Codes Rang faiblement structurés. (Resultants of Ore polynomials and McEliece Cryptosystems based on weakly structured Rank Codes)

  2014cites this paper
• Locally Dense Codes

  2014influential citation
• The distribution of factorization patterns on linear families of polynomials over a finite field

  2014cites this paper
• Stopping Set Distributions of Algebraic Geometry Codes from Elliptic Curves

  2012cites this paper
• Inapproximability Results for the Weight Problems of Subgroup Permutation Codes

  2012cites this paper
• Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

  2012influential citation
• On the Minimum Degree Up to Local Complementation: Bounds and Complexity

  2012cites this paper
• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem

  2010cites this paper
• A new sieve for distinct coordinate counting

  2010cites this paper