42 problems

Erdős–Frankl–Füredi conjecture.

Let $p\in(0,(3-\sqrt{5})/2)$ denote the prevalence, and let $N_{opt}^{(S)}$ be the rounded optimal configuration for the Sterrett group-testing scheme. Malinovsky–Albert conjecture…

Hu–Hwang–Wang conjecture. Individual testing is optimal when $\beta\geq 1/3$; equivalently, every such algorithm requires

Linear-regime threshold conjecture. The result of Theorem $$ is the correct result for arbitrary test designs without multi-edges.

Arbitrary-design threshold conjecture. The bound in Theorem $$ represents the correct information-theoretic threshold even for arbitrary test designs.

Analytic maximization conjecture. For every $c>c_{\mathrm{inf}}^{\mathrm{TGT}}$, the function

GPTA optimality conjecture. Among all nested testing procedures that preserve the order $u_1,u_2,\ldots,u_n$, the GPTA is an optimal nested procedure. It is not necessarily uniquel…

Lower-bound conjecture. The quantity

Binary-splitting decoding complexity conjecture. To find no false negatives, the decoding algorithm must examine subtrees of depth

MSGT list-size conjecture. Substituting $L=\gamma K$ establishes a lower limit for $\gamma$ that guarantees that the MSGT algorithm's error probability is at most that of the maxim…

The sparse pooled data problem has items partitioned into compartments, and the algorithm's error probability is bounded using a union bound over items; for items in the same compa…

Polynomial-delay code conjecture. There exists a tropical code using the same underlying block design whose maximum delay is polynomial in the relevant parameters, rather than the…

Yao–Hwang conjecture. There exists $p_0\in\left[\frac{2-\sqrt{2}}{2},\frac{3-\sqrt{5}}{2}\right]$ such that, for every $p\in\left[p_0,\frac{3-\sqrt{5}}{2}\right]$, PTA is optimal o…

Let $M_0$ be the binomial random variable discussed in the preceding bound, and consider the final integral term in the upper bound of Theorem, both with and without approximating…

Let $x$ be the prevalence of a condition in a homogeneous population, let $\gamma_1$ be the threshold at which the elementary algorithm $\mathcal A_1$ becomes dominant, and let…

In the probabilistic group testing model, let the lower and upper bounds refer to the numbers of nonadaptive measurements required to achieve error probability tending to zero in t…

Sample-complexity conjecture. For any monotone test function $f(\cdot)$,

Consider a finite population of size $N$ and Procedure $D$ in group testing. An optimal partition is a collection of subgroup sizes $\{n_1,\ldots,n_I\}$ with … that minimizes the e…

Hu–Hwang–Wang cutoff-point conjecture. For $r\leq 3$,

Let $R$ satisfy … For every $\epsilon>0$, let $C=C(\epsilon)$ be a constant. Here $k$, $n_{\mathrm{pos}}$, $p'$, and the profile $\phi(\ell)$, as well as the first moment function…

Subset Select rank conjecture. For every polynomial-time Subset Select algorithm, the resulting output matrix satisfies the desired rank condition.

Rank conjecture. For sufficiently large $n$, all such submatrices have, with high probability, rank at least

Let $p$ be the prevalence parameter, let $(k,m)$ be an optimal nested strategy for $p$, and write $m$ through its pool-size sequence $\pi$. Corroborated-for-$p>2^{-51}$ conjecture.…

Let $p\binom{}{}$ be the prevalence parameter, let $D_k(m,p)$ denote the cost of a nested strategy $(k,m)$, and let $m_{33}$ and $m_{34}$ be the strategies defined by … and … A str…

Consider either combinatorial nonadaptive group testing, where $k$ uniformly randomly chosen items among $n$ are defective, or probabilistic nonadaptive group testing, where each o…