256 problems

2403.10985 introduced the notion of reversible capacity of a graph and showed that it is at most the Shannon capacity. It is conjectured there that the two values are equal. At the…

Consider the real additive white Gaussian noise sequence channel … where the noise coordinates are independent $N(0,N_0/2)$. An $(E,M,\epsilon)$ code has $M$ equiprobable messages,…

For every integer $n\ge 1$, energy $E>0$, and noise standard deviation $\sigma>0$, let $x_0,\ldots,x_n\in\mathbb{R}^n$ satisfy $\lVert x_i\rVert^2=E$ for all $i$, and let the signa…

For an $n$-party monotone access structure $\Gamma\subseteq 2^{[n]}$, let $\ell_{\Gamma}$ be the minimum, over all linear secret-sharing schemes for one-bit secrets realizing…

Entropic Marton-type conjecture. There exists $c_2=\exp(O(1/c_1))$ such that, for every $m\in\mathbb{Z}_+$ and every such $X$, there is a subspace $G$ with

Completely monotone conjecture. The function $t\longmapsto I(X,t)$ is completely monotonous, that is

Let $(X,Y)$ be a doubly symmetric binary source ${\mathrm{DSBS}}(p)$ with $p\in(0,1/2)$. Let $R(D_{1},D_{2})$ denote its rate-distortion function under Hamming distortion, let $h$…

Let $G\in\mathbb{F}_q^{\ell\times\ell}$ be any kernel, and let $\mathbb{P}\{\mathsf{D}_1=1\}$ denote the probability that the first distance-process value equals $1$. Good $D$ impl…

The capacity-region claim. The capacity region of the $K$-user linear deterministic broadcast channel for this diamond message set is the set of non-negative rate tuples satisfying…

Let $\rho$) be the root of a tree, let $u$ denote the broadcast labeling on its vertices, and consider message-passing algorithms whose messages take values in an alphabet $\Sigma$…

Inner-loop error-bound conjecture.

Incorrect-path splitting conjecture. Under the Gaussian approximation, for any incorrect path that survives at some unfrozen bit $u_i$, it will split at some stage within…

Entropy-based measurement conjecture. For sufficiently large $n$, the linear program referred to as LP exactly recovers $x$ from $nH(k/n)/2$ measurements.

Let $M$ be a channel with second eigenvalue $\lambda_2(M)$, and let $T_b$ be the $b$-ary tree. The reconstruction problem is census-solvable when the root can be reconstructed from…

Consider a state-dependent channel $p(y|x,s)$ with independent and identically distributed state $S^n$, where the receiver obtains rate-limited state information through a separate…

Let $C_{PF}(\mathbf{N},P_T)$ denote the proportional fair capacity of a Gaussian broadcast channel with noise vector $\mathbf{N}$ and total power $P_T$. Let $\preceq$ denote the co…

Gaussian-case conjecture. In the Gaussian case, the surfaces of $\mathcal{R}_{in}$ and $\mathcal{R}_{out}$ are

Let $v$ be a string, let $L^m(v)$ denote the length of its shortest grammar, and let $\boldsymbol{\operatorname{MDL}}(v)$ denote the MDL code for $v$. Let $\gamma(n):=n f_1(n)$. Sy…

Let $h_n$ denote the normalized conditional entropy in the code ensemble, and let $\tau$ and $\rho$ be the degree sequences appearing in Theorem 1. For each admissible random varia…

Let $X$ and $X'$ be independent and identically distributed, discrete, real-valued random variables with finite entropy $H(X)<\infty$. Entropic Solymosi inequality. One has … where…

Let $p_1,p_2,\dots$ be a sequence of arbitrary discrete distributions presented adaptively over time. An online random sampling algorithm generates exact samples from these distrib…

Unconditional logarithmic rent conjecture. The bound continues to hold when (L2)--(L4) are dropped: when the excitation is endogenous to the designer's policy, agents learn from th…

Conditional $W$-way MPST conjecture. There is a unique inner- and outer-regular finite Borel measure $\widetilde\mu$ on $\widehat{\mathcal{A}}_{\mathrm{cond}}$ such that

Let $W$ be a positive integer and let $D$ be a symmetric, $W$-way DPI-additive divergence on bounded $W$-tuples of probability distributions. Write … and let $\mathsf{C}_{\alpha}$…

Let $Y$ be the output of the binary hypercube Gaussian-location channel, let $V$ denote its binary-hypercube input, and let $P_Y$ and $P_{V\mid Y}$ be the corresponding distributio…