Questions in Information Theory
1
vote
0answers
38 views
Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?
I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation ...
0
votes
0answers
108 views
Specific probability bound on minimal Kolmogorov sufficient statistic?
Using the notation from this question and defining the additional notation:
$K^*(B) = \ell(P^*_B)$
is there some universal Turing machine such that $\forall c \exists n,k\Pr\{K^*(B) \geq c+n\} \geq ...
-1
votes
1answer
66 views
Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph
I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{...
6
votes
1answer
222 views
Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic
Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$.
A bitstring $B$ is generated by drawing 0s and 1s ...
-1
votes
1answer
37 views
Relationship between worst case length of transcript and entropy of transcript
Consider the two party model of communication complexity where Alice and Bob are given inputs $X$ and $Y$ sampled from some distribution $\mu$, and their goal is to solve some problem $P$ (the details ...
4
votes
1answer
2k views
Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?
While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission.
Popular Bloom filter instead of marking just 1 hash ...
12
votes
1answer
998 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, ...
0
votes
0answers
63 views
Using idea of entropy (maybe Shannon entropy or other continuous entropy) to the topic of functional analysis
I am an electrical engineer without a detailed background in theoretical computer science. I am posting here since I hypothesize that the concept of entropy or other branches of information theory (as ...
4
votes
1answer
59 views
Can entropicly secure encryption algorithms be used on low-entropy messages by adding noise
There exist information-theoretic notions of security like Shannon's "perfect security" that one-time pads exhibit. All methods which achieve perfect security will require long keys, however. If we ...
4
votes
1answer
208 views
The Maxwell's Demon and Computer Science
What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I ...
0
votes
1answer
78 views
Error correction that adapts to different error rates
Say we have $N$ bits that we'd like to store in an $M$-bit error correcting code, where $M > N$. Given $\epsilon > 0$, as long as $N > N_0(\epsilon)$ we can recover the original bits as long ...
4
votes
1answer
357 views
Autoencoders and information compression
Disclaimer: I know very (very) little about deep nets, besides what an introductory course on machine learning would teach on neural networks, and skimming some paper abstracts and introductions.
If ...
1
vote
0answers
28 views
Problem dependent lower bound for stochastic bandits with full information
Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
1
vote
0answers
46 views
Parametrically-relaxed Kolmogorov complexity
Consider the following problem:
Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation.
Output: The encoding of some kind of automaton (say, a Turing machine) which ...
4
votes
1answer
181 views
Relation between variance and mutual information
Given two discrete random variables $X,Y$ such that $X,Y \in \mathbb{R}$ and $0 \leq X,Y \leq 1$, is it true that $$|\text{Cov}[X,Y] \leq \sqrt{\frac{1}{2} \text{I}[X,Y]}|. $$
This bound may be ...
1
vote
0answers
101 views
Connection between diamond norm and output purity norm
Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register ...
-1
votes
1answer
96 views
Does a code need at least two symbols to be defined as a code? [closed]
I am wondering whether you could still call a code something that, if transmitting, only transmits one symbol. Or does the formal definition of code require 2 or more symbols? (and would the answer ...
2
votes
1answer
223 views
Entropy of a byte in a compression algorithm?
I have a (fixed, long) string of bytes that I want to compress, $C$. I use a typical (good) lossless compression algorithm on it, to generate a compressed string of bytes, $C^*$. Then I define a ...
1
vote
0answers
106 views
Information theoretic lower-bound on object graph serialization
This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding ...
1
vote
1answer
51 views
Families of LDPC codes with constant error fraction corrected
I am looking for families of error-correcting LDPC codes with a constant error fraction corrected by a decoding algorithm.
For example, I know that Sipser and Spielman proved that there is an ...
4
votes
1answer
197 views
Word length using entropy : Maximum entropy criteria
The question is based on research paper titled, Markovian language model of the DNA and its information content
In the supplementary document, the Authors show how they determine the word length of ...
0
votes
0answers
178 views
Submodularity of KL divergence
Entropy on a set of random variables is known to be submodular. Now given a set of random variables $P_1, P_2, P_3, \dots, P_N$ and $Q_1, Q_2, Q_3, \dots, Q_N$, where every $P_i$ is a true ...
6
votes
1answer
648 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 ...
-2
votes
1answer
85 views
Lower bound on the number of objects in the universe [closed]
From Cover & Thomas' Elements of Information Theory:
Player A chooses some object in the universe,
and player B attempts to identify the object with a series of yes–no
questions. Suppose ...
3
votes
1answer
148 views
The average number of compressible strings in a random set of random strings
In the book Elements of Information Theory (p.446), it is stated:
...although there are some simple sequences, most sequences do not have simple descriptions. Similarly, most integers are not simple. ...
4
votes
0answers
94 views
Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?
Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi.
In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
-2
votes
1answer
165 views
Why don't we transmit at rates higher than the Shannon capacity if we are going to get a nonzero probability of error anyways ?
Shannon capacity $C$ is the upper limit on a rate $R$ defined as the number of information symbols $k$ divided by the number of transmitted symbols $n$, that can be transmitted over a channel such ...
4
votes
2answers
445 views
Relation between group theory and information theory
Motivation: I am interested about the application of group theory to information theory. To be precise, I am interested in data compression (source coding theory).
Question:
Is there any paper/survey ...
4
votes
0answers
60 views
What is the shortest description of a universal computational structure that includes a meta-circular evaluator?
I am wondering whether there is a minimal (or the shortest known) way of specifying a universal computational structure that includes a specification of a meta-circular evaluator within that structure....
6
votes
1answer
155 views
Lower bound on prefix code lengths
For a prefix code $C:\{0,1\}^*\to\{0,1\}^*$, define $f(n)$ as the length of the longest encoding of a number with up to $n$ bits:
$$
f(n)=\max_{|k|\le n}\left|C(k)\right|.
$$
(Note that by taking ...
8
votes
3answers
217 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 ...
1
vote
1answer
223 views
Does Huffman coding always produce shorter codes than the Shannon code?
Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$.
Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and
let $L(C)$ be the expected length of the code.
The ...
2
votes
2answers
281 views
What is empirical mutual information?
The topic says it all - I've been seeing this referenced a few times in information theory literature (Feedback in the non-asymptotic regime, Y. Polyanskiy et. al. among others), oftentimes making ...
1
vote
0answers
85 views
Maximal correlation vs correlation coefficient when one RV is Gaussian
Last week I asked a question on MOF (see here), but I got no reply. So I am asking my question here.
Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have ...
3
votes
0answers
61 views
Estimate smooth vector, from dot-product queries
I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$. I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$. I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^...
5
votes
1answer
279 views
Turbo codes and message passing
I'm self-studying turbo codes for a graduate course in coding theory. I understood how turbo codes works by directly reading Berrou' paper and some of the following works on this topic. Given that, ...
0
votes
1answer
97 views
Kraft Macmillan inequality explanation [closed]
I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me.
We would like to encode a sequence of ...
3
votes
0answers
110 views
What is the problem of finding a largest subset of smallest Kolmogorov complexity?
What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting ...
1
vote
2answers
192 views
Information-theoretic Diffie-Hellman
The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand.
In Diffie-Hellman Alice and Bob ...
3
votes
1answer
176 views
Is joint Kolmogorov Complexity order invariant?
Due to the symmetry of information, it follows up to an additive constant that
K(X,Y) = K(Y,X)
Does this hold for more than two data objects as well?
0
votes
0answers
110 views
“Elements of Information Theory”: Some (basic) help needed here
I was following the textbook by Cover & Thomas (2006): Elements of Information Theory. (hyperlink is not owned by me)
I have one question that has been irking for me some time. It is regarding ...
1
vote
0answers
110 views
Initialization of errata evaluator polynomial for simultaneous computation in Berlekamp-Massey for Reed-Solomon
This is a continuation of this post on SO.
I am trying to implement an errata (errors-and-erasures) decoder for Reed-Solomon. My current approach is to use Berlekamp-Massey (because it's the most ...
8
votes
1answer
456 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 ...
14
votes
5answers
784 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 ...
15
votes
1answer
368 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 ...
3
votes
0answers
352 views
An upper bound for chi-square divergence in terms of KL divergence for general alphabets
In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
4
votes
1answer
308 views
Introductions to steganography from an information-theoretic standpoint
Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
3
votes
0answers
73 views
One kind of dependence relation between a pair of random variables
I have been working on privacy and come across a neat problem.
Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution $P_{...
3
votes
1answer
1k 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 ...
4
votes
2answers
157 views
Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?
Suppose that $X$ and $Y$ are two random variables that are defined on the same support. Furthermore, suppose that $H(X | Y) = \log n$ for some $n$. I am now interested in how much the term $H(X | Y, X ...
