# Tag Info

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 ...
Accepted

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 ...

### Lower bound on the number of objects in the universe

Because an optimal prefix free code, e.g. a Huffman code, can be shown to be within one bit of source entropy. This is certainly in Cover and Thomas, I am pretty sure.

### How does the Multiplicative Weights Update method maximize entropy?

The details are on page 3 of the paper Algorithms, games, and evolution by Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. They explain how the multiplicative weights update ...
Accepted

### Entropy-like quantity

It's the $\alpha^{\mathrm{th}}$ moment of the Tribus surprisal. This generalizes the statement that entropy = expected surprisal. Or in Ross's textbook, "expected surprise".
1 vote

### Information Bottleneck - Calculating the Mutual information between the Labels and the Features

This is only a partial answer. I might update it if I decide to look at the implementation. I understand this as being fixed network layers that don't get updated in training. Am I mistaken? Note ...
1 vote

### Does this notion of entropy have a name?

This is called "output entropy". Suppose you have a communications channel that takes a string and then outputs a random string within a relative $\delta$ radius of it. If you use the input ...
1 vote

### Entropy-like quantity

So we ended up calling this quantity the $\alpha$th moment of information and proving some inequalities about it: https://arxiv.org/abs/2004.12680 (paper to appear in the NIPS 2021 conference).
1 vote

### Volume of elements mapped to the same codeword is $2^{H(X|\hat{X})}$

If I understand right what "average volume" means here, I don't think this is correct. For example, let's say you map $n$-bit strings (under uniform distribution) to $n$-bit strings as follows: Given ...
1 vote
Accepted

### An equation relating Time complexity, Space complexity, and entropy of output

(Too long for a comment.) There are two aspects to your question. There is the idea of a time-"space" tradeoff, and the idea of entropy as a measure or bound for how hard this tradeoff must be for a ...
1 vote

### Is uniform convergence faster for low-entropy distributions?

We have largely resolved the question for product measures. I'm going to change the notation from the OP to be in line with our paper, https://arxiv.org/abs/2209.04054 I'll be writing $\mu$ rather ...
1 vote

### Word length using entropy : Maximum entropy criteria

Disclaimer: This is based on generic information theory knowledge only. Too long for a comment. Summary: The pointwise product of your two plots should go to some limit, as the relevant blocklengths ...

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