Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [coding-theory]

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

50 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
0 answers
371 views

Looking for an operator on polynomials

I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc). I wonder ...
Dana Moshkovitz's user avatar
13 votes
0 answers
192 views

Name and references for balanced variant of the long code?

The long code (arising in PCP theory etc) is an encoding of a set of $k$ values, using binary strings of length $2^k$ (double exponential in the number of bits needed to specify a value), with one ...
David Eppstein's user avatar
7 votes
0 answers
199 views

Geometric Intuition behind Locally testable codes

Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code ...
Turbo's user avatar
  • 12.9k
6 votes
0 answers
114 views

Codes that are both locally testable and locally decodable

Are there any known constructions of binary locally testable codes with very low (e.g., independent of the length of the codeword) query complexity and "good" rate (e.g., mapping strings of length $k$ ...
user avatar
6 votes
0 answers
281 views

Tree rotation, a problem similar to Huffman coding

I am not sure whether the following problem has been studied. We have a undirected tree $T$. We would like to construct another tree $T'$. $T'$ is a binary tree. Each inner nodes of $T'$ ...
jian's user avatar
  • 769
6 votes
0 answers
279 views

Huffman "terminator" bitstring

Motivation Imagine a huffman compressed file that gets downloaded partially, like in P2P software, so we allocate disk space for the whole file first and then start downloading random file chunks. ...
schnaader's user avatar
  • 161
5 votes
0 answers
121 views

Quantum security of cryptosystems: Are any non-Goppa code-based systems resistant to hidden subgroup attacks?

One of the main candidates for post-quantum cryptography is code-based cryptography (as opposed to lattice-based). The Niederreiter cryptosystem based on Goppa codes is shown to be resistant to hidden ...
Root's user avatar
  • 387
5 votes
0 answers
78 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 ...
Antimony's user avatar
  • 917
5 votes
0 answers
157 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$ ...
Anurag's user avatar
  • 190
5 votes
0 answers
330 views

Weight enumerator of a binary linear code

The weight enumerator polynomial of a $(n,k)$ binary linear code $\mathcal{C}$ is defined as $$WE(\mathcal{C}) = \sum_{i=0}^{n}WE_{i}(\mathcal{C}) x^{i}$$ where $$WE_{i}(\mathcal{C}) = \#\{c\in\...
Pavithran Iyer's user avatar
4 votes
0 answers
84 views

Is there a standard interpretation of this quantity?

Define an encoding scheme by a pair of functions: $$\mathsf{encode} : \mathcal{M}\to\mathcal{X},\quad \mathsf{decode} : \mathcal{X}\to\mathcal{M}$$ Typical examples of encoding schemes are things like ...
Mark Schultz-Wu's user avatar
4 votes
0 answers
103 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 ...
Turbo's user avatar
  • 12.9k
4 votes
0 answers
114 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 ...
Jeremy Kun's user avatar
  • 1,318
3 votes
0 answers
155 views

Computational complexity of minimum distance of rate $\frac{1}{2}$ codes

We know from Berlekamp, McEliece and Van Tilborg [On the inherent intractability of certain coding problems, IEEE Trans. Information Theory, 24 (1978)] that computing minimum distance of a (binary) ...
Root's user avatar
  • 387
3 votes
0 answers
76 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 ...
user avatar
3 votes
0 answers
54 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 ...
Or Meir's user avatar
  • 5,615
2 votes
0 answers
98 views

The existence of (non-rectangular) two dimensional Gray code

A Gray code consists of $n$-bit distinct strings $s_1,s_2, \ldots,s_N$ such that each $s_i$ and $s_{i+1}$ differs by one bit. For example: $000, 001, 010, 011, 111, 110, 101, 100$. It is known that we ...
Kai-Yuan Lai 賴開元's user avatar
2 votes
0 answers
88 views

Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
user2316602's user avatar
2 votes
0 answers
199 views

Damerau–Levenshtein distance with transposition of non-adjacent characters?

Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
Ted's user avatar
  • 21
2 votes
0 answers
112 views

Relation between automorphism group of a linear code and its dual code

Are there any strong connections between automorphism groups of codes that are dual codes of each other? I am looking for statements like one charcterizes other or one gives bounds on other etc. In ...
Root's user avatar
  • 387
2 votes
0 answers
109 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 ...
Bartolinio's user avatar
2 votes
0 answers
122 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 ...
Max Hopkins's user avatar
2 votes
0 answers
159 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 ...
Chad Brewbaker's user avatar
2 votes
0 answers
126 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 ...
BharatRam's user avatar
  • 393
2 votes
0 answers
87 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. ...
David Harris's user avatar
  • 3,508
2 votes
0 answers
75 views

Weight enumerator and levels of polynomial hierarchy

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$, ...
Pavithran Iyer's user avatar
2 votes
0 answers
107 views

Bayesian compression

Suppose you have a sequence generated by an i.i.d. process (such as repeatedly rolling a die and recording the values in order) parameterized by some K-dimensional vector $\vec{\gamma}$ (the ...
user13501's user avatar
2 votes
0 answers
442 views

Lee metric, Gilbert-Varshamov and Hamming bounds for larger relative distance ranges

Gardy and Sole provide a Gilbert-Varshamov lower bound and a Hamming upper bound for the Lee metric when the distance between codewords is smaller than the length of the code (captured by $r = \delta ...
v s's user avatar
  • 2,208
1 vote
0 answers
20 views

Coloring the $k$-deletion graph “constructively”

For $n,k\ge 1$, we define the graph $D_{n,k}$ to have vertex set $\{0,1\}^n$, with distinct $x,y$ being adjacent if $LCS(x,y)\ge n-k$. My question is: fixing $k>1$, does there exist some $C=C_k$ ...
Zach Hunter's user avatar
1 vote
0 answers
77 views

BCH codes and polynomials with many values in a subfield

For points $P=\{x_1, \ldots, x_n\} \subset {\mathbb F}_{2^m}$ define $$\mathcal{C}(P, t) =\{(f(x_1), \ldots, f(x_n)) \mid \mbox{$f\in {\mathbb F}_{2^m}[X]$ has degree $t$}\}$$ and $\mathcal{C}'(P, t) =...
user6584's user avatar
  • 1,242
1 vote
0 answers
133 views

Quantum error correction and graph codes

I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
Root's user avatar
  • 387
1 vote
0 answers
86 views

Explicit binary codes with block length n, distance n / log n, rate 1 - o(1)?

What are the best (i.e., highest-rate) explicit binary codes with block length $n$ and minimum distance $d$, in the regime $d = n^{1 - o(1)}$? The "redundancy" of a code is the difference between the ...
William Hoza's user avatar
  • 1,743
1 vote
0 answers
54 views

Underlying codes in Niederreiter cryptosystems

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 ...
Root's user avatar
  • 387
1 vote
0 answers
185 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.
J.Doe's user avatar
  • 19
1 vote
0 answers
88 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 ...
luegofuego's user avatar
1 vote
0 answers
42 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 ...
robit's user avatar
  • 111
1 vote
0 answers
69 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. ...
MJK's user avatar
  • 315
1 vote
0 answers
68 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 ...
BharatRam's user avatar
  • 393
1 vote
0 answers
45 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 ...
BharatRam's user avatar
  • 393
1 vote
0 answers
20 views

can constant weight codes achieve channel capacity

Can a sequence of constant weight linear codes achieve channel capacity on Additive White Gaussian Noise channel? (by a sequence achieving capacity I mean a sequence of linear codes of increasing ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
61 views

Number of non-isomorphic codes

We have number of non-isomorphic graphs given in http://planetmath.org/enumeratinggraphs Over an alphabet $q$ how many non-isomorphic $[n,k,d]_q$ codes are possible particularly in the special case ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
114 views

On Labeling the cube

Regularly in a Hamming hypercube, the vertices are labelled so that edge difference equals path difference. That is greater the edge difference, greater the hamming distance of the labelled vertices ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
138 views

Information theory and Tsfasman-Manin's problem

Yuri Manin recently posted an interesting paper on computability of boundary regions of distance-rate trade-offs for error correction codes. http://arxiv.org/PS_cache/arxiv/pdf/1107/1107.4246v1.pdf I ...
v s's user avatar
  • 2,208
1 vote
0 answers
335 views

Soft decoding of linear block (20,10) codes - what methods are used ?

What algorithms are advised for soft-decoding of linear block codes (20,10) ? What are advised references ? Sincerely Yours Alex PS By soft-decoding - I mean that input - is set of 20 real ...
Alexander Chervov's user avatar
1 vote
1 answer
100 views

Code indistinguishability assumption for Code based cryptography (in special cases)

Cryptosystems that are based on error correcting codes are often based with hardness of the two problem. Computational syndrome decoding is hard Indistinguishability Assumption (IA): Distinguishing ...
Root's user avatar
  • 387
0 votes
0 answers
87 views

Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common

Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common. ...
C. Mürtz's user avatar
  • 101
0 votes
0 answers
60 views

Is there a name/terminology for binary codes with evenly spaced number of ones?

I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
randomprime's user avatar
0 votes
0 answers
160 views

Is the following graph an expander graph?

Let's say we have the following bipartite-graph, denoted $G=(L,R,E)$: It has the following adjacency matrix: I am having problems decoding a received word from what I was told is an expander code ...
Louie_the_unsolver's user avatar
0 votes
0 answers
54 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 ...
Mark's user avatar
  • 101
-1 votes
0 answers
16 views

Shannon's Code Ordering of Probabilities

The first step in the Shannon's Code is to order the probabilities in decreasing order. Why do we do this? Is it to make it prefix-free or assign most probable words with shorter codewords?
revision's user avatar