66 problems

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

An undirected unicast network consists of an undirected communication network with unicast demands between source–destination pairs. Its achievable rate is the common information r…

Let a $k$-pair network be a directed acyclic network with sources $S=\{s_1,\dots,s_k\}$ and sinks $T=\{t_1,\dots,t_k\}$. It is strongly reachable if, for every $j$, there are edge-…

Condensed derangement set throughput conjecture. Different condensed derangement sets achieve roughly the same average throughput for $N$ larger than $5$.

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

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…

Let $\sigma$ denote the total number of non-zero elements in the network's local coding matrix, and let $m$ be the matrix dimension. Define … where the limit is understood in the r…

Let $q$ be the cardinality of the finite field used for the random network code, and let $e$ be the total number of links in a large random network satisfying certain unspecified p…

Cost-function conjecture. The cost function for minimizing the number of packets involved in network coding is

A protograph-based batched network code (P-BNC) consists of a precode ${\cal{P}}$, sets ${\cal F}_{\rm outer}$ and ${\cal F}_{\rm inner}$ of outer- and inner-code encoding function…

Let $(V,E)$) be a network with Gaussian source signals, destination node $d$, and wiretapped edges $\tilde{E}subseteq E$. Define the secrecy closure of $\tilde{E}$ by … Here,…

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…

A network coding instance consists of a finite network with messages and edges whose alphabet sizes are allowed to vary with a common alphabet-size parameter. Undecidability conjec…

The bandwidth trade-off curve describes the achievable operating points for cooperative node repair in distributed storage systems with base stations and link constraints. Closed-f…

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 $\psi(n)$ denote the smallest prime power that is at least $n$. The upper bound for the gap of the minimal combination network $\mathcal{N}_{h,r,h}$ involves the quantity…

Let a multicast network have one source with $h$ messages and $N$ terminals, and let $q$ denote the field size of a linear solution. It is known that a field size $q\geqslant N$ su…

In an undirected communication network, consider transmitting multiple independent messages between specified source–sink pairs. Li and Li's conjecture. Network coding cannot achie…

Let $q$ be the field-size parameter and let $\ell$ be the number of shots. In the multishot setting, the construction uses $q>\ell$; for MDS codes, corresponding to $n^\prime=1$, t…

Let $\mathcal{N}$ be a multicast network, and let $GF(q)$ denote a finite field. The network is linearly solvable over $GF(q)$ if it admits a linear network code over that field. S…

Let $V=[6]$ and let $r_{\operatorname{K}}$ and $r_V=(r_i:i\in V)$ denote the secret-key rate and discussion-rate vector, respectively. Write … Let $\mathcal R$ denote the achievabl…

Let $\ell$ be the secret message size, let $n$ be the network dimension, let $t$ be the security parameter, and let $e$ be the number of list-decodable rank errors for which the li…

A sum-network is a network in which every terminal demands the sum of the symbols generated at all sources. Consider the class of sum-networks having three sources and $n\geq 3$ te…