19
votes
Accepted
Entropy and computational complexity
Yes, but most of the work so far (except very recently, see below) has focused on turning irreversible computations into reversible ones, thereby hoping to avoid any entropy generation. (Note: there ...
- 36.9k
14
votes
Accepted
What are some standard books/papers on Information Theory?
This is a list of recommended books, videos and web sites copied from the Further Readings section of my book on information theory (given at the end of this post).
Applebaum D (2008). Probability ...
- 156
7
votes
Accepted
Does Huffman coding always produce shorter codes than the Shannon code?
This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample.
And if you want a really nice ...
- 24.3k
7
votes
Accepted
Why don't we transmit at rates higher than the Shannon capacity if we are going to get a nonzero probability of error anyways ?
Look at the strong converse to Shannon's theorem:
for rates above the channel capacity, if $n$ bits are to be transmitted, the probability of error is exponentially close to 1, so $1-e^{c n}$ for ...
- 24.3k
7
votes
Accepted
Relation between group theory and information theory
Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't ...
- 186
7
votes
Accepted
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key."
1.44 bits per ...
- 11.2k
7
votes
Is algorithmic information theory still evolving?
A modern tweak on algorithmic information theory is algorithmic randomness which was developed intensively in the 2000s (2009-2009) and is still quite active.
The most notorious open problem there ...
- 4,475
7
votes
Accepted
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
Chaitin in his 1976 paper
Chaitin, Gregory J., Information-theoretic characterizations of recursive infinite strings, Theor. Comput. Sci. 2, 45-48 (1976). ZBL0328.02029.
studied sets such that ...
- 4,475
6
votes
Accepted
Showing that interval-sum queries on a binary array can not be done using linear space and constant time
I believe that what you are looking for is a compact data structure supporting the rank operation. See...
https://en.m.wikipedia.org/wiki/Succinct_data_structure
Specifically, you can modify Emils (...
6
votes
Showing that interval-sum queries on a binary array can not be done using linear space and constant time
I wouldn’t be so sure such an algorithm doesn’t exist; there are certainly algorithms that get very close. Below, $\log n$ is $\log_2n$, $\log^{(k)}n$ is $\mathop{\underbrace{\log\dots\log}_{k\text{ ...
- 16.9k
6
votes
What is empirical mutual information?
I agree with @usul. I've also never seen the term empirical mutual information mentioned, but I've seen the term empirical entropy quite a lot, especially in the compression community. The definition ...
- 1,101
6
votes
Accepted
Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise
Here is the problem: if $M$ has low entropy (for example, if the attacker has side information that narrows $M$ down to just two possible messages), then conditioned on $M+K$, the key $K$ also has low ...
- 878
6
votes
Accepted
Converting a Bernoulli to a Gaussian
Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively.
Consider the ...
- 76
6
votes
Information and Coding Theory Texts
Maybe not so math oriented but with math rigor:
Elements of Information Theory by Thomas M. Cover, Joy A. Thomas
Essential Coding Theory by Venkatesan Guruswami, Atri Rudra and Madhu Sudan
- 181
5
votes
Accepted
Is joint Kolmogorov Complexity order invariant?
You don't need symmetry of information. The invariance theorem does the trick. Let $p$ the smallest program such that $U(p) = \langle x, y\rangle$. One way of producing $(y, x)$ is to take make a ...
- 459
5
votes
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
Your definition of $\chi^2$ divergence is missing a term; namely,
$$
\chi^2(P\|Q) = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ} - 1\right)^2
= \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1
$$
(...
- 4,451
5
votes
Kolmogorov Complexity of a Decidable Language
Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^* KCDL(L_x)$, where $L_x$ is the language which consists only of the string $x$, and $=^*$ means equals up to an additive ...
- 36.9k
5
votes
Generating $k$ random bits from a pdf with entropy $H(p) = k$
The relevance of Shannon entropy is to repeated sampling: Given $n$ independent samples from a source with binary Shannon Entropy $k$, you can extract $nk(1+o(1)$ i.i.d. uniform bits as $n$ tends to ...
- 441
5
votes
Accepted
Maximal uniquely decodable codes
Maximal implies sharp, even for uniquely decodable codes.
Proof: If there is some sequence of letters which will never appear in the middle of a concatenation of codewords, then we can add this ...
- 24.3k
4
votes
A Question on Convex Conjugate Duality for KL Divergence
An alternative proof:
Given that $\psi(p)=D_{KL}\left(p\,||q\,\right)$ is closed and convex we know that $\psi^{**}(p)=\psi(p)$.
One proposes $\psi^{*}(\lambda)=\log\left(\sum_{x}q(x)e^{\lambda_{x}}...
- 41
4
votes
Difference between self-information and entropy
Self-information applies to an individual outcome, $x$. It measures how surprising that specific outcome is.
The entropy of process $X$ is the average amount of Shannon self-information something ...
- 141
4
votes
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
@odea, one can see that $\chi^2(P||Q) \leq c D(P||Q)$ cannot hold in general by taking a two point space with $P = \{ 1 , 0\}$ and $Q = \{ q, 1-q \}$. Then $\chi^2(P ; Q) = \frac 1 q -1$ while $D(P||Q)...
4
votes
Is there any connection between the diamond norm and the distance of the associated states?
Following up on the line of thinking presented by Alex Monras, there is actually a quite generic argument for this kind of bound that goes beyond diamond norm and applies to many other channel ...
- 141
4
votes
Relation between group theory and information theory
Reference Goppa's information theory work.
http://iopscience.iop.org/article/10.1070/RM1984v039n01ABEH003062/meta;jsessionid=2978C0F66C0E4C77833FEDFE7B511F98.c1.iopscience.cld.iop.org
[CITATION] ...
- 12.8k
4
votes
Accepted
The Maxwell's Demon and Computer Science
A good place to start looking at these ideas is this paper, though it talks about the (related) idea of information and thermodynamics. It relates fundamental computational tasks (eg. editing a bit) ...
- 148
4
votes
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times ...
- 11.2k
4
votes
Accepted
Uniqueness of the distribution maximizing the channel capacity
This conjecture is false. Here is a counterexample.
Suppose we have a binary symmetric channel:
$x_1 \rightarrow y_1$ with probability $1-\epsilon$ and $y_2$ with probability $\epsilon$,
$x_2 \...
- 24.3k
4
votes
Accepted
Expected vs worst-case communication complexity
The reason is that a lower bound on the worst-case complexity automatically implies a lower bound on the expected complexity, so there is no reason to prove the latter.
To see the implication, ...
- 5,350
4
votes
Accepted
Is subtractive dithering the optimal algorithm for sending a real number using one bit?
Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$.
We can at least prove that if $x$ is ...
- 376
4
votes
Information and Coding Theory Texts
Both texts in the other answer are great texts, and the Guruswami, Rudra, Sudan book is more based in the TCS approach to coding theory, which may be relevant to the potential reader. The books below ...
- 2,070
Only top scored, non community-wiki answers of a minimum length are eligible