Questions tagged [it.information-theory]
Questions in Information Theory
198
questions
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 ...
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|$)...
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
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
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
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
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
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
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
15
votes
5
answers
1k
views
The utility of Renyi entropies?
Most of us are familiar with — or at least have heard of — the Shannon entropy of a random variable, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$, and all the related information-theoretic ...
- 3,718
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
15
votes
1
answer
469
views
Information complexity of query algorithms?
Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems.
Is there an analogue of information ...
- 3,718
15
votes
0
answers
250
views
Fano's inequality in the high error regime
Fano's inequality says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More ...
- 5,290
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
14
votes
1
answer
2k
views
Entropy and computational complexity
There are researcher showing that erasing bit has to consume energy, now is there any research done on the average consumption of energy of algorithm with computational complexity $F(n)$? I guess, ...
- 1,050
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
13
votes
3
answers
3k
views
On the entropy of a sum
I am looking for a bound on the entropy $H(X+Y)$ of the sum of two independent discrete random variables $X$ and $Y$. Naturally, $$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$$ However, applied to the sum of $n$...
- 775
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
12
votes
1
answer
15k
views
What are some standard books/papers on Information Theory?
I have started Information Theory classes just recently and was wondering what would be a standard book to purchase. I know I can go for basic introductory books but I also like to purchase standard ...
- 141
12
votes
1
answer
813
views
The entropy of a convolution over the hypercube
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
user887
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
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
11
votes
1
answer
381
views
Is algorithmic information theory still evolving?
I am currently looking for a subject for a thesis and encountered the field of algorithmic information theory.
The field seems very interesting for me, but it seems everything is the field was done ...
- 111
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
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
10
votes
2
answers
812
views
A converse to Fano's inequality ?
Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev:
Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ is ...
- 31.9k
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
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
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
10
votes
1
answer
432
views
Is subtractive dithering the optimal algorithm for sending a real number using one bit?
Consider the problem of sending a real number $x\in[0,1]$ using a single bit $X\in\{0,1\}$ in an unbiased manner.
We assume that the sender and receiver have access to shared randomness $h\sim U[-1/2,...
- 9,408
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
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
9
votes
2
answers
341
views
Guessing a low entropy value in multiple attempts
Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice ...
- 5,290
9
votes
3
answers
337
views
Is there a generalization of information theory to polynomially knowable information?
I apologize, this is a bit of a "soft" question.
Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating ...
- 419
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
9
votes
1
answer
323
views
The entropy of a noisy distribution
Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$ such that
$$\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n} \right\},$$
and $f$ is a ...
user887
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
9
votes
1
answer
724
views
Information theory and convex optimization
I'm taking a graduate level course in information theory and I'm constantly struck by how much convex optimization there is in this subject. However, the proofs seem to shy away from using the full ...
- 263
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
9
votes
3
answers
1k
views
Kolmogorov Complexity applications in Number Theory
What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.)
One of ...
- 831
9
votes
0
answers
160
views
"Looking for help understanding a proof by Gossner (1998)."
Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
- 209
8
votes
2
answers
4k
views
A Question on Convex Conjugate Duality for KL Divergence
The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as
$$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the ...
- 425
8
votes
3
answers
272
views
Showing that interval-sum queries on a binary array can not be done using linear space and constant time
You are given a $n$-sized binary array.
I want to show that no algorithm can do the following (or to be surprised and find out that such algorithms exist after all):
1) Pre-process the input array ...
- 9,408
8
votes
4
answers
757
views
Expected empirical entropy
I'm thinking about some properties of the empirical entropy for binary strings of length $n$ when the following question crosses my way:
$\underbrace{\large\frac{1}{2^{n}}\normalsize\sum\limits_{w\in\...
- 490
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
8
votes
2
answers
163
views
Smoothly leaking information over time
Say I have a one bit random variable $X \in \{0,1\}$, and let $n$ be a natural number. I want a sequence of random variables $0 = X_0, X_1, \ldots, X_n = X$ s.t.
$$H\left(X~|~\{X_0,\ldots,X_k\}\...
- 3,243
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
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
3
answers
4k
views
Are Shannon entropy and Boltzmann entropy mutually convertible?
Are Shannon entropy and Boltzmann entropy mutually convertible, much like mass and energy according to Einstein's formula?
- 207
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