# Questions tagged [it.information-theory]

Questions in Information Theory

179 questions
Filter by
Sorted by
Tagged with
277 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 ...
541 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. ...
528 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 ...
2k 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 ...
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 ...
416 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)...
124 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 ...
140 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. ...
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 ...
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 ...
671 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 ...
237 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 ...
875 views

622 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 ...
603 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 ...
521 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 ...
681 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 ...
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 ...
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.
7k 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 ...
786 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 ...
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 ...
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 ...
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|$)...