Questions tagged [coding-theory]

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

Filter by
Sorted by
Tagged with
39
votes
13answers
2k 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 ...
11
votes
1answer
346 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 ...
2
votes
0answers
72 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$, ...
1
vote
1answer
129 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 ...
6
votes
4answers
493 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,...
5
votes
0answers
291 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\...
2
votes
1answer
106 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/...