# Questions tagged [coding-theory]

The mathematical theory of codes, as used in communication, data compression, and cryptography.

93 questions
Filter by
Sorted by
Tagged with
68 views

### How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...
34 views

### Attacks on Niederreiter cryptosystem

Guo et al presented an attack on QC LDPC McEliece cryptosystem. Before that, a similar attack was presented on QC MDPC in Asiacrypt by Guo et al. Do these attacks also work on Niederreiter ...
73 views

### Quantum security of cryptosystems

One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup ...
48 views

Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$. The minimum distance $d$ is given by $d= min\lbrace k \text{ such that there are$k$linearly ... 0answers 90 views ### Where in$PH$are these problems? Is 'Given two codes with alphabet in$\mathbb F_2$with Generator matrices$G_1$and$G_2$do they have the same minimum distance?' in$NP$or is it in$coNP$(I can see it in$P^{NP}$)? If$G_1$is ... 1answer 128 views ### Minimum distance of a code Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number$d$such that there exists$d$linearly dependant columns. I am ... 0answers 26 views ### Minimum distance of a code [duplicate] Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number$d$such that there exists$d$linearly dependant columns. I am ... 2answers 61 views ### Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d? I'm not sure I can find an explicit formula. Wondering if anyone can come up with lower/upper bounds. 0answers 66 views ### Explicit Formula of Delsarte's Linear Programming Upper Bound for$A_q(n,3)$The problem of giving an explicit formula for$A_q(n,d)$is sometimes referred to as "the main problem in coding theory." The value of$A_q(n,d)$is given by the maximum number of codewords in a q-ary ... 2answers 201 views ### Why can't codes be defined over infinite fields? In Coding Theory, people use$q$-ary alphabets: why do we need a finite set? Why can't we define codes over infinite sets. such as$\mathbb{R}$or$\mathbb{C}$? 0answers 71 views ### Error correction with asymmetric channel Suppose A is trying to transmit a message to B over a noisy low bandwidth channel, while B has the ability to simultaneously transmit arbitrary amounts of information losslessly to A. Are there ... 1answer 99 views ### Does a code need at least two symbols to be defined as a code? [closed] I am wondering whether you could still call a code something that, if transmitting, only transmits one symbol. Or does the formal definition of code require 2 or more symbols? (and would the answer ... 0answers 72 views ### Function which detects rotation of bit string Consider a function$F: \mathbb{F}_2^d \to \mathbb{Z}^n = (f_1,\ldots,f_n)$with the property that if$y \in \mathbb{F}_2^d$is a rotation of$x \in \mathbb{F}_2^d$, i.e.$y$is$x$permuted by an ... 1answer 124 views ### Why are folded Reed Solomon Codes considered non linear? This is for my understanding. What am I missing? 1answer 53 views ### Families of LDPC codes with constant error fraction corrected I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm. For example, I know that Sipser and Spielman proved that there is an ... 0answers 134 views ### Unit hypercube encodings How can we chose to place$k$points in$[0,1]^d$, such that the minimum Euclidian distance between any two points is maximized? Is there a more common term for these combinatorial designs than unit ... 2answers 617 views ### Relation between group theory and information theory Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory). Question: Is there any paper/survey ... 1answer 175 views ### Structured set of binary words Definitions: Let$n\in \mathbb N$be an integer, and consider the field$\mathbb K=GF(2^n)$. For$c\in \mathbb N$, let$S_c$be a set of$n$elements from$\mathbb K$such that: Every element$e$... 1answer 106 views ### The noise distribution on$F_2^n$: probability of landing in a subspace versus a coset Let$V = F_2^n$be the$n$-dimensional vector space over the field of two elements. The$\epsilon$-noise distribution on$V$, denoted$\mu_\epsilon$, is a probability distribution on$V$for which ... 0answers 146 views ### The edit distance of BWT of two strings with one difference Let$BWT$stand for the Burrows-Wheeler transform on strings. What is the maximal edit distance of$BWT(w)$and$BWT(u)$, if$w$and$u$differ only in one character. 0answers 70 views ### Convex hull of codebook (LP-decoding) So the well-cited article by Feldman et al from 2005 has a method of constructing the convex hull of the feasible set for ML-decoding. Basically, he considers the parity check matrix$H$as a Tanner ... 0answers 40 views ### Reference request on dynamic flows combined with network coding I have read some papers about network coding and dynamic flows (flows over time). I think I have made comprehensive searches on google, google scholar and IEEE Xplore. IMHO, the reasons for the ... 1answer 113 views ### Can Quarter-Subset Membership be decided space-efficiently? Consider the following decision problem. Let$q = \sum_{i=0}^{n/4} \binom{n}{i}$and let$(C_0^n, C_1^n,\dots,C_{q-1}^n)$be a suitable enumeration of those subsets of$\{0,1,\dots,n-1\}$that have at ... 0answers 73 views ### Communication complexity of edit resilient synchronization Supposing we have two strings$A$and$B$that are both edit distance$\tau$from each other at two different sites is there a communication complexity model where synchronizing such strings have been ... 0answers 60 views ### Optimal distribution of integer edge weights I am not sure whether the following problem has been studied. Any help would be greatly appreciated. I have$L$sets,$S_1, S_2,...,S_L$, each of$n$elements, taken from a universe of$N$elements. ... 2answers 167 views ### Are there Similar Distance Binary Error Correcting Codes? I'm trying to find a low distortion embedding of the trivial metric space into hamming space. It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ... 0answers 48 views ### Reference for randomized GMD decoding The GMD decoder is an algorithm for decoding concatenated codes up to half their minimal distance. The standard presentation of this algorithm usually proceeds in two steps: First, one shows a ... 0answers 62 views ### The curve used in Parvaresh-Vardy decoding Consider the Parvaresh-Vardy list decoder. As I understand it, the idea is to decide on a curve over an extension field of the form$(f,f^h mod E, f^{h^2} mod E,\dots)$and then evaluate each of ... 0answers 44 views ### Number of different cycles in cyclic codes with length n I am studying Information theory, coding theory in particular at the moment, and I am having trouble determining how many different cycles are defined by a certain generator polinomial? Given a ... 2answers 2k views ### How many different Huffman encoding for a given number of symbols In Huffman coding, if we have two symbols to be encoded, we will get the result either 01 or 10. If we have three symbols, we ... 0answers 68 views ### What is the largest noise rate$\eta(n)$for which learning parities with noise is easy? Learning Parity with Noise (LPN) is usually stated with constant noise rate$\eta < 1/2$on the labels, and it is believed to be hard to learn because of the high statistical dimension of the ... 0answers 113 views ### Universal constant for bivariate testing In the seminal paper of Polishchuk and Spielman where they give a construction of nearly linear sized$PCP$for an$NP$problem, one of the key ingredients is a low-degree test for bivariate ... 0answers 124 views ### Applications of small Kakeya sets over finite fields It was proved by Dvir that a Kakeya set in$\mathbb{F}_q^n$has size at least$q^n/n!$, a bound which was later improved to$q^n/2^n$. For$n = 2$and$q$odd the exact bound is$q(q+1)/2 + (q-1)/2$... 1answer 65 views ### Complicated Huffman coding [closed] I am trying to figure out how to code these symbols. I am pretty sure I have it, but it gets a little tricky. Let A,B, and C have probabilities .71, .16, and .13 respectively. I am trying to code the ... 1answer 342 views ### Distance of arbitrary vectors to Hadamard code Let$n$be a positive integer and$N = 2^n$. The Hadamrd code of "block length"$N$can be generated using the inner product$f_u(x) = \langle u,x \rangle$mod$2$for all$u \in \{0,1\}^n$. It is ... 1answer 285 views ### Approximation algorithms for min vector subset-sum over GF(2) In this question vzn asked about the following problem, which I'll call Vector-Subset-Sum. Given a set of vectors$v_i$over GF(2) and a target vector$y$, is there a subset of the$v_i$summing to ... 1answer 105 views ### Reference request: Classical analog of quantum threshold theorem For quantum circuits, once the gate error is below a threshold, the error probability of an entire computation can be driven exponentially small with polylog costs in time and space: http://arxiv.org/... 1answer 268 views ### Question about “typical set” in Shannon's source coding theorem I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of$Ni.i.d$random ... 1answer 300 views ### Source Coding Theorem: what happen when we go below N*H(x) bits? I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on Shannon's source coding theorem (p81):$N$i.i.d. random variables each with ... 1answer 88 views ### Subspace-evasive set performance in the random case A subspace evasive set is defined as a large subset of a vector space which has small intersection with any$k$dimensional affine space. That is, it "evades" all affine subspaces of small enough ... 2answers 136 views ### Determining the distribution of results of a simple algorithm Setting Consider repeating the following process on the numbers$N=\{1, 2, 3, \ldots, n\}$: Pick an integer$k \in N$, uniformly at random. Pick a subset of$k$elements from$N$, uniformly at ... 0answers 40 views ### Decoding of Gabidulin codes Consider the space of matrices in$\mathbb{F}_q^{n \times m}$where$\mathbb{F}_q$is the finite field with$q$elements. We can define a metric on this space, given by$d(A,B) := rank(A-B)$, called ... 1answer 106 views ### Are there good locally decodable _erasure_ codes Are there known locally decodable erasure codes with linear codeword length and$\:n^{o(1)}\:$query complexity? According to pages 1 and 4 of this link (which annoying does not give its own ... 0answers 79 views ### Complexity of counting codeword length distribution Suppose I have a code$C$over$GF(2)$. I would like to count exactly the number of codewords of$C$of weight$k$. Here$k$should be thought of as small compared to the dimensions of the code. ... 4answers 1k views ### Research in Coding Theory I have just started learning about coding theory. Hence, I would like to ask for your suggestions and guidance for a very beginner like me. Which books are good for beginning coding theory? (I start ... 1answer 194 views ### Coding theory and complete problems Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete. My questions are the following:$(1)...
Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that: $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$. $A_{n}$ is in $\#P-Complete$, ...