Questions tagged [coding-theory]
The mathematical theory of codes, as used in communication, data compression, and cryptography.
9
questions
39
votes
13
answers
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 ...
4
votes
1
answer
441
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,328
4
votes
1
answer
339
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
11
votes
1
answer
481
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
7
votes
4
answers
759
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,...
- 32.1k
5
votes
0
answers
332
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\...
- 323
5
votes
2
answers
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 ...
- 103
3
votes
2
answers
434
views
Minimum distance of a code
Is there a way to compute minimum distance of a code given a systematic parity check matrix? I know that min dist is smallest number $d$ such that there exists $d$ linearly dependant columns. I am ...
- 387
2
votes
0
answers
75
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$, ...
- 323