Deterministic constant-column-sparsity small-singular-value conjecture

Fix an integer $d\geq 2$ and a constant $C>0$. Let $r(k),n_k\in\mathbb{N}$ satisfy

$$\frac{k}{r(k)}\to C, \qquad \frac{n_k}{r(k)}\to\infty.$$

For each $k$, let $M^{(k)}\in\{-1,0,1\}^{k\times n_k}$ be a deterministic matrix whose every column has exactly $d$ nonzero entries. Choose $\Omega_k\subset[n_k]$ uniformly from $\binom{[n_k]}{r(k)}$. Unrestricted deterministic sparse-sketch conjecture. Then

$$s_{\min}\bigl(M^{(k)}_{\Omega_k}\bigr)=o(1)$$

with probability $1-o(1)$. This open problem asks whether the paper's structural double-overlap assumption is necessary. It concerns the scarcity of well-invertible column subsets in deterministic sparse matrices; the source provides no resolution.