7 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 ...
Chris Aldrich's user avatar
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-...
Peter Shor 's 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 ...
Joshua Grochow's 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\...
Noah Stephens-Davidowitz's user avatar
6 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
hddmss's user avatar
  • 181
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 ...
Mahdi Cheraghchi's 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 ...
Or Meir's user avatar
  • 5,350
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 ...
Peter Shor 's 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] ...
Turbo's user avatar
  • 12.8k
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 ...
zeb's user avatar
  • 376
4 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 ...
kodlu's user avatar
  • 2,070
3 votes
Accepted

Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?

Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well Asymptotic for ...
Pedro Juan Soto's user avatar
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 ...
Emil Jeřábek's user avatar
3 votes
Accepted

Theorem of Sudan, Trevisan and Vadhan about list-decoding

I don't think Step 4 works. The circuit $C_j^{\mathrm{Enc}(x)}$ takes $i \in [N]$ as input and outputs the $i$-th bit of $x$. For each $i \in [N]$, the circuit asks $\mathrm{poly}(\log N)$ queries ...
Shuichi's user avatar
  • 46
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 ...
WiFO215's 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 ...
Igor Shinkar's user avatar
  • 1,897
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

Minimum distance of a code

I hate to reopen an old topic but I just want to add for future searches that there is no way to do this in general unless you can logic-out the weight enumerators, but for a specific instance of a ...
esabo's user avatar
  • 21
2 votes

Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?

If you're not looking for asymptotic results, there are extensive tables that are maintained by researchers. You can find them at www.codetables.de. Go to that webpage, and click "linear codes". They ...
Peter Shor 's user avatar
2 votes
Accepted

Bounds for maximum number of code-words in a ternary error correcting code with length n and distance d?

The exact answer is unknown in general. One standard upper bound for $q-$ary codes is the Singleton bound, which gives $$|C|\leq q^{n-d+1},$$ and codes meeting this bound are called MDS. A lower ...
kodlu's user avatar
  • 2,070
2 votes
Accepted

Why are folded Reed Solomon Codes considered non linear?

Suppose we consider $s$-folded Reed-Solomon codes that are based on polynomials over a field $\mathbb{F} = \mathrm{GF}(p^t)$. Then the alphabet of those codes is of size $p^{t \cdot s}$. Hence, in ...
Or Meir's user avatar
  • 5,350
2 votes
Accepted

Families of LDPC codes with constant error fraction corrected

Here are a few examples: There are the expander codes of Spielman (not to be confused with Sipser-Spielman): http://www.cs.yale.edu/homes/spielman/Research/ITsuperc.pdf There are the linear-time ...
Or Meir's user avatar
  • 5,350
2 votes

What are the general direction and target question in the field of quantum error correction?

One big open question is the existence of "good" quantum LDPC codes. These are stabilizer quantum error correcting codes with constant check weight, constant rate and linear distance. Most ...
smapers's user avatar
  • 839
2 votes

Survey on Quantum error correction

Try these: Quantum Error Correction by Todd Brun Quantum Error Correction: An Introductory Guide by Joschka Roffe For surface codes, Dan Browne's lecture notes might help.
raycosine's user avatar
  • 203
2 votes
Accepted

The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

The probability that $x \in C + e$ is equal to $2^n \langle T_\rho 1_{0}, 1_{C+e} \rangle$, where $T_\rho$ is the noise operator and $\rho = 1-2\epsilon>0$. Now $$ 2^n \langle T_\rho 1_0, 1_{C+e} \...
Yuval Filmus's user avatar
  • 14.3k
2 votes

Are all linear-rate and -distance classical linear codes expanding?

Really cool question! This is a little bit on the handwavy side of things, but here is my take. The conclusion is that we can show the existence of an $\Omega(1)$-expander of size $\Theta(n)$, let me ...
loplo's user avatar
  • 41
1 vote

Reference request for linear algebra over GF(2)

As you mention, standard Linear Algebra books demonstrate the notions using infinite fields (usually the reals and the complex numbers). Pretty much, though, all the definitions are general enough to ...
Pavlos M.'s user avatar
1 vote
Accepted

Notation of sequences in rate distortion theory

In information theory notation, capital letters such as $X$ denote random variables, and lowercase letters such as $x$ mean their possible outcomes (i.e., fixed values). For example you can write the ...
Mahdi Cheraghchi's user avatar
1 vote
Accepted

weights in low density codes

Your question is somewhat ill-posed: given $n$ and $k$, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2. Instead, you can ask the question of what is the maximum ...
smapers's user avatar
  • 839
1 vote
Accepted

Explicit Bits-back Coding (a.k.a. Free Energy Coding) applied to Gaussian mixtures

Apparently, no. This is a generalization where the relationship between $k$ and $i$ is stochastic (i.e. defined by a distribution and not deterministic). To recover the original bits-back argument, we ...
Daniel Severo's user avatar

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