Questions tagged [it.information-theory]

Questions in Information Theory

Filter by
Sorted by
Tagged with
15
votes
0answers
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 ...
10
votes
1answer
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. ...
9
votes
1answer
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 ...
31
votes
5answers
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 ...
9
votes
2answers
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 ...
12
votes
2answers
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)...
1
vote
0answers
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 ...
5
votes
1answer
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. ...
1
vote
0answers
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 ...
13
votes
5answers
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 ...
10
votes
4answers
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 ...
4
votes
1answer
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 ...
11
votes
1answer
875 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 \...
14
votes
5answers
20k 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 ...
5
votes
1answer
254 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
0answers
341 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
4answers
444 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,\...
6
votes
1answer
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 ...
2
votes
3answers
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 ...
27
votes
1answer
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 ...
10
votes
1answer
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 ...
21
votes
2answers
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 ...
4
votes
2answers
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.
23
votes
5answers
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 ...
2
votes
1answer
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 ...
9
votes
6answers
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 ...
55
votes
13answers
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
3answers
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 ...
44
votes
10answers
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|$)...

1 2 3
4