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

learn more… | top users | synonyms

1
vote
0answers
36 views

Information theoretic secret key agreement

Supposing Alice and Bob share correlation sequences in $\{0,1\}^n$ what coding theory based schemes are available to extract a common key for cases (I am not worried about secrecy). $(1)$ Alice and ...
0
votes
1answer
80 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 ...
3
votes
0answers
38 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 ...
2
votes
0answers
48 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 ...
5
votes
0answers
64 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$ ...
-3
votes
1answer
46 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 ...
2
votes
1answer
66 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
1answer
101 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 ...
0
votes
1answer
40 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: ...
1
vote
1answer
108 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 $N$ $i.i.d$ random ...
0
votes
1answer
106 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 ...
1
vote
1answer
54 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 ...
0
votes
2answers
129 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 ...
1
vote
0answers
27 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 ...
3
votes
1answer
51 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 ...
2
votes
0answers
44 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. ...
3
votes
4answers
364 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 ...
6
votes
1answer
155 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: ...
2
votes
0answers
58 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$, ...
3
votes
2answers
164 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 ...
1
vote
0answers
24 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 ...
13
votes
0answers
168 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 ...
6
votes
0answers
92 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$ ...
1
vote
0answers
90 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 ...
5
votes
0answers
221 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}) = ...
3
votes
4answers
221 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 ...
4
votes
2answers
97 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
0answers
274 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 ...
3
votes
0answers
84 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 ...
2
votes
0answers
79 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 ...
3
votes
2answers
1k 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
147 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
2answers
342 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 ...
3
votes
1answer
218 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. ...
2
votes
0answers
80 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 ...
2
votes
1answer
119 views

Ambivalent Coding

Consider the following situation, I want to send one of two bitstrings, A or B, to a receiver. Clearly, I can do this by sending the shortest, but is there a better way? It seems that the requirement ...
8
votes
2answers
220 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 ...
6
votes
1answer
159 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 ...
1
vote
1answer
150 views

fast range summable hash functions

I'm finding is there any range summable hash function. ADD: The hash function I refer to is the one that is typically used in tug-of-war sketch(AMS sketch). Please refer to The space complexity of ...
4
votes
2answers
116 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 $ ...
5
votes
2answers
960 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 ...
7
votes
3answers
1k 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 ...
10
votes
1answer
207 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$, ...
11
votes
1answer
289 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 ...
15
votes
0answers
322 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 ...
6
votes
0answers
201 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'$ ...
-4
votes
2answers
390 views

Covering Codes with Game Theory Application

Here is a question I came up with and i have been pondering for a while. It relates to covering codes, a subset of coding theory. I could not come up with an adequate solution, so here I am, asking ...
3
votes
1answer
254 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 ...
8
votes
2answers
307 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 ...
3
votes
2answers
375 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 ...