Skip to main content

Questions tagged [it.information-theory]

Questions in Information Theory

Filter by
Sorted by
Tagged with
61 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 ...
47 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 ...
Lance Fortnow's user avatar
32 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 ...
Artem Kaznatcheev's user avatar
27 votes
5 answers
9k 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 ...
Joe Fitzsimons's user avatar
27 votes
1 answer
538 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 ...
Andy Drucker's user avatar
  • 4,644
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 ...
Peter Shor 's user avatar
17 votes
6 answers
24k 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 ...
Auron's user avatar
  • 273
16 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, ...
XL _At_Here_There's user avatar
16 votes
0 answers
371 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 ...
Dana Moshkovitz's user avatar
15 votes
5 answers
2k 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 ...
Henry Yuen's user avatar
  • 3,798
15 votes
1 answer
17k 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 ...
Anshuman Sabath's user avatar
15 votes
1 answer
654 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 ...
Jay Hacker's user avatar
15 votes
1 answer
496 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 ...
Henry Yuen's user avatar
  • 3,798
15 votes
0 answers
258 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 ...
Or Meir's user avatar
  • 5,615
15 votes
0 answers
286 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 ...
Or Meir's user avatar
  • 5,615
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 ...
SRobertJames's user avatar
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$...
robinson's user avatar
  • 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 ...
mac389's user avatar
  • 233
12 votes
1 answer
848 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 ...
user avatar
12 votes
2 answers
448 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)...
v s's user avatar
  • 2,208
11 votes
1 answer
527 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 ...
Joe Fitzsimons's user avatar
11 votes
1 answer
403 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 ...
Yovboy's user avatar
  • 111
11 votes
1 answer
899 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 \...
AntonioFa's user avatar
  • 445
10 votes
4 answers
685 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 ...
Vasilis's user avatar
  • 131
10 votes
2 answers
856 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 ...
Suresh Venkat's user avatar
10 votes
1 answer
724 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 ...
Turbo's user avatar
  • 13k
10 votes
3 answers
355 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 ...
Arthur B's user avatar
  • 429
10 votes
2 answers
378 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 ...
Alex Golovnev's user avatar
10 votes
1 answer
555 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. ...
Nicholas Mancuso's user avatar
10 votes
1 answer
447 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,...
R B's user avatar
  • 9,458
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 ...
Joe Fitzsimons's user avatar
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 ...
Phil's user avatar
  • 201
9 votes
2 answers
356 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 ...
Or Meir's user avatar
  • 5,615
9 votes
2 answers
641 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 ...
Or Meir's user avatar
  • 5,615
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 ...
user avatar
9 votes
1 answer
581 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 ...
Dimitris's user avatar
  • 1,356
9 votes
1 answer
755 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 ...
luegofuego's user avatar
9 votes
2 answers
8k 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 ...
Martin Leslie's user avatar
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 ...
Subhayan's user avatar
  • 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 ...
Nav89's user avatar
  • 209
8 votes
2 answers
5k 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 ...
SAmath's user avatar
  • 425
8 votes
3 answers
274 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 ...
R B's user avatar
  • 9,458
8 votes
4 answers
796 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\...
Danny's user avatar
  • 500
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 ...
Jason Smith's user avatar
8 votes
2 answers
167 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\}\...
Geoffrey Irving's user avatar
8 votes
0 answers
910 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 ...
v s's user avatar
  • 2,208
8 votes
0 answers
359 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, ...
Antonio Valerio Miceli-Barone's user avatar
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?
Mok-Kong Shen's user avatar
7 votes
4 answers
457 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,\...
kodlu's user avatar
  • 71

1
2 3 4 5