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

Abstract

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 \textsc{element-extraction} in a query model that combines both: linear measurements with bounded adaptivity. In the \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 ${\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 \textsc{element-extraction} algorithm must spend $\Omega (k(n^{1/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{\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}.

References in corpus (1)

• On the parity complexity measures of Boolean functions