A Deterministic Reduction for the Gap Minimum Distance Problem

DOI10.1109/TIT.2012.2209198MaRDI QIDQ2989711zbMATH OpenOpenAlexFDO

Authors Qi Cheng, Daqing Wan

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tit.2012.2209198

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Recommendations

• A deterministic reduction for the gap minimum distance problem (extended abstract)
• A simple deterministic reduction for the gap minimum distance of code problem
• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
• Approximation algorithms for min-distance problems
• A deterministic algorithm for the cost-distance problem
• The rectilinear distance minisum problem with minimum distance constraints:
• scientific article; zbMATH DE number 1305459
• Minimum-distance bounds by graph analysis
• A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
• A Schur analysis approach to minimum distance problems

Cited in

(14)

• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• Subset sums over Galois rings
• Solving linear equations parameterized by Hamming weight
• Parameterized intractability of even set and shortest vector problem from Gap-ETH
• Counting polynomials with distinct zeros in finite fields
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
• A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
• Subset sums over Galois rings. II
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all _p norms
• Parameterized inapproximability of the minimum distance problem over all fields and the shortest vector problem in all \(\ell_{p}\) norms
• Improved lower bounds for approximating parameterized nearest codeword and related problems under ETH
• Approximating the number of relevant variables in a parity implies proper learning
• On the constant-factor approximability of minimum cost constraint satisfaction problems

This page was built for publication: A Deterministic Reduction for the Gap Minimum Distance Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989711)