Skip to main content
Share Your Experience: Take the 2024 Developer Survey
21 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 ...
Joshua Grochow's user avatar
16 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 ...
James V Stone's user avatar
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 ...
Peter Shor 's user avatar
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 ...
Chris Aldrich's user avatar
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 ...
jbapple's user avatar
  • 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 ...
Bjørn Kjos-Hanssen's user avatar
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 ...
Bjørn Kjos-Hanssen's user avatar
7 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
hddmss's user avatar
  • 191
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 ...
Adam Smith's user avatar
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 ...
Kunal's user avatar
  • 76
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 ...
Peter's user avatar
  • 459
5 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)...
James Melbourne's user avatar
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 $$ (...
Clement C.'s user avatar
  • 4,471
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 ...
Joshua Grochow's user avatar
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 ...
Yuval Peres's user avatar
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 ...
Peter Shor 's user avatar
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}}...
nosferatttu's user avatar
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 ...
Post169's user avatar
  • 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] ...
Turbo's user avatar
  • 12.9k
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 ...
Mark M. Wilde's user avatar
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) ...
Abhishek Shetty's user avatar
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 ...
jbapple's user avatar
  • 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 \...
Peter Shor 's user avatar
4 votes
Accepted

Why not include private randomness in internal communication information definition?

I agree that the definition you suggest is more natural. However, this definition is equivalent to the definition without the private randomness, so I assume they omit the private randomness just to ...
Or Meir's user avatar
  • 5,615
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, ...
Or Meir's user avatar
  • 5,615
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 ...
zeb's user avatar
  • 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 ...
kodlu's user avatar
  • 2,070
4 votes

Can theoretical computer science be combined with mechanism and information design and applications in financial markets

This depends on whether the CS department you are studying at has somebody working in this field. Some of them (at least three of the top ten in the U.S.) do, and some of them don't, and some of them ...
Peter Shor 's user avatar
4 votes

How much information does it take to specify, not each member of a group, but any one member?

This answer continues Peter's. It assumes Peter's interpretation of the problem and verifies that with that interpretation the function $f(S)=\min S$ is optimal, as Peter suggested. Here's the ...
Neal Young's user avatar
  • 10.8k
3 votes
Accepted

Relation between variance and mutual information

I think you can show it as follows, and even get a better constant in the end. Forewarning, there's enough cleverness here that I'm kind of suspect that everything is right. But the basic idea is ...
Andrew Morgan's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible