The intractability of computing the minimum distance of a code
From MaRDI portal
Publication:4392377
DOI10.1109/18.641542zbMath1053.94583OpenAlexW2111319461MaRDI QIDQ4392377
Publication date: 28 December 1998
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2e0b89803e126a41e872f1d68eeb3e8eb71698c5
Related Items (90)
Randomized Decoding of Gabidulin Codes Beyond the Unique Decoding Radius ⋮ Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes ⋮ The inapproximability of lattice and coding problems with preprocessing ⋮ Polycyclic codes associated with trinomials: good codes and open questions ⋮ On the Parameterized Complexity of Girth and Connectivity Problems on Linear Matroids ⋮ Coding theory package for Macaulay2 ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ A database of linear codes over \(\mathbb F_{13}\) with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm ⋮ Some new quasi-twisted ternary linear codes ⋮ Solving linear equations parameterized by Hamming weight ⋮ On the complexity of and solutions to the minimum stopping and trapping set problems ⋮ An Extension of the Brouwer-Zimmermann Minimum Weight Algorithm ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ A generalization of quasi-twisted codes: multi-twisted codes ⋮ New linear codes from constacyclic codes ⋮ Performance bounds for QC-MDPC codes decoders ⋮ Regular Matroids Have Polynomial Extension Complexity ⋮ ECC\(^2\): error correcting code and elliptic curve based cryptosystem ⋮ New binary linear codes from quasi-cyclic codes and an augmentation algorithm ⋮ A formula on the weight distribution of linear codes with applications to AMDS codes ⋮ Counting 2-connected deletion-minors of binary matroids ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebraic geometric codes on anticanonical surfaces ⋮ Computing sparse multiples of polynomials ⋮ Hamming weights and Betti numbers of Stanley-Reisner rings associated to matroids ⋮ New quantum codes from metacirculant graphs via self-dual additive \(\mathbb{F}_4\)-codes ⋮ A new algorithm for equivalence of cyclic codes and its applications ⋮ New quantum codes from self-dual codes over \(\mathbb{F}_4\) ⋮ Generalized weights of codes over rings and invariants of monomial ideals ⋮ Good classical and quantum codes from multi-twisted codes ⋮ New binary and ternary quasi-cyclic codes with good properties ⋮ The weight distribution of codes over finite chain rings ⋮ On the equivalence of two post-quantum cryptographic families ⋮ Expand-convolute codes for pseudorandom correlation generators from LPN ⋮ Cyclic distances of idempotent convolutional codes ⋮ A generalization of cyclic code equivalence algorithm to constacyclic codes ⋮ Unnamed Item ⋮ The Distributions of Functions Related to Parametric Integer Optimization ⋮ A New Efficient Threshold Ring Signature Scheme Based on Coding Theory ⋮ On the Gröbner bases of some symmetric systems and their application to coding theory. ⋮ A note on edge-based graph partitioning and its linear algebraic structure ⋮ On the \(\mathbb{F}_2\)-linear relations of Mersenne Twister pseudorandom number generators ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ On the (co)girth of a connected matroid ⋮ A new iterative computer search algorithm for good quasi-twisted codes ⋮ The asymptotic probability distribution of the relative distance of additive quantum codes ⋮ Blocking optimal arborescences ⋮ COMPUTING THE DISTANCE DISTRIBUTION OF SYSTEMATIC NONLINEAR CODES ⋮ Computing girth and cogirth in perturbed graphic matroids ⋮ Some results on the structure of constacyclic codes and new linear codes over \(\mathrm{GF}(7)\) from quasi-twisted codes ⋮ Blocking unions of arborescences ⋮ Blocking optimal structures ⋮ The complexity of the weight problem for permutation and matrix groups. ⋮ Boolean autoencoders and hypercube clustering complexity ⋮ Some new linear codes from skew cyclic codes and computer algebra challenges ⋮ Sparse Solutions of Linear Diophantine Equations ⋮ A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography ⋮ Computing the spark: mixed-integer programming for the (vector) matroid girth problem ⋮ Detection and recognition of a binary linear code ⋮ Unnamed Item ⋮ \((l,s)\)-extension of linear codes ⋮ Two new zero-dimensional qubit codes from bordered metacirculant construction ⋮ Characteristic vector and weight distribution of a linear code ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ A method for efficiently computing the number of codewords of fixed weights in linear codes ⋮ A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem ⋮ A search algorithm for linear codes: Progressive dimension growth ⋮ Some generalizations of the ASR search algorithm for quasitwisted codes ⋮ Geometrical organization of solutions to random linear Boolean equations ⋮ Moment subset sums over finite fields ⋮ Unnamed Item ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ Key masking using biometry ⋮ Ensuring Message Embedding in Wet Paper Steganography ⋮ Minimal distance of propositional models ⋮ On equivalence of cyclic codes, generalization of a quasi-twisted search algorithm, and new linear codes ⋮ New linear codes over non-prime fields ⋮ A Survey of the Game “Lights Out!” ⋮ MOD-2 INDEPENDENCE AND DOMINATION IN GRAPHS ⋮ Lights Out on graphs ⋮ Linear codes from vectorial Boolean functions in the context of algebraic attacks ⋮ The highly connected matroids in minor-closed classes ⋮ Unnamed Item ⋮ Update on the Extension of Good Linear Codes ⋮ Efficient representation of binary nonlinear codes: constructions and minimum distance computation ⋮ Algorithms for the minimum weight of linear codes ⋮ 3SUM, 3XOR, triangles
This page was built for publication: The intractability of computing the minimum distance of a code
