17 problems

Let $N(n,3,t)$ denote the sequence reconstruction number for length-$n$ sequences over a binary deletion channel with three deletions and trace length parameter $t$, and let…

Extremal intersection conjecture. For $q\geqslant 4$ and sufficiently large $n$, we have

The successive-cancellation tree decoder and the neural polar decoder are being compared for deletion-channel codes, and the neural decoder appears to attain slightly better frame-…

Uniform-capacity threshold conjecture.

Let $X$ be uniformly distributed on $\{0,1\}^n$, let $Y=\operatorname{BDC}_d(X)$ be the output of the binary deletion channel with deletion probability $d$, and let…

Concentration conjecture, weak form. Almost surely,

Let $C_{\text{unif}}(d)$ denote the maximum coding rate achievable by uniformly-random codes for the binary deletion channel with deletion probability $d$. Positive-rate conjecture…

Let $\operatorname{BDC}_p$ be the binary deletion channel, and let $\mathcal{G}_{\operatorname{BDC}}$ be its channel group acting on $\{0,1\}^n$. The transformations that flip all…

Let $N(n,\ell,t)$ denote the minimum number of traces of length $t$ needed to reconstruct every binary sequence of length $n$ with deletion distance parameter $\ell$, as defined in…

Let $C(d)$ denote the capacity of the binary deletion channel with deletion probability $d\in[0,1]$. Dalai's convexity conjecture. The capacity curve $d\mapsto C(d)$ is convex on t…

Tian et al.'s polarization conjecture. Polarization occurs as $N \to \infty$ while the total number of deletions $d$ remains fixed.

Alternating-string conjecture. The alternating string $x=\texttt{1010...}$ minimizes the autocorrelation coefficient $\kappa^2$.

Let $x$ be a binary subsequence of length $m$, and let $H_n(x)$ denote the entropy associated with the uncertainty set of binary supersequences of length $n$ containing $x$, weight…

Let $N_m$ denote the smallest sequence length for which every binary sequence can be reconstructed from the distribution of the sequence obtained after deleting all but $m$ symbols…

Let $d$ be the deletion probability, let $C$ denote the capacity of the deletion channel, and let $\mathbb{X}^\dagger$ denote the input process constructed in the paper. The conjec…

Monotonicity conjecture for $C_4$. The bound $C_4$ improves as $L$ increases, and this behavior holds for every value of $L$.

Monotonicity conjecture for $C_3$. The bound $C_3$ improves as $L$ increases, and this behavior holds for every value of $L$.