As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [it.information-theory]

Questions in Information Theory

198 questions
Filter by
Sorted by
Tagged with
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 ...
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|$)...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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$...
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 ...
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 ...
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 ... 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)...
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 ...
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 ...
882 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ... 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...