286 problems

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…

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…

Let $B_1,\ldots,B_n$ be independent Bernoulli random variables with parameters $p_1,\ldots,p_n\in[0,1]$, let $S=\sum_{i=1}^n B_i$, and write $P_k(p)=\mathbb{P}_p(S=k)$. Determine t…

For every integer $n\ge 2$, let $X=(X_1,\ldots,X_n)$ be a centered Gaussian vector satisfying $\operatorname{Var}(X_i)=1$ for every $i$. Let $Z_1,\ldots,Z_n$ be independent standar…

For every integer $n\ge 1$, every Boolean function $f\colon\{-1,1\}^n\to\{-1,1\}$, and every noise parameter $\rho\in[0,1]$, let $X$ be uniformly distributed on $\{-1,1\}^n$, let…

Let $n\ge 2$ independent arms have distributions $X_i\sim\mathcal{N}(\mu_i,1)$, with $\mu_i\in[0,1]$ and a unique optimal arm $*$. Write $\Delta_i=\mu_*-\mu_i$ for $i\ne *$,…

Let $X$ and $Y$ be independent identically distributed real-valued random variables with a common log-concave density and finite differential entropy. Define $F:[0,1]\to\mathbb{R}$…

Let $\mathcal{W}_0$ be the class of admissible waveforms without a cyclic prefix, let $x_{\mathrm{OFDM}}\in\mathcal{W}_0$ denote conventional OFDM, and let…

Given arbitrary nonempty families of finite-dimensional quantum channels $\mathcal{N}_0$ and $\mathcal{N}_1$, characterize the optimal asymptotic Stein exponent for discriminating…

Let $(X,Y)$ be jointly Gaussian with $X,Y\sim\mathcal{N}(0,1)$ and correlation coefficient $\rho\in(0,1)$. The exact common information of $(X,Y)$ is conjectured to satisfy…

Let $Q_{XY}$ be a joint distribution on finite alphabets, and consider distributed hypothesis testing with null hypothesis $\mathcal{H}_0: P_{XY}=Q_XQ_Y$ and alternative hypothesis…

Let $X_1,\ldots,X_N$ be observations from a centered stationary Gaussian process with spectral density $f$ belonging to a Sobolev-type class $\mathcal F_s$, and let the observation…

Let $G_q$ be an alphabet of size $q\ge 2$, let $t\ge 1$ be fixed, and let $C\subseteq G_q^n$. For $X,Y\in G_q^{t\times n}$, define the column Hamming distance by…

Let $X^n=(X_1,5e5c,5e5c,X_n)$ have independent coordinates distributed as $\operatorname{Bernoulli}(p)$, with $0<p<\tfrac12$, and let distortion be normalized Hamming distortion. D…

For every pair of integers $n,k$ satisfying $3\leq k\leq n-1$, the optimal leading coefficient in the high-SNR maximum-likelihood error-probability expansion for SNR-dependent…

For every finite two-receiver discrete memoryless broadcast channel $p_{Y,Z\mid X}$, the capacity region equals the full Marton inner bound:…

Let $G$ be a finite simple undirected graph on $n$ vertices, and let $\mathcal{L}(G)$ denote the probability that the uniform sequential attachment process outputs a graph isomorph…

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

Let $X_1$ and $X_2$ be binary classical random variables with quantum side-information systems $B_1$ and $B_2$, respectively, and let $\rho^{X_1B_1}$ and $\rho^{X_2B_2}$ be classic…

Find a computable single-letter characterization of the capacity region for general 3-receiver discrete memoryless broadcast channels without degradedness assumptions. Source: A. E…

For every finite undirected edge-capacitated network and every finite collection of independent source-destination unicast sessions, prove or disprove that the zero-error network-c…

Determine whether an algorithm exists which, given the exact adjacency matrix of any nonempty finite simple graph G and an integer t=1, halts and returns a rational a with |a-Theta…

Decide whether average-case hardness of Learning Parity with Noise in the standard constant-noise regime can be established by a worst-case-to-average-case reduction from a worst-c…