# Tag Info

### The utility of Renyi entropies?

Renyi entropy is analogous, in some sense, to $\ell_p$-norms, so let's first recall why those norms are useful. Suppose we have a vector of numbers $a \in \mathbb{R}^n$. We want to have a single ...
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 ...
Accepted

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

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

### How can you prove that all halting probabilites are normal real numbers?

Marzio's comment gives a link to a formal proof that the Chaitin constant $\Omega$ is normal. Let me give some higher level intuition. $\Omega$ is definened to be an algorithmically random number, ...

### Information complexity of query algorithms?

Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science. Alexander Golynski gave a good example in his ground breaking paper titled "Cell ...
Accepted

### Lower bound proof for compressive sensing (Gel'fand widths)?

$m = \Omega(k \log(n/k))$ is a lower bound for any compressive sensing scheme, not just $\ell_1$-minimization using RIP guarantees on the measurement matrix. In fact, the recovery algorithm need not ...
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 ...

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