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

We shall study $D$-LQPs for the domains $D=\mathbb{Z}_{q}$, the ring of integers modulo $q$ (with $q\ll n$) as well as $D=\mathbb{Z}$, but with coefficients of small magnitude (at most $\operatorname{poly}(n)$, say). Such restrictions on the coefficients are necessary, because allowing arbitrary integer coefficients makes it possible to recover the entire input $\mathbf{z}$ with the single query $\sum_{i=1}^{n}2^{i-1}z_{i}$.

When $D=\mathbb{Z}_{q}$, for small $q$, solving elemx without the promise that $\mathbf{1}^{\mathsf{T}}\mathbf{z}\neq 0$ is hard, regardless of the number of rounds. Intuitively, there is no cheap way to deterministically verify that a subset $I\subseteq[n]$ indeed contains an index $i\in I$ where $z_{i}\neq 0$. Defining the “cost” of an LQP to be the number of queries it makes in the worst case (formally defined in Section 2), we obtain the following not-too-hard results.

As noted earlier, adding the promise that $\mathbf{1}^{\mathsf{T}}\mathbf{z}\neq 0$ permits a more efficient $k$-round deterministic algorithm. For each integer $q\geq 2$, define $\textsc{elemx}^{(q)}_{n}$ to be the version of $\textsc{elemx}_{n}$ where we are given the stronger promise that $\mathbf{1}^{\mathsf{T}}\mathbf{z}\neq 0$ under arithmetic in $\mathbb{Z}_{q}$. Equivalently, using set notation, we are promised that $|Z|\not\equiv 0\pmod{q}$. We prove the following results, using similar round-elimination arguments.

Although Theorem 1.4 subsumes Theorem 1.3 in the asymptotic sense, we find it useful to present the former result in full, first, to lay the groundwork for our subsequent lower bound proofs. As we shall see, the fact that $\mathbb{Z}_{2}$ is a field leads to an especially clean execution of the round elimination strategy. Note also that a weaker form of Theorem 1.3 follows from existing work on formula size-depth tradeoffs (see Section 7); however, the resulting proof, once fully unrolled, is considerably more complex than our direct argument.

At a high level, a lower bound proof based on round elimination works as follows. We consider a hypothetical $k$-round protocol for $n_{k}$-dimensional instances of some problem $P$ that does not incur much cost in its first round. Based on this low cost, we extract a $(k-1)$-round protocol for $n_{k-1}$-dimensional instances of $P$ by “lifting” these smaller instances to special $n_{k}$-dimensional instances on which the $k$-round protocol essentially “wastes” its first round. If we can carry out this argument while ensuring that the shrinkage from $n_{k}$ to $n_{k-1}$ is not too drastic, then a too-cheap $k$-round protocol will eventually give us a $0$-round protocol for a nontrivial instance dimension, leading to a contradiction.

In the proofs of the above two theorems, this strategy is executed by identifying a large collection of pairwise disjoint sets that are treated identically in the protocol’s first round. Viewing these sets as blocks of indices within $[n]$, we consider block-structured instances of $\textsc{elemx}_{n}$ and proceed to lift general instances of $\textsc{elemx}_{n^{\prime}}$ into these block-structured ones. In Theorem 1.3, these blocks arise from elementary linear algebraic considerations. In Theorem 1.4, the fact that inputs are in $\{0,1\}^{n}$ instead of $\mathbb{Z}_{q}^{n}$ necessitates a brief excursion into additive combinatorics.

Finally, we consider LQPs over $\mathbb{Z}$, the ring of all integers, but with bounds on the magnitude of coefficients (which, as we noted earlier, is necessary in order to have nontrivial results). To be precise, we consider domains of the form $\mathbb{Z}_{[b,c]}:=\{a\in\mathbb{Z}:\,b\leq a\leq c\}$. While we are unable to prove a full tradeoff lower bound in this case, we do obtain a near-optimal result for $k=2$ rounds.

The former result is straightforward, based on the simple observation that such an LQP can extract the entire input $\mathbf{z}$ followed by basic information theoretic considerations. Incidentally, the problem of extracting all of $\mathbf{z}$ using $\mathbb{Z}_{[0,1]}$-LQPs has a long history as the coin weighing problem, for which a 1-round $O(n/\log n)$ algorithm exists; see Section 1.2.

The significant result here is the latter. It again uses a round elimination strategy and, as before, the bird’s-eye view is that we identify disjoint blocks of indices to engineer a suitable lifting. This time, the blocks arise out of extremal combinatorics considerations, specifically the sunflower lemma, in its recently strengthened form [Rao20]. Furthermore, upon carrying out this round elimination, we are left with a $1$-round LQP that solves elemx only under a cardinality constraint on the input set. To finish the proof, we must demonstrate hardness even for this special case. This is not as straightforward as Proposition 1.5: our argument to handle this hinges on the Frankl–Wilson theorem [FW81] on set systems with forbidden intersection sizes.

Attempts to extend the above proof outline to handle more than two rounds runs into technical issues of integer divisibility. We suspect that this is an artifact of our proof machinery and not inherent to the problem. We conjecture that every deterministic $k$-round $\mathbb{Z}_{[-B,B]}$-LQP requires cost $\widetilde{\Omega}(n^{1/k})$, suppressing polylogarithmic factors. Indeed, we believe that much more is true, and that a communication complexity analogue of such a tradeoff also holds. We shall take this up after a discussion of related work.

Our work touches upon several themes with long histories of study in computer science: determinism versus randomization, adaptivity versus non-adaptivity, sublinear algorithms, and input access through structured queries. With these connections in mind, we recall a small number of works that are either close in spirit to ours or shed light on some aspect of this work.

The most basic query model is the Boolean decision tree. In this setting, deterministic and randomized complexities are polynomially related for total Boolean functions [BdW02, ABB⁺17], whereas arbitrarily large gaps are possible for search problems [LNNW95]. Parity decision trees—equivalent to our $\mathbb{Z}_{2}$-LQPs—have been studied in several works (e.g., [ZS10, HHL18] and the references therein), usually for Boolean functions and focusing on connections with communication complexity of XOR-composed functions. Beyond the Boolean—or indeed the discrete—setting lie linear decision trees, where the input is a real vector and one can query the sign of a linear form [DL78, KLM19]. All such “decision tree” models are fully adaptive and the vast majority of works using them do not focus on amount of adaptivity as a resource.

At the other extreme is the (nonadaptive) linear sketching model, where a high-dimensional input is accessed through one batch of linear queries (equivalently, through a low-dimensional sketch of it produced by a sketching matrix). This paradigm is ubiquitous in data streaming algorithms and compressed sensing [Mut05, Don06, Woo14, CY20] and has connections to dimension reduction and metric embeddings. Some recent work carries the message that linear sketching might be a complete paradigm for a large class of data streaming algorithms [LNW14] and certain communication protocols [KMSY18, HLY19]. Most work on linear sketching considers randomized sketches, since determinism often precludes sublinear cost.

Turning to determinism, the well-studied coin weighing problem, put in our terms, asks for a $\mathbb{Z}_{[0,1]}$-LQP that retrieves the entire input $\mathbf{z}\in\{0,1\}^{n}$. It has long been known that $(2\pm o(1))n/\log n$ nonadaptive queries are necessary and sufficient. Special cases and variants of this problem have been studied over the years; see [ER63] for some early history and [Bsh09, MK13] for recent history. While some of these works consider adaptive LQPs, there is no strong rounds-vs-queries tradeoff for this problem, which is harder than elemx.

The body of work on round complexity under linear queries is much smaller. There is one recent work very close to ours: Assadi, Chakrabarty, and Khanna [ACK20] studied a problem very similar to elemx that they called single-element-recovery, where the input is a vector $\mathbf{x}\in\mathbb{R}_{\geq 0}^{n}$, and by applying $\mathbb{R}$-linear queries one wishes to recovery an arbitrary element from the support of $\mathbf{x}$. While their query model is much stronger than our $\mathbb{Z}$-linear or $\mathbb{Z}_{q}$-linear queries, it is balanced by the $\mathbb{R}_{\geq 0}$-valued inputs that prevent tricks to recover the entire input in one query. Their main theorem implies that the deterministic $k$-round search algorithm making roughly $k(n^{1/k}-1)$ queries in total—very similar to Algorithm 1—has cost exactly matching the lower bound. Linear queries and adaptivity are also featured together in some work on sparse recovery problems. One such problem is to find an approximately closest $s$-sparse vector $\mathbf{x}^{\star}$ to an input $\mathbf{x}$, using $\mathbb{R}$-linear queries to the input and $r$ rounds of adaptivity. For this, [PW13] have proven near optimal lower bounds of $\Omega(r(\log n)^{1/r})$ when $s=1$ and [KP19] have extended them to small $s$, proving $\Omega(\frac{1}{r}s(\log n)^{1/r})$ queries are needed when $\log s<(\log n)^{1/r}$.

A number of works consider rounds of adaptivity in query models beyond linear queries. Recent examples include works on maximizing submodular functions through adaptive oracle queries [BS18]; on adaptivity hierarchy theorems in property testing [CG18]; on identifying biased coins through pairwise comparisons or in multi-armed bandit settings [AAAK17]; and on finding approximately maximum bipartite matchings through demand queries and OR-queries [Nis21]. Other works have studied adaptivity in the massive parallel communication/computation (MPC) model [BKS17] and in various graph query models [AB19, BHPSR⁺20].

A rich body of work on cost/adaptivity tradeoffs is found in communication complexity, where adaptivity manifests as rounds of interaction. An early work [NW93] gave exponential separations between $k$ and $k+1$ rounds for all $k$ and introduced a round elimination paradigm that remains ubiquitous to this day. This work also explains how an earlier result [KW90] connecting circuit and communication complexities can be used to relate bounded-round communication complexity for a specific problem to the size of bounded-depth, unbounded fan-in formulas. More work has been spurred by applications of bounded-round communication lower bounds in data structures, where they provide lower bounds in the cell-probe model [MNSW98, Sen03, CR04, PT07, LPY16]; and in streaming algorithms, where they translate naturally to tradeoffs between the number of passes made over the input stream and the working memory required [GM09, ER14, GO16, CCM16, CW16]. In much of this body of work, round elimination is performed using information theoretic arguments that naturally provide lower bounds against randomized algorithms.

In contrast, it is rare to see deterministic tradeoffs where corresponding randomized ones do not hold because randomization makes the problem “too easy.” This is exactly the situation with elemx, as shown by this work in the context of the randomized upper bounds (Section 6) via $\ell_{0}$-sampling [JST11]. In light of the preceding discussion, our instantiations of round elimination must use techniques beyond Shannon-style information theory. They indeed do. Our techniques therefore have the potential for further use in separating determinism from randomization in this fine-grained (round aware) sense.

Our query complexity results on elemx suggest a tantalizing communication complexity analogue. Let $\textsc{ur}^{\subset}_{n}$ denote⁵⁵5The notation, due to Nelson and Yu [NY19], is to be read as “universal relation with a subset constraint.” the communication complexity problem where Alice and Bob receive sets $X,Y\subseteq[n]$ respectively with the promise that $Y\subset X$, and their goal is to produce an element in $X\smallsetminus Y$. Clearly, a $k$-round query protocol for elemx making $q$ queries, with each answer lying in a set of size $M$, provides a $k$-round communication protocol for $\textsc{ur}^{\subset}$ using at most $q\log M$ bits. Therefore, our results here would be subsumed, in an asymptotic sense, if one could resolve the following conjecture positively.

We find the above conjecture compelling because it would demonstrate a new phenomenon in communication complexity, where a problem is easy for one-round randomized and for interactive deterministic protocols, but exhibits a nontrivial tradeoff for bounded-round deterministic ones.

In passing, we note that the $\textsc{ur}^{\subset}$ problem was introduced in [KNP⁺17] where its randomized communication complexity was studied. The randomized lower bound was subsequently used by Nelson and Yu [NY19] to prove the optimality of Ahn, Guha, and McGregor’s graph sketching algorithm for graph connectivity [AGM12]. An outstanding open question about the latter problem (viewed as a communication problem where $n$ players, each holding a vertex neighborhood, talk to a coordinator who determines whether the graph is connected) is whether it admits a deterministic algorithm with sublinear communication. A better understanding of $\textsc{ur}^{\subset}$ in the deterministic setting could be key to addressing this question.

There are also two problems similar to $\textsc{ur}^{\subset}$ for which lower bounds have already been proven. The universal relation problem ur gives Alice and Bob unequal sets $X,Y\subseteq[n]$ and asks them to produce an element $i\in(X\smallsetminus Y)\cup(Y\smallsetminus X)$. This has deterministic communication complexity $\geq n+1$ [TZ97]. The Karchmer-Wigderson game for $\textsc{parity}_{n}$ is the problem ur with the additional constraints that $|X|$ be even and $|Y|$ be odd; existing circuit complexity results [Has86, Ros15] imply, as briefly explained in Section 7, that $k$-round deterministic communication protocols for this require $\Omega(k(n^{1/k}-1))$ bits of communication.

The search problem $\textsc{elemx}_{n}$ was already formally defined in eq. 1. We shall also work with special cases of this problem, where the cardinality of the input set is further restricted in some way. These are formalized as follows: we define

In the course of this paper, we will use several important theorems from combinatorics. For results on $\mathbb{Z}_{q}$-LQPs (proved in Section 4), we use the following result of van Emde Boas and Kruyswijk [vEBK69] on zero sumsets, slightly reworded to use modern notation.

A stronger result that $s(G)=1+r(q-1)$ applies when $G=\mathbb{Z}_{q}^{r}$ and $q$ is a prime power [Ols69]; it is conjectured that the prime-power constraint is unnecessary [GG06, conjecture 3.5].

When working over $\mathbb{Z}$ (in Section 5), we use the well-known notion of a sunflower and the following recent result of Rao [Rao20], which refines the noted result of Alweiss, Lovett, Wu, and Zhang [ALWZ20] that improved the classic sunflower lemma of Erdős and Rado [ER60]. The note [BCW20] further improves Rao’s bound by replacing the $\log(pt)$ factor with $\log t$, but this will not affect our proof. Tao [Tao20] gives an alternative presentation of Rao’s result which may be simpler to follow.

In a different part of our argument, we will need a well known theorem of Frankl and Wilson [FW81].

We now describe a framework for our round elimination arguments. For this section, we shall work over a general ring (with unity), $R$, and “LQP” will mean a $D$-LQP where $D\subseteq R$. Fix this ring $R$.

Suppose we have an LQP $\Pi$ that operates on inputs in $\{0,1\}^{n}$ and produces outputs in $[n]$. Further, suppose $S_{1},\ldots,S_{m}\subseteq[n]$ is a collection of pairwise disjoint nonempty sets. We then define a certain LQP $\Pi^{(S_{1},\ldots,S_{m})}$ operating on inputs in $\{0,1\}^{m}$ and producing outputs in $[m]$. To aid intuition, we describe the construction procedurally in Algorithm 1.

To define $\Pi^{\prime}:=\Pi^{(S_{1},\ldots,S_{m})}$ formally, we first define the lifting matrix

whose entries lie in $\{0,1\}$ and which maps the input space of $\Pi^{\prime}$ to the input space of $\Pi$ according to 1, thanks to the pairwise disjointness of the sets $S_{i}$. At a given node $v$ of $\Pi$, labeled with $A_{v}\in\mathbb{Z}_{q}^{d_{v}\times n}$, the simulation in 2 would retrieve the measurement $A_{v}\mathbf{z}=A_{v}L\mathbf{w}$. The protocol $\Pi^{\prime}$ can get the same result by making the query $A_{v}L\in\mathbb{Z}_{q}^{d_{v}\times m}$.

Thus, the protocol tree for $\Pi^{\prime}$ is formed as follows. Prepare a copy of $\Pi$ and let $\varphi\colon\Pi^{\prime}\to\Pi$ be the natural bijection between their nodes. Label each internal node $v$ of $\Pi^{\prime}$ with $A_{v}:=A_{\varphi(v)}L$. Copy over all edge labels from $\Pi$ to $\Pi^{\prime}$. For each leaf $\ell$ of $\Pi^{\prime}$, if $o_{\varphi(\ell)}\in S_{i}$, then assign label $o_{\ell}:=i$. If no such $i$ exists, assign $o_{\ell}:=1$ (say). This labeling is well defined because of the pairwise disjointness of the sets $S_{i}$.

In the sequel, to perform round elimination, we shall use the construction of $\Pi^{\prime}$ in a special way that we record in the lemma below. We also record a definition that will be relevant when invoking the lemma.