Processing math: 100%

Conjectures, Etc.

This page lists a few fun conjectures/problems and is updated from time to time. If you solve one, let me know!

Which Boolean Functions are Most Informative?

Conjecture: Let $X^n$ be i.i.d. Bernoulli(1/2), and let $Y^n$ be the result of passing $X^n$ through a memoryless binary symmetric channel with crossover probability $\alpha$ . For any Boolean function $b: \{0,1\}^n\rightarrow \{0,1\}$ , we have

$I(b(X^n);Y^n)\leq 1-H(\alpha).$

I am offering $100 for a correct proof of (or counterexample to) this conjecture. For more details on the conjecture itself, see the original paper with Gowtham R. Kumar.

Entropy Power Inequality for a Triple Sum?

For a random vector $X$ with density on $R^n$ , define its entropy power as

$N(X) = 2^{2 h(X)/n},$

where $h(X)$ is the differential entropy of $X$ .

If $X,Y,Z$ are independent random vectors, each having density on $R^n$ , is it true that

$N(X+Z) N(Y+Z) \geq N(X)N(Y) + N(Z)N(X+Y+Z) ?$

It turns out that this inequality is true if $Z$ is Gaussian, but the only proof I know of is via a more general result (see this paper). So, I would also be interested in a direct proof of the inequality in the special case where $Z$ is Gaussian.

The in-line helper

Let $m$ terminals be connected in a line, where terminal $i$ observes discrete memoryless source $X_i$ , and communicates to terminal $i+1$ at rate $R_i$ . The Slepian-Wolf theorem tells us that the constraints

$R_i \geq H(X_1, \dots, X_i |X_{i+1}, \dots, X_m), 1\leq i \leq m$

are both necessary and sufficient for terminal $m$ to recover $X_1, \dots, X_m$ near-losslessly.

Suppose we only demand that terminal $m$ recovers $X_1, \dots X_{j-1}, X_{j+1}, \dots X_m$ near-losslessly. What conditions on rates are necessary and sufficient to do so?