8 votes

Research in Coding Theory

From a mathematical perspective: Try 1) Handbook of coding theory - Huffman and Pless 2) Fundamentals of Error-Correcting Codes - Huffman and Pless 3) Introduction to coding theory - Ron ...
user avatar
  • 12.5k
7 votes

Minimum distance of a code

The problem for an arbitrary binary code is NP-hard. Reference: Alexander Vardy, “The Intractability of Computing the Minimum Distance of a Code,” IEEE Trans. Inf. Thy., Vol. 43 pp. 1757-...
user avatar
7 votes
Accepted

Complexity of finding automorphism group of code

By taking direct sum of codes (given their two generator matrices $G_1, G_2$, consider the block matrix $G_1 \oplus G_2 = \begin{bmatrix} G_1 & 0 \\ 0 & G_2 \end{bmatrix}$), finding the ...
user avatar
6 votes
Accepted

How many different Huffman encoding for a given number of symbols

The answer is $C_{n-1} n!$ . That is, the $(n-1)$st Catalan number times $n$ factorial. There are $C_{n-1}$ ways of making a complete binary tree with $n$ leaves, and there are $n!$ ways of assigning ...
user avatar
6 votes
Accepted

Relation between group theory and information theory

Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't ...
user avatar
6 votes

Why can't codes be defined over infinite fields?

Sphere packings give a nice analogue of codes over $\mathbb{R}$. A sphere packing is a set $\mathcal{P} \subset \mathbb{R}^n$ such that $d_{\mathcal{P}} := \inf_{x,y \in \mathcal{P}, x \neq y} \|x - y\...
user avatar
5 votes

Why can't codes be defined over infinite fields?

It is possible to define codes over infinite fields, but it is usually not as useful as codes over finite fields. The original motivation for error-correcting codes comes from the needs to transmits ...
user avatar
  • 5,055
5 votes
Accepted

Reference request: Classical analog of quantum threshold theorem

The classical theory of fault tolerance was pioneered by John von Neumann. I think this is the original reference: von Neumann, J. (1956). "Probabilistic Logics and Synthesis of Reliable Organisms ...
user avatar
5 votes

Information and Coding Theory Texts

Maybe not so math oriented but with math rigor: Elements of Information Theory by Thomas M. Cover, Joy A. Thomas Essential Coding Theory by Venkatesan Guruswami, Atri Rudra and Madhu Sudan
user avatar
5 votes
Accepted

Reference request for linear algebra over GF(2)

Strangely, linear algebra specific to finite fields is best studied in textbooks on the theory of error-correcting codes (for example, MacWilliams and Sloane). Pretty much all familiar notions in ...
user avatar
5 votes
Accepted

Maximal uniquely decodable codes

Maximal implies sharp, even for uniquely decodable codes. Proof: If there is some sequence of letters which will never appear in the middle of a concatenation of codewords, then we can add this ...
user avatar
4 votes
Accepted

Are there good locally decodable _erasure_ codes

Locally decodable codes and locally decodable erasure codes are qualitatively equivalent. Both imply $\Omega(m)$ many disjoint $q$-tuples from which one can recover a given message coordinate, where $...
user avatar
  • 6,940
4 votes

Research in Coding Theory

Lecture notes of the course "An Algorithmic Introduction to Coding Theory," by Madhu Sudan. Publication Date: 2001. The first chapter offers useful comments regarding several textbooks on coding ...
user avatar
  • 182
4 votes
Accepted

Are there Similar Distance Binary Error Correcting Codes?

Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$. To see it, write the elements of the set as the rows of ...
user avatar
  • 5,055
4 votes
Accepted

Distance of arbitrary vectors to Hadamard code

What you are asking is the covering radius of the Hadamard code. I am not sure what the answer is but the covering radius of the punctured Hadamard code is at least $\frac{N}{2} - \frac{\sqrt{N}}{2}$, ...
user avatar
4 votes

Relation between group theory and information theory

Reference Goppa's information theory work. http://iopscience.iop.org/article/10.1070/RM1984v039n01ABEH003062/meta;jsessionid=2978C0F66C0E4C77833FEDFE7B511F98.c1.iopscience.cld.iop.org [CITATION] ...
user avatar
  • 12.5k
4 votes
Accepted

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$. We can at least prove that if $x$ is ...
user avatar
  • 366
3 votes
Accepted

Can Quarter-Subset Membership be decided space-efficiently?

I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be ...
user avatar
3 votes

Approximation algorithms for min vector subset-sum over GF(2)

Dumer, Miccancio and Sudan showed that the minimum distance of a linear code is not approximable to any constant factor in randomized polynomial time, unless $\mathsf{NP} = \mathsf{RP}$. The minimum ...
user avatar
  • 6,940
3 votes

Question about "typical set" in Shannon's source coding theorem

$S_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S_δ$ but it is not necessarily a member of the typical set. The only reason to use the typical ...
user avatar
  • 467
3 votes
Accepted

Source Coding Theorem: what happen when we go below N*H(x) bits?

It's not clear exactly what your question is. What the textbook is talking about is the strong converse to Shannon's source coding theorem, but rate distortion theory is another part of information ...
user avatar
3 votes
Accepted

Subspace-evasive set performance in the random case

Here's a quick calculation. For a fixed affine subspace $H$ of dimension $k$, the probability that a random point falls in $H$ is $1/q^{n-k}$. The probability that at least $c$ points in $S$ fall in ...
user avatar
  • 6,940
3 votes

Information and Coding Theory Texts

Both texts in the other answer are great texts, and the Guruswami, Rudra, Sudan book is more based in the TCS approach to coding theory, which may be relevant to the potential reader. The books below ...
user avatar
  • 1,966
2 votes

Research in Coding Theory

My favorites for the first part of your question: Neal Koblitz: "A Course in Number Theory and Cryptography" $\rightarrow$ Very good introduction for mathematical treatment Oded Goldreich: "The ...
user avatar
  • 490
2 votes

Explanation of polar decoding?

Shor is probably referring to this fantastic lecture by Emre Telatar that walks you through the steps in polar coding. Do watch it! In doing so, you shall see that the best mental model to have in ...
user avatar
  • 21
2 votes

Bivariate low-degree polynomial testing of Polishchuk-Spielman

If I understand it correctly, Gauss's lemma implies that that $P$ and $E$ have a non-trivial common factor over $\mathbb{F}[x,y]$. But in the beginning of the proof of Lemma 8 they assume without ...
user avatar
  • 1,877
2 votes

Research in Coding Theory

excellent 50p survey by leading expert/member Luca Trevisan from 2004 also tracking recent/latest research in the field Some Applications of Coding Theory in Computational Complexity sections: ...
user avatar
  • 10.8k
2 votes

Good codes decodable by linear-sized circuits?

You should look at Tornado codes {1}, which, for any $R$ and $\epsilon>0$ and large enough $n$ can be designed to recover (with high probability) from a loss of a $(1-R)(1-\epsilon)$ fraction of ...
user avatar
2 votes

Using error-correcting codes in theory

Error-correcting code have had applications in property testing: Functional property testing: Showing tolerant testing can be quite hard: Tolerant Versus Intolerant Testing for Boolean Properties, ...
2 votes

Determining the distribution of results of a simple algorithm

I suspect you won't get a closed form solution for the distribution you're looking for. Think of the seemingly easier problem where $k$ is always chosen to be exactly $2$, and where you get the set $\{...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible