14 problems

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…

Asymptotic-capacity undecidability conjecture. The following problem is undecidable: given a partially fixed-size network $(V,E,\{A_v\},\{B_v\},s_M,s_E)$, decide whether its asympt…

A partially fixed-size network has vertex set $V$, edge set $E$, source-message sets $\\{A_v\\}$, demanded-message sets $\\{B_v\\}$, and size specifications $s_M$ and $s_E$. The sp…

Let $p_{k,n,\delta}(\Gamma_m)$ denote the forwarding probability for a grid network of size $m$, and let $Y$ be a binomial random variable with parameters $n$ and $(\theta^+(p))^2$…

Let a $k$-pair network have sources $s_1,\dots,s_k$ and sinks $t_1,\dots,t_k$, and suppose it is strongly reachable, meaning that for every sink $t_j$ there are edge-disjoint direc…

Let $\boldsymbol A$ be an instance of the paper's network-coding problem with $r$ receivers, where each receiver wants $r$ data packets and every pair of receivers wants at most on…

Two-path conjecture. Node $k$ always has two disjoint shortest paths $p_{0}$ and $p_{1}$ satisfying one of the following alternatives: (1) $p_{0}$ runs from $X_{0}$ through the col…

Consider an additive white Gaussian noise multiway relay channel (AWGN MWRC) with relay power $P_0=LP$, where $L$ is the number of users and $P$ is the user power. Let…

Let $n,k,\alpha$ and $\gamma$ be integers with $k\leq n$ and $\gamma<\alpha$. Let $M$ be a $(\gamma,\alpha)$ regular or irregular symmetric or asymmetric banded random matrix of size…

Capacity trichotomy conjecture. The capacity of the sum-network is either $0$, $2/3$, or at least $1$.

Let $\rho=\lambda/\mu<1$ be the load factor in the three-receiver system, and consider the newly proposed coding module. Define decoding delay as the time from packet arrival at th…

Consider a $K\times N$ switch with traffic patterns consisting only of unicasts and broadcasts. The 1.25 speedup conjecture. The minimum speedup required to achieve $100\%$ through…

Consider a $2\times N$ switch with traffic consisting of unicasts and broadcasts, and let $G$ be its enhanced conflict graph. Let $QSTAB(G)$ denote the fractional stable set polyto…

Bounded-delay existence conjecture. There exists a finite value $I$, depending on the graph and in particular on $T(e)$, such that one can choose delays satisfying $i_e(p)<I$ for e…