1,234 problems

Let $X$ be uniformly distributed on the Boolean hypercube $\\{-1,1\\}^n$, and let $Y$ be obtained by transmitting $X$ through a memoryless binary symmetric channel with crossover p…

Let $f:\{-1,1\}^{n}\rightarrow\{-1,1\}$ be a Boolean function. Its Fourier entropy is the Shannon entropy of its power spectrum $\{\hat{f}(S)^2:S\subseteq\{1,\ldots,n\}\}$, and its…

Cuff's conjecture. With enough common randomness, the strong coordination region is the same as the empirical coordination region for any network setting.

Let $B_1,\ldots,B_n$ be independent Bernoulli random variables with parameters $p_i\in[0,1]$, let $\mathbf{p}=(p_1,\ldots,p_n)$, and let $H(\mathbf{p})$ denote the Shannon entropy…

Cover's conjecture. The feedback capacity is at most as large as the nonfeedback capacity under twice the power:

Let $M$ files be stored across $N$ servers, with each file stored independently using the same $(N,K)$-MDS code. A user wants to retrieve one file without revealing its index to an…

Let $\mathcal{K}(r,V)$ be the minimum of $\mathbb{E}[\Phi(\Pi)]$ over probability distributions $P_\Pi$ on $\mathbb{R}$ with mean $r$ and variance $V$, where $\Phi$ is the standard…

Let $X$ and $Y$ be independent identically distributed log-concave random variables in dimension $1$, and let $h$ denote differential entropy. Ball–Nayar–Tkocz conjecture. The map…

MMSE conjecture. If

Super-exponential codebook-size conjecture. The codebook size for any continuous-alphabet channel should be a super-exponential function of $n$, namely

No network-coding gain conjecture. Network coding has no rate benefit over routing in undirected unicast networks.

Let $X$ be uniformly distributed on $\{0,1\}^n$, let $Y$ be obtained from $X$ through a memoryless binary symmetric channel with crossover probability $0<p<\frac{1}{2}$, and let…

Let a 2-user multiple-input-single-output broadcast channel have finite-precision channel state information at the transmitter, meaning that the channel estimation error does not i…

Let an $[n,k]$ MDS storage code store a database accessed by a Symmetric Private Information Retrieval scheme, with $t$-colluding servers, $b$ Byzantine servers, and $r$ unresponsi…

Extension conjecture. The analytical results can be extended to the case of correlated channels.

Let $Q$ be a non-uniform distribution and $U$ the uniform distribution on a support of cardinality $2^n$. Let $T$ be the matrix with two rows, $Q$ and $U$, and $2^n$ columns. The q…

Steel's conjecture. In the Ising model, in the Kesten–Stigum regime, high-probability tree model estimation may be achieved with $k=O(\log n)$ samples.

Let a triply-noisy channel have substitution, insertion, and deletion parameters $\varsigma$, $\iota$, and $\delta$, respectively, and let $h_2$ denote the binary entropy function.…

Let $P_{\mathcal{M}}$ be a stationary distribution with entropy $H$, let $H_N$ denote the LAWS hit rate after $N$ total queries, and let $N_{\min}$ be the per-node visit threshold.…

Csiszár–Narayan conjecture. The mismatch capacity under the maximum-metric decoder for discrete-memoryless channels and product decoding metrics is given by the limiting multi-lett…

Tightness conjecture. The upper bound on the linearithmic capacity of deterministic identification over additive white Gaussian noise channels should be tight, and the use of typic…

Let $X^*$ be the unique capacity-achieving input distribution for the amplitude-constrained AWGN channel with peak-amplitude constraint $|X|\le A$. As $A$ increases, consider the s…

Information-theoretic impossibility conjecture. Recovery is information-theoretically impossible no matter the sample size in the sub-linear sparsification regime where $d=o(p)$.

Let $K\ge 3$ and let $B=K$, so that every user is connected to every relay. A rate tuple is written as $({R_X},{R_Y},{R_Z},{R_{Z_{\Sigma}}})$, with the components denoting the comm…

Let $\mathbf{X}\sim\operatorname{Unif}(\mathbb{H}^n)$ be uniformly distributed on the Boolean hypercube, and let $\mathbf{Y}$ be obtained by passing each bit of $\mathbf{X}$ throug…