Questions tagged [coding-theory]
The mathematical theory of codes, as used in communication, data compression, and cryptography.
98
questions
39
votes
13answers
2k views
Using error-correcting codes in theory
What are applications of error-correcting codes in theory besides error correction itself? I am aware of three applications: Goldreich-Levin theorem about hard core bit, Trevisan's construction of ...
27
votes
1answer
517 views
Good codes decodable by linear-sized circuits?
I'm looking for error-correcting codes of the following type:
binary codes with constant rate,
decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of ...
21
votes
2answers
3k views
How good is the Huffman code when there are no large probability letters?
The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a ...
16
votes
0answers
361 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 ...
13
votes
5answers
4k views
Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?
The popular DEFLATE algorithm uses Huffman coding on top of Lempel-Ziv.
In general, if we have a random source of data (= 1 bit entropy/bit), no encoding, including Huffman, is likely to compress it ...
13
votes
0answers
190 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 ...
11
votes
2answers
290 views
Solvability of matrix filling
Matrix $A$ has dimension $n \times n(n-1)$. We want to fill $A$ using integers between $1$ and $n$, inclusive.
Requirements:
Each column of $A$ is a permutation of $1, \dots, n$.
Any submatrix ...
11
votes
1answer
355 views
Constructing vectors in general position
Let a real $k\times n$ ($k\le n$) matrix ${\bf A}$ with the property that any collection of $k$ columns is full rank.
Q: Is there an efficient way to deterministically find a vector ${\bf a}$ such ...
10
votes
4answers
644 views
Surveys on Network Coding
I want to start learning about Network Coding:
http://en.wikipedia.org/wiki/Network_coding
Do you know any good survey (e.g. from IEEE Surveys and Tutorials) on the above subjects. I found some ...
10
votes
1answer
233 views
Boolean error correcting code over $\mathbb{F}_q$
Is there any known construction of a linear error correcting code $\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^m$ (with reasonable parameters), such that when given a Boolean vector $v\in \{0,1\}^n$, ...
9
votes
2answers
486 views
Applications of Spectral Graph Theory in Information and Coding Theory
I wanted to find out what are some application of SGT in the area of information and coding theory and maybe communications. The most related that comes to mind is the work on Expander Codes
Michael ...
8
votes
2answers
350 views
Finding out a set by intersection comparison
The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related.
The general ...
8
votes
2answers
576 views
How do I construct an optimal affix code?
An affix code is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in ...
8
votes
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 ...
8
votes
2answers
286 views
Bivariate low-degree polynomial testing of Polishchuk-Spielman
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 ...
7
votes
3answers
2k views
Maximum subset of words with Hamming distance ≥ D
For all words of fixed length L over a given alphabet, I am interested in a practical algorithm that can give me a subset of maximal cardinality such that the Hamming distance between any two words in ...
7
votes
1answer
1k views
Dual BCH codes of design distance $d$
The SODA 2008 Ailon-Liberty paper on fast Johnson-Lindenstrauss transforms uses a "dual BCH code of design distance 5" as part of the construction. They cite the
MacWilliams-Sloane book on error-...
7
votes
1answer
195 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)...
7
votes
0answers
190 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 ...
6
votes
4answers
518 views
Optimal encoding of $k$-subsets of $n$
A colleague asks the following question:
Let $S_k$ denote the subsets of $n$ of size $k$. Is there an optimal
and efficient encoding of these subsets ? Namely, is there an function
$f$ from $[0,...
6
votes
1answer
212 views
Best upper bound on rate for q-ary codes
Among the many upper bounds for families of codes in $\mathbb F _2 ^n$, the best known bound is the one by McEliece, Rodemich, Rumsey and Welch (derived through a linear programming relaxation ...
6
votes
0answers
110 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$ ...
6
votes
0answers
225 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'$ ...
6
votes
0answers
266 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. ...
5
votes
1answer
117 views
Complexity of finding automorphism group of code
What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for ...
5
votes
2answers
122 views
Reference Request: Error correction code for a random projection
I'm interested in a variant of the Binary Channel, where the bits aren't flipped with some probability, but rather they are completely erased. Output words therefore vary in length.
I'm quite sure ...
5
votes
2answers
781 views
Explanation of polar decoding?
Polar decoding, according to Arikan's paper, can be decoded using a successive cancellation (SC) decoder, which is based on calculating the likelihood ratio, as seen in the image below.
How can I ...
5
votes
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 ...
5
votes
0answers
125 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$ ...
5
votes
0answers
293 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\...
5
votes
2answers
2k views
Transposition of any characters in Damerau–Levenshtein edit distance computation
Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters?
Maybe some ...
4
votes
2answers
646 views
“long code test” and “dictatorship test”
Why is "long code test" also called "dictatorship test"?
I got really confused when I read about it in Arora's survey.
4
votes
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 ...
4
votes
2answers
406 views
On the need for a self-correcting function in the PCP theorem
Original proof of the PCP theorem, uses self-correction property of linear functions.
Assume we have $f: \{0,1\}^n \rightarrow \{0,1\}$, a function or table of values,
that is $(1-\delta)$-close to ...
4
votes
2answers
661 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 ...
4
votes
2answers
125 views
Gift bits when encoding a sequence of messages, how is that?
Recently a friend of mine asked a question I couldn't give immediate answer to.
Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n * m $ bits....
4
votes
2answers
200 views
The length of non perfect binary 1 error correcting codes
I am interested in the best known number of code words in binary 1 error correcting codes of length $n$. I am aware of the Hamming code when $n=2^r-1$, but i would like to get lower bounds for other $...
4
votes
1answer
110 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 ...
4
votes
2answers
758 views
Asymptotically good codes
In short my question is what are all known explicit constructions of asymptotically good codes over finite alphabet?
In more details: A sequence of codes codes $C_i: F^{k_i}\rightarrow F^{n_i}$ with ...
4
votes
1answer
124 views
Lower bounds on 2-query locally decodable codes
Does any one knows if there is a non-quantum proof of the fact that non-linear 2-query LDC must have exponential size?
4
votes
1answer
290 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 ...
4
votes
0answers
91 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 ...
4
votes
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 ...
3
votes
2answers
5k views
Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy
Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense ...
3
votes
1answer
303 views
reduction of maximum independet set to minimum distance of code
Is there a reference for direct reduction of computing maximum independent set of a suitably constructed graph to computing minimum distance of a linear code when the code is specified by its parity ...
3
votes
1answer
364 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 ...
3
votes
2answers
171 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 ...
3
votes
1answer
165 views
Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$
I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$.
Given $p$, I am looking for a ...
3
votes
1answer
259 views
Surveys on Algorithmic Problems in Coding Theory
Coding Theory has many algorithmic problems that enriched theoretical computer science. I want to learn specifically the connection between coding theory and the hardness of computational problems. I'...
asked Feb 25 '13 at 13:37
Mohammad Al-Turkistany
19.6k4 gold badges51 silver badges134 bronze badges
3
votes
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 ...
