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.

127 questions
Filter by
Sorted by
Tagged with
3k 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 ...
536 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 ...
• 4,634
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 ...
• 24.8k
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 ...
5k 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 ...
• 171
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 ...
318 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 ...
• 779
476 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 ...
• 1,356
684 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 ...
• 131
264 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$, ...
446 views

• 32.1k
3k 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 ...
• 73
231 views

327 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: http://arxiv.org/...
• 3,263
7k 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 ...
219 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 ...
• 958
139 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 ...
144 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?
437 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 ...
• 1,318