The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries

Two widely-used computational paradigms for sublinear algorithms are using linear measurements to perform computations on a high dimensional input and using structured queries to access a massive input. Typically, algorithms in the former paradigm are non-adaptive whereas those in the latter are highly adaptive. This work studies the fundamental search problem of $\text{textsc}element-extraction$ in a query model that combines both: linear measurements with bounded adaptivity. In the $\text{textsc}element-extraction$ problem, one is given a nonzero vector $\mathbf{z}=(z_1,\dots ,z_n)\in \{0,1{\}}^n$ and must report an index $i$ where $z_i=1$. The input can be accessed using arbitrary linear functions of it with coefficients in some ring. This problem admits an efficient nonadaptive randomized solution (through the well known technique of ${\mathrm{\ell }}_0$-sampling) and an efficient fully adaptive deterministic solution (through binary search). We prove that when confined to only $k$ rounds of adaptivity, a deterministic $\text{textsc}element-extraction$ algorithm must spend $\mathrm{\Omega }(k(n^{1\mathrm{/}k}-1))$ queries, when working in the ring of integers modulo some fixed $q$. This matches the corresponding upper bound. For queries using integer arithmetic, we prove a $2$-round $\tilde{\mathrm{\Omega }}(\sqrt{n})$ lower bound, also tight up to polylogarithmic factors. Our proofs reduce to classic problems in combinatorics, and take advantage of established results on the {\em zero-sum problem} as well as recent improvements to the {\em sunflower lemma}.