Questions tagged [it.information-theory]
Questions in Information Theory
198
questions
9
votes
2
answers
637
views
High probability events without low probability coordinates
Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small ...
- 5,290
4
votes
2
answers
134
views
Gift bits when encoding a sequence of messages, how is that?
Recently a friend of mine asked a question I couldn't give immediate answer to.
Say we have $ n $ messages of length $ m $ bits each. Now we can pack them in a single message of length $ n * m $ bits....
- 333
10
votes
0
answers
152
views
Threshold for non-zero quantum capacity of depolarizing channels
In "Quantum-channel capacity of very noisy channels", DiVincenzo, Shor and Smolin showed that it is possible to perform quantum communication over depolarizing channels provided that the fidelity was ...
- 13.5k
10
votes
2
answers
376
views
Subset Numbering
Fix $k\ge5$.
For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$.
We would like this labelling to satisfy the following ...
- 2,162
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
11
votes
1
answer
517
views
Distinguishing between $N$ quantum states
Given a quantum state $\rho_A$ chosen uniformly at random from a set of $N$ mixed states $\rho_1 ... \rho_N$, what is the maximum average probability of correctly identifying $A$?
This problem can be ...
- 13.5k
15
votes
1
answer
640
views
Bloom filter hashes: more or bigger?
In implementing a Bloom filter, the traditional approach calls for multiple independent hash functions. Kirsch and Mitzenmacher showed that you actually only need two, and can generate the rest as ...
- 303
8
votes
2
answers
3k
views
Efficient synchronization of two instances of an ordered list
What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move ...
- 181
6
votes
1
answer
153
views
Minimal bandwidth required to synchronize two sets of values
We consider two computers who possess two sets of fixed-size values (ie. $k$-bit numbers for some constant $k$), and we assume that the two sets have a large overlap (ie. a large proportion of the ...
- 8,234
8
votes
0
answers
893
views
Applications of Theoretical Computer Science in Information Theory
Inspired by this question:
Information Theory used to prove neat combinatorial statements?
Are there any nice applications of theoretical computer science in information theory (the other way has ...
- 2,208
0
votes
0
answers
431
views
norms of compressible and incompressible vector
Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$
I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case ...
- 1
16
votes
0
answers
370
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 ...
- 11k
1
vote
0
answers
610
views
Information channel with symmetric channel matrix
It took me a while to figure out that a "symmetric channel" does not mean a channel with a symmetric channel matrix. (Rather, "symmetric channel" means that the rows of the matrix are all permutations ...
- 111
1
vote
2
answers
813
views
Arithmetic coding, the termination symbol, and the empty string
Suppose the source alphabet is $a, b, c$ with $a$ as the termination symbol and so the unit interval is correspondingly divided as
$[0, P(a), P(a)+P(b), 1]$.
Strings consisting of a bunch of $b$'s ...
- 73
2
votes
1
answer
260
views
Landauer's principle internals - how it works
I attached a picture, where the energy dissipation (entropy increase) on information erasure is explained. Is the explanation correct?
"RESTORE TO ONE" - is it correct to identify the operation as "...
- 431
0
votes
0
answers
135
views
Tractability of mutual information-augmented ensemble classification algorithms
I am seeking to augment random forest classification using Shannon-Weaver mutual information as a metaheuristic to partition candidate datasets. Specifically, I am trying to determine if such an ...
- 163
4
votes
2
answers
430
views
Combinations with symbols
Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than ...
- 43
-4
votes
2
answers
468
views
Covering Codes with Game Theory Application
Here is a question I came up with and i have been pondering for a while. It relates to covering codes, a subset of coding theory. I could not come up with an adequate solution, so here I am, asking ...
- 13
13
votes
4
answers
2k
views
Relation between computational complexity and information
I work in a computational neuroscience lab that quantifies the mutual information between pairs or groups of neurons. Recently, the boss his shifted focus to measuring the "complexity of neural ...
- 233
15
votes
0
answers
284
views
Mutual information vs. Product sets
Suppose we have two dependent random variables $X$ and $Y$, each of which is uniform over $\{0,1\}^n$, such that their mutual information $I(X;Y)$ is small, say, at most $\sqrt{n}$. Does this imply ...
- 5,290
10
votes
1
answer
551
views
Determine the minimum number of coin-weighings
In the paper On two problems of information theory, Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.
...
- 746
9
votes
1
answer
559
views
Applications of Spectral Graph Theory in Information and Coding Theory
I wanted to find out what are some application of SGT in the area of information and coding theory and maybe communications. The most related that comes to mind is the work on Expander Codes
Michael ...
- 1,346
31
votes
5
answers
3k
views
Efficiently computable variants of Kolmogorov complexity
Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:
It corresponds to an intuition of giving strings with patters or ...
- 10.1k
9
votes
2
answers
7k
views
Comparing Shannon-Fano and Shannon coding
I am interested in a few algorithms for creating prefix codes:
Shannon coding: we take $l_i=\lceil -\log p_i\rceil$.
Shannon-Fano coding: list probabilities in decreasing order and then split them in ...
- 320
12
votes
2
answers
435
views
Channel coding results using Kolmogorov complexity
Usually Shannon entropy is used to prove channel coding results. Even for source-channel separation results shannon entropy is used. Given the equivalence between Shannon (global) vs Kolmogorov (local)...
- 2,208
1
vote
0
answers
128
views
High Dimensional Volume (HDV) estimator for Entropy estimation
I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data ...
- 11
5
votes
1
answer
143
views
Long-term data encoding, Phoenix Mars DVD
While browsing I've stumbled over the Phoenix Mars lander
http://en.wikipedia.org/wiki/Phoenix_(spacecraft)#Phoenix_DVD
and it says that the craft contains a DVD with all kinds of information on it.
...
- 151
1
vote
0
answers
135
views
Information theory and Tsfasman-Manin's problem
Yuri Manin recently posted an interesting paper on computability of boundary regions of distance-rate trade-offs for error correction codes.
http://arxiv.org/PS_cache/arxiv/pdf/1107/1107.4246v1.pdf
I ...
- 2,208
13
votes
5
answers
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
10
votes
4
answers
678
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
4
votes
1
answer
262
views
Relation between Code Length and Symbol Weight in a Huffman Code
I'm not sure if I should ask this here or over at StackOverflow (sorry if this is not the right place).
I'm constructing a Huffman code for a series of symbols with associated weights. I have a list ...
- 143
11
votes
1
answer
882
views
A simple(?) funny combinatorial problem!
Let we fix $0<E<1$ and an integer $t>0$.
for any $n$ and for any vector $\bar{c} \in [0,1]^n$ such that $\sum_{i\in [n]} c_i \geq E \times n$
$A_{\bar{c}} :=|\{ S \subseteq [n] : \sum_{i \...
- 445
17
votes
6
answers
22k
views
Which is the limit of lossless compression data? (if there exists such a limit)
Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression.
So far, the only source I ...
- 273
5
votes
1
answer
263
views
Quantum Channel Decoding
Let a quantum channel $\Phi(\cdot)$ between two Hilbert spaces $\mathcal{H}_{in}$ and $\mathcal{H}_{out}$.
What is the quantum channel $\Phi_{inv}(\cdot)$ that best reverses $\Phi(\cdot)$ ?
$\forall $...
8
votes
0
answers
352
views
Approximation of Quantum Channels
Background:
In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels:
A quantum channel is a linear, ...
7
votes
4
answers
449
views
Is there a standard definition of Quantum Randomness?
I hope this question is not too vague.
For classical bit generators there is the classical statistical definition which (informally) states that a source is ideally random if its output $X_1,X_2,\...
- 71
6
votes
1
answer
629
views
Existence of zero-knowledge proof for location
N items have been placed at specific points on a map. A prize is awarded to the first person who turns in a list with the location of all N items. The location of each item must fall with a distance ...
- 173
2
votes
3
answers
632
views
Is there a lower bound of number of redundant bits necessary to encode a word with certain Hamming distance?
Is there a lower bound (in coding theory or elsewhere) of number of redundant bits necessary to encode a word with certain Hamming distance?
There is some known data for parity checks, CRC, Hamming ...
- 123
27
votes
1
answer
530
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,614
10
votes
1
answer
703
views
Lovasz theta function and regular graphs (odd cycles in particular) - connections to spectral theory
The post is related to:
https://mathoverflow.net/questions/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles
How far away is the Lovasz bound from the zero-error ...
- 12.6k
21
votes
2
answers
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 ...
- 23.9k
4
votes
2
answers
3k
views
Why does the Fibonacci sequence produce a worst-case Huffman encoding?
I noticed this in my Algorithms class, but just now got around to asking.
- 51
24
votes
5
answers
8k
views
Is there any connection between the diamond norm and the distance of the associated states?
In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such ...
- 13.5k
2
votes
1
answer
925
views
Can the mutual information of a "cell" be negative?
Please forgive me if this is not the right Stack Exchange (I also posted it at Cross Validated). Please also forgive me for inventing terms.
For discrete random variables X and Y, the mutual ...
- 123
9
votes
6
answers
2k
views
Where does the information in a fractal come from?
When I view a fractal such as the Mandelbrot, my first thought is, where did this interesting picture come from. For a picture of this complexity, the information that generated this picture must be ...
- 201
60
votes
14
answers
4k
views
Information Theory used to prove neat combinatorial statements?
What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ?
Some examples I can think of are related to lower bounds for locally decodable ...
35
votes
3
answers
2k
views
What is the Volume of Information?
This question was asked to Jeannette Wing after her PCAST presentation on computer science.
“From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge ...
- 8,556
45
votes
10
answers
4k
views
Kolmogorov complexity applications in computational complexity
Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...