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

Amit<EMAIL_ADDRESS>Department of Computer
Science, Dartmouth College Manuel<EMAIL_ADDRESS>Department of Computer Science, Dartmouth College

###### 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 element-
extraction in a query model that combines both: linear measurements with
bounded adaptivity.

In the element-extraction problem, one is given a nonzero vector
$\mathbf{z}=(z_{1},\ldots,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 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 $\widetilde{\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
zero-sum problem as well as recent improvements to the sunflower lemma.

#### Keywords:

query complexity; linear measurements; sketching; round elimination

#### Acknowledgements:

We thank Deeparnab Chakrabarty, Prantar Ghosh, and anonymous reviewers for
several helpful discussions, comments, and pointers.

This work was supported in part by NSF under award 2006589.

##  1 Introduction

Determinism versus randomization in algorithm design is a fundamental concern
in computer science and is the topic of a great many works in complexity
theory. In “space-constrained” models such as communication complexity and
data streaming, basic results show that derandomization can entail an
exponential or worse blow-up in cost. For instance, in the two-party
communication setting, the very basic $n$-bit equality problem admits a
bounded-error randomized protocol with only $O(1)$ communication ($O(\log n)$
if restricted to private coins), whereas its deterministic communication
complexity is as large as it gets, namely $n+1$. In the data streaming
setting, the similarly basic distinct-elements problem admits a one-pass
bounded-error randomized algorithm that uses $O(\log n)$ space to provide a
$(1+\varepsilon)$-approximation [KNW10], whereas a deterministic algorithm
would require $\Omega(n)$ space, even if multiple passes and large
approximation factors are allowed [CK16]. In this work, we explore such a
price-of-determinism phenomenon in the _query complexity_ world, for a
similarly basic search problem.

The focus of our study is a search problem that we call element-extraction
(henceforth, elemx), where the input is a set
$Z\subseteq[n]:=\\{1,\ldots,n\\}$, promised to be nonempty, and the goal is to
extract any element from $Z$. Formally, this is a total search problem given
by the relation $\textsc{elemx}_{n}\subseteq 2^{[n]}\times[n]$, where

$\displaystyle\textsc{elemx}_{n}=\left\\{(Z,i):Z\subseteq[n],\,i\in[n],\,\text{and
}|Z|>0\Rightarrow i\in Z\right\\}\,.$ (1)

As is often the case, the natural correspondence between sets in $2^{[n]}$ and
vectors in $\\{0,1\\}^{n}$ will be useful. Indeed, we shall freely switch
between these two viewpoints, using the notational convention that uppercase
letters denote sets and their corresponding lowercase boldface variants denote
characteristic vectors. Thus, we can also formalize elemx as

$\displaystyle\textsc{elemx}_{n}=\left\\{(\mathbf{z},i):\mathbf{z}=(z_{1},\ldots,z_{n})\in\\{0,1\\}^{n},\,i\in[n],\,\text{and
}\mathbf{1}^{\mathsf{T}}\mathbf{z}>0\Rightarrow z_{i}=1\right\\}\,.$ (2)

The goal of an algorithm solving elemx is to produce an output $i$ such that
$(Z,i)\in\textsc{elemx}$: with certainty in the deterministic setting, and
with probability $\geq 2/3$ (say) in the randomized setting. In other words,
the algorithm must produce a _witness_ of the nonemptiness of $Z$. To do so,
the algorithm may access $Z$ (equivalently, $\mathbf{z}$) using linear
queries, as we shall now explain.

In a Boolean decision tree model, an algorithm may only access the input
vector by querying its individual bits. In such a setting, there is not much
to say about elemx: even randomized algorithms are easily seen to require
$\Omega(n)$ queries. But things get interesting if we allow more powerful
queries: specifically, linear ones. Let us define a _linear query protocol
over domain $D$_ (a $D$-LQP, for short) to be a query protocol wherein each
query is an evaluation of a linear form $\sum_{i=1}^{n}a_{i}z_{i}$, where each
$a_{i}\in D$. The domain $D$ should be thought of a “reasonable” subset of a
ring containing $\\{0,1\\}$—e.g., a finite field, or integers with bounded
absolute value—and the linear functions will be evaluated in the underlying
ring. The cost of an LQP is the number of linear form evaluations used.333Note
that this is somewhat lower than the number of bits needed to encode the
output of the queries. In this work we particularly care about the amount of
adaptivity in an LQP, which quantifies the extent to which each query depends
on the outcomes of previous queries.

To set the stage, we recall the problem of $\ell_{0}$-sampling [FIS08, CF14],
from the world of sketching and streaming algorithms. The goal of
$\ell_{0}$-sampling is to sample a pair $(i,x_{i})$ from a nonzero input
vector $\mathbf{x}\in\mathbb{R}^{n}$ (say), so that $x_{i}\neq 0$ and $i$ is
distributed nearly uniformly on the support of $\mathbf{x}$. This is a
fundamental primitive, used as a low-level subroutine in a wide range of
applications in streaming and other “big data” algorithms. There are several
solutions to this problem [CF14], most of which provide a linear sketching
scheme, wherein one computes $\mathbf{y}=S\mathbf{x}$ for a certain random
$d\times n$ matrix $S$ and then runs a recovery algorithm on the low-
dimensional vector $\mathbf{y}$ to produce the desired sample. Notice that if
the input is a vector $\mathbf{z}\in\\{0,1\\}^{n}$, such a scheme provides a
randomized LQP for $\textsc{elemx}_{n}$ (allowing a small probability of
error). In particular, using the optimal $\ell_{0}$-sampling sketch of
Jowhari, Sağlam, and Tardos [JST11], we obtain a $\mathbb{Z}$-LQP that makes
$O(\log n)$ queries, using coefficients in $\\{0,1,\ldots,n\\}$, and has the
pleasing property of being non-adaptive. We can also obtain a
$\mathbb{Z}_{q}$-LQP that makes $O(\log^{2}n/\log q)$ queries;444Throughout
this paper, “$\log$” denotes the base-$2$ logarithm. details in Section 6.

Turning to the deterministic setting—our main focus in this paper—it is easy
to show that a non-adaptive $\mathbb{Z}$-LQP for $\textsc{elemx}_{n}$ must
make $\Omega(n/\log n)$ queries, for basic information-theoretic reasons. For
completeness, we give the proof in Proposition 1.5. However, this heavy
determinism penalty disappears upon moving to general deterministic LQPs,
where we can use adaptivity. Indeed, a simple binary search strategy leads to
a $\mathbb{Z}$-LQP that makes $O(\log n)$ queries, using coefficients in
$\\{0,1\\}$. We can refine this observation to trade off the query complexity
for amount of adaptivity. This brings us to our central concept.

Define a $k$-round LQP to be one where the queries are made in batches that we
call rounds: the collection of linear forms defining the queries in round $i$
depend only on the results of queries made in rounds $1,\ldots,i-1$ (a formal
definition appears in Section 2). Then, a natural generalization of the binary
search strategy provides a $k$-round $\mathbb{Z}$-LQP for elemx, using
coefficients in $\\{0,1\\}$, making at most $k(\lceil n^{1/k}\rceil-1)$
queries in total. When we are additionally promised that
$\mathbf{1}^{\mathsf{T}}\mathbf{z}\neq 0$, where addition is performed in the
ring $\mathbb{Z}_{q}$, then this algorithm also works as a
$\mathbb{Z}_{q}$-LQP; details in Section 6. Notice that $k$-round LQPs
naturally interpolate between linear sketches at one extreme (when $k=1$) and
linear decision trees at the other (when $k=n$).

The most important message of this paper is that the above rounds-versus-
queries tradeoff is asymptotically tight for deterministic linear query
protocols for elemx, in several natural settings. We state our results
informally for now, with formal statements given after the necessary
definitions and preliminaries.

###  1.1 Our Results and Techniques

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.

######  Proposition 1.1.

Every deterministic $\mathbb{Z}_{2}$-LQP for $\textsc{elemx}_{n}$ has cost
$\geq n-1$, which is optimal.

######  Proposition 1.2.

For $q\geq 3$, every deterministic $\mathbb{Z}_{q}$-LQP for
$\textsc{elemx}_{n}$ has cost $\geq{n}/(2q\ln q)$.

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.

######  Theorem 1.3.

Every deterministic $k$-round $\mathbb{Z}_{2}$-LQP for
$\textsc{elemx}^{(2)}_{n}$ has cost $\geq k(n^{1/k}-1)$.

######  Theorem 1.4.

Every deterministic $k$-round $\mathbb{Z}_{q}$-LQP for
$\textsc{elemx}^{(q)}_{n}$ has cost
$\Omega\left(\frac{1}{q^{1+1/k}\ln^{2}q}k(n^{1/k}-1)\right)$.

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.

######  Proposition 1.5.

Every deterministic $1$-round $\mathbb{Z}_{[-B,B]}$-LQP for
$\textsc{elemx}_{n}$ costs $\Omega({n}/\log(nB))$.

######  Theorem 1.6.

Every deterministic $2$-round $\mathbb{Z}_{[-B,B]}$-LQP for
$\textsc{elemx}_{n}$ costs $\Omega(\sqrt{n}/\log^{3/2}(nB))$.

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.

###  1.2 Related Work and Connections

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}$ denote555The 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.

######  Conjecture 1.7.

Every deterministic $k$-round communication protocol for
$\textsc{ur}^{\subset}$ costs $\widetilde{\Omega}(n^{1/k})$ bits, suppressing
polylogarithmic factors.

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.

##  2 Preliminaries

Throughout the paper, we shall freely switch between the equivalent viewpoints
of sets in $2^{[n]}$ and vectors in $\\{0,1\\}^{n}$, using the notational
convention that when an uppercase letter (e.g., $S,Z$) denotes a set, the
corresponding lowercase boldface letter (e.g., $\mathbf{s},\mathbf{z}$)
denotes the characteristic vector of that set and vice versa.

###  2.1 Various Definitions

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

$\displaystyle\textsc{elemx}^{(q)}_{n}$
$\displaystyle=\left\\{(Z,i):Z\subseteq[n],\,i\in[n],\,\text{and
}|Z|\not\equiv 0{\@displayfalse\pmod{q}}\Rightarrow i\in Z\right\\}\,;$ (3)
$\displaystyle\textsc{elemx}^{(q,h)}_{n}$
$\displaystyle=\left\\{(Z,i):Z\subseteq[n],\,i\in[n],\,\text{and }|Z|\equiv
h{\@displayfalse\pmod{q}}\Rightarrow i\in Z\right\\}\,;$ (4)
$\displaystyle\textsc{elemx}^{1/4}_{n}$
$\displaystyle=\left\\{(Z,i):Z\subseteq[n],\,i\in[n],\,\text{and
}|Z|=n/4\Rightarrow i\in Z\right\\}\,.$ (5)

######  Definition 2.1 (Protocol).

Let $f\subseteq\\{0,1\\}^{n}\times\mathcal{O}$ be a search problem with input
space $\\{0,1\\}^{n}$ and output space $\mathcal{O}$. A deterministic _$k$
-round $D$-linear query protocol_ ($D$-LQP), $\Pi$, on this input space is a
rooted tree of depth $k$ where each internal node $v$ is labeled with a matrix
$A_{v}\in D^{d_{v}\times n}$; each leaf node with an output
$o_{\lambda}\in\mathcal{O}$; and the edges from a node $v$ to its children are
labeled with the elements of
$\mathcal{M}_{v}:=\\{A_{v}\mathbf{z}:\,\mathbf{z}\in\\{0,1\\}^{n}\\}$
bijectively. The quantity $d_{v}$ of node $v$ is the _cost_ of the node,
sometimes also denoted $\operatorname{cost}(v)$. Given an input
$\mathbf{z}\in\\{0,1\\}^{n}$, the _measurement at_ internal node $v$ is
$A_{v}\mathbf{z}$. The transcript of $\Pi$ on $\mathbf{z}$ —denoted
$\Pi(\mathbf{z})$—is the unique root-to-leaf path obtained by walking along
the edges determined by these measurements; the _$j$ th measurement_ is the
label of the $j$th edge on this path; and the _output_ is the label $o_{\ell}$
of the leaf $\ell:=\ell(\Pi(\mathbf{z}))$ reached by this path. We say that
$\Pi$ solves $f$ if $(\mathbf{z},o_{\ell})\in f$ for every input $\mathbf{z}$.

Since this paper is largely focused on deterministic complexity, henceforth we
shall assume that all LQPs are deterministic unless stated otherwise.

######  Definition 2.2 (Cost).

The _query cost_ of a protocol $\Pi$ is:

$\displaystyle\operatorname{cost}(\Pi)$
$\displaystyle:=\max_{\mathbf{z}\in\\{0,1\\}^{n}}\operatorname{cost}(\Pi;\mathbf{z})\,,\qquad\text{where}\quad\operatorname{cost}(\Pi;\mathbf{z}):=\sum_{v\text{
internal node on }\Pi(\mathbf{z})}d_{v}\,,$

which is, informally, the number of linear queries performed when $\Pi$
executes on $\mathbf{z}$. While we do not focus on bit complexity in this
paper, it is worth noting that to make an information-theoretically fair
comparison between different domains, one should consider the number of bits
returned in response to all the queries. This number may be larger than
$\operatorname{cost}(\Pi)$, though only by an $O(\log n)$ factor for
$D=\mathbb{Z}_{[-B,B]}$ with $B=\operatorname{poly}(n)$, and not at all for
$D=\mathbb{Z}_{2}$.

######  Definition 2.3 (Complexity).

The $D$-linear query complexity and $k$-round $D$-linear query complexity of a
search problem $f$ are defined, respectively, to be

$\displaystyle\operatorname{LQ}_{D}(f)$
$\displaystyle=\min\\{\operatorname{cost}(\Pi):\Pi\text{ is a $D$-LQP that
solves }f\\}\,;$ $\displaystyle\operatorname{LQ}_{D}^{k}(f)$
$\displaystyle=\min\\{\operatorname{cost}(\Pi):\Pi\text{ is a $k$-round
$D$-LQP that solves }f\\}\,.$

###  2.2 Useful Results from Combinatorics

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.

######  Theorem 2.4 ([vEBK69]).

Let $G$ be a finite abelian group with exponent666The exponent of a group is
the least common multiple of the orders of its elements. $\exp(G)$ and order
$|G|$. Let $s(G)$ be the minimal positive integer $t$ for which any sequence
of $t$ elements from $G$ has a nonempty subsequence which sums to zero. Then
$s(G)\leq\exp(G)(1+\ln\frac{|G|}{\exp(G)})$. ∎

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].

######  Theorem 2.5 (Rao).

There is a universal constant $c_{1}>1$ such that every family of more than
$(c_{1}p\log(pt))^{t}$ sets, each of cardinality $t$, must contain a _$p$
-sunflower_, defined as a family of $p$ distinct sets whose pairwise
intersections are identical. ∎

######  Theorem 2.6 (Frankl–Wilson).

Let $m(n,k,\overline{l})$ be the largest size of a collection $\mathcal{F}$ of
subsets of $\binom{[n]}{k}$ for which no two elements
$F,F^{\prime}\in\mathcal{F}$ have intersection size $l$. Then, if $k-l$ is a
prime power:

$\displaystyle m(n,k,\overline{l})$ $\displaystyle\leq\binom{n}{k-l-1}\,,$
$\displaystyle\text{ if }k\geq 2l+1\,;$ $\displaystyle m(n,k,\overline{l})$
$\displaystyle\leq\binom{n}{l}\binom{2k-l-1}{k}\Big{/}\binom{2k-l-1}{l}\,,$
$\displaystyle\text{ if }k\leq 2l+1\,.\hbox
to0.0pt{~{}~{}\qquad\qquad\qquad\qquad\qed\hss}$

###  2.3 Our Round Elimination Framework

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$.

######  Definition 2.7 (Homomorphism and shadowing).

A protocol homomorphism is a map $\varphi$ from a protocol $\Upsilon$ to a
protocol $\Pi$ such that (i) for any two nodes $u,v$ in $\varphi$, the node
$\varphi(u)$ is a child of $\varphi(v)$ iff $u$ is a child of $v$, and (ii)
$\varphi$ maps leaves of $\Upsilon$ to leaves of $\Pi$. We say that $\varphi$
is cost-preserving for each internal node $v$ of $\Upsilon$,
$\operatorname{cost}(v)=\operatorname{cost}(\varphi(v))$. We say that
$\Upsilon$ shadows $\Pi$ through $\varphi$ if $\varphi$ is injective, cost-
preserving, and maps the root of $\Upsilon$ to a child of the root of $\Pi$.
Notice that when this is the case, $\Upsilon$ is one round shorter than $\Pi$.

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.

Algorithm 1 Outline of protocol $\Pi^{(S_{1},\ldots,S_{m})}$

1:Lift our input $W\subseteq[m]$ to $Z:=\bigcup_{i\in W}S_{i}\subseteq[n]$
(this step is only conceptual).

2:Mimic $\Pi$ by simulating the queries it would have made to its input $Z$.
Emulate each such query by making the corresponding query to our own input
$W$. This is indeed possible using linear queries to $W$.

3:Suppose $\Pi$ wants to output $h$. If $h\in S_{i}$, then output that index
$i$ (which must be unique); otherwise, output an arbitrary index.

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

$\displaystyle
L=[\mathbf{s}_{1}~{}\mathbf{s}_{2}~{}\cdots~{}\mathbf{s}_{m}]\in R^{n\times
m}\,,$ (6)

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.

######  Lemma 2.8.

Suppose that $\Pi$ correctly solves $\textsc{elemx}_{n}$ on inputs in
$\mathcal{Z}\subseteq\\{0,1\\}^{n}$. Let $S_{1},\ldots,S_{m}\subseteq[n]$ be
pairwise disjoint and let $L$ be defined by eq. 6. Let $\rho$ be the root node
of $\Pi$ and, for $\mathbf{r}\in R^{d_{\rho}}$, let
$\mathcal{W}_{\mathbf{r}}:=\\{\mathbf{w}\in\\{0,1\\}^{m}:\,L\mathbf{w}\in\mathcal{Z}$
and $A_{\rho}L\mathbf{w}=\mathbf{r}\\}$. Then, there is a protocol $\Upsilon$
that shadows $\Pi$ and correctly solves $\textsc{elemx}_{m}$ on each input in
$\mathcal{W}_{\mathbf{r}}$.

###### Proof.

Using the above setup and terminology, construct
$\Pi^{\prime}:=\Pi^{(S_{1},\ldots,S_{m})}$ as in Algorithm 1. The given
conditions imply that on all inputs in $\mathcal{W}_{\mathbf{r}}$, the first
measurement of $\Pi^{\prime}$ is always $\mathbf{r}$ and thus leads an
execution of $\Pi^{\prime}$ to a particular child, $u$, of its root node.
Thus, we can shrink $\Pi^{\prime}$ to the subprotocol $\Upsilon$ rooted at
$u$. Notice that the bijection $\varphi$ is a cost-preserving protocol
homomorphism and so $\Upsilon$ shadows $\Pi$ through $\varphi|_{\Upsilon}$.

By construction, $\Upsilon$ on input $\mathbf{w}\in\mathcal{W}_{\mathbf{r}}$
simulates $\Pi$ on $\mathbf{z}:=L\mathbf{w}=\sum_{i\in W}\mathbf{s}_{i}$, an
input on which $\Pi$ correctly solves $\textsc{elemx}_{n}$. Therefore, if
$\Pi$ outputs $h$, then $h\in Z=\bigcup_{i\in W}S_{i}$. By the disjointness
guarantee, there exists a unique $i\in W$ for which $h\in S_{i}$. As
$\Upsilon$ reports precisely this $i$, it correctly solves
$\textsc{elemx}_{m}$ on $\mathbf{w}$. ∎

######  Definition 2.9 (Uniform family).

Fix a matrix $A\in R^{d\times n}$. An $A$-uniform family of size $m$ is a
collection of $m$ pairwise disjoint sets $S_{1},\ldots,S_{m}\subseteq[n]$ such
that $A\mathbf{s}_{1}=\cdots=A\mathbf{s}_{m}=\mathbf{r}$, for some vector
$\mathbf{r}\in R^{d}$.

##  3 Linear Queries Modulo 2

We begin our study of the element-extraction problem by considering
$\mathbb{Z}_{2}$-linear queries. As noted in Section 1.1, we shall later
generalize the results to $\mathbb{Z}_{q}$, but we feel it is worth seeing our
framework in action in the especially clean setting of $\mathbb{Z}_{2}$. We
begin by showing that the additional promise of odd cardinality on the input
set $Z$ is crucial, or else there is no interesting rounds-vs-queries tradeoff
to be had.

######  Proposition 3.1 (Restatement of Proposition 1.1).

$\operatorname{LQ}_{\mathbb{Z}_{2}}(\textsc{elemx}_{n})=n-1$.

###### Proof.

The upper bound is achieved by the trivial $1$-round LQP (i.e., a sketch) that
queries all but one of the individual bits of the input.

Now assume to the contrary that there is a $\mathbb{Z}_{2}$-LQP $\Pi$ with
$\operatorname{cost}(\Pi)=d\leq n-2$ that solves $\textsc{elemx}_{n}$. Let
$A\in\mathbb{Z}_{2}^{d\times n}$ be the matrix whose rows represent all
queries along the path $\Pi(\mathbf{0})$. Then $\dim\,\ker A\geq n-d\geq 2$,
whence there exist distinct nonzero vectors
$\mathbf{y},\mathbf{z}\in\mathbb{Z}_{2}^{n}$ such that
$A\mathbf{y}=A\mathbf{z}=\mathbf{0}$. Setting
$\mathbf{x}=\mathbf{y}+\mathbf{z}$, we also have $A\mathbf{x}=\mathbf{0}$.
Thus, the three nonzero inputs $\mathbf{x},\mathbf{y},\mathbf{z}$ lead to the
same leaf, namely $\ell(\Pi(\mathbf{0}))$, and produce the same output $i$,
say. By the correctness of $\Pi$, we have $x_{i}=y_{i}=z_{i}=1$, which
contradicts $\mathbf{x}=\mathbf{y}+\mathbf{z}$. ∎

Accordingly, for the rest of this section, we focus on the problem
$\textsc{elemx}^{(2)}_{n}$, as defined in eq. 3. We shall prove Theorem 1.3
using a round elimination technique. As discussed in Section 2, this round
elimination will be enabled by identifying a certain $A$-uniform family. The
next lemma, establishing a useful fact about matrices over $\mathbb{Z}_{2}$,
will provide us this family.

######  Lemma 3.2.

Every matrix $A\in\mathbb{Z}_{2}^{d\times n}$, admits an $A$-uniform family
$S_{1},\ldots,S_{m}$ of size $m\geq{\lceil{n/(d+1)}\rceil}$ such that each
cardinality $|S_{i}|$ is odd.

###### Proof.

Let $\mathbf{b}_{1},\ldots,\mathbf{b}_{n}$ be the (nonzero) column vectors of
the matrix

$B:=\left[\begin{array}[]{c}A\\\
\mathbf{1}^{\mathsf{T}}\end{array}\right]\in\mathbb{Z}_{2}^{(d+1)\times n}$

formed by appending the all-ones row to $A$. For each $Q\subseteq[n]$, let
$B_{Q}$ be the collection of column vectors $\\{\mathbf{b}_{i}:\,i\in Q\\}$
and let ${\langle{B_{Q}}\rangle}$ be the linear subspace of
$\mathbb{Z}_{2}^{d+1}$ spanned by the vectors in $B_{Q}$.

Partition $[n]$ into nonempty disjoint sets $T_{1},\ldots,T_{m}$ iteratively,
as follows. For each $i$, let $T_{i}$ be a maximal subset of
$[n]\smallsetminus\bigcup_{j=1}^{i-1}T_{j}$ such that the vectors in
$B_{T_{i}}$ are linearly independent. Since these vectors live in
$\mathbb{Z}_{2}^{d+1}$, it follows that $|T_{i}|\leq d+1$. We stop when
$\bigcup_{j=1}^{m}T_{m}=[n]$, implying $m\geq{\lceil{n/(d+1)}\rceil}$.

We claim that, for each $i\in\\{2,\ldots,m\\}$, we have
${\langle{B_{T_{i-1}}}\rangle}\supseteq{\langle{B_{T_{i}}}\rangle}$. Indeed,
if there exists an element
$\mathbf{x}\in{\langle{B_{T_{i}}}\rangle}\smallsetminus{\langle{B_{T_{i-1}}}\rangle}$,
then there is a set $Q\subseteq T_{i}$ for which $\mathbf{x}=\sum_{h\in
Q}\mathbf{b}_{j}$. Since ${\langle{B_{T_{i-1}}}\rangle}$ is closed under
linear combinations and does not contain $\mathbf{x}$, there exists $h\in Q$
with $\mathbf{b}_{h}\notin{\langle{B_{T_{i-1}}}\rangle}$. By construction,
$h\notin\bigcup_{j=1}^{i-2}T_{j}$, so $h$ was not included in $T_{i-1}$
despite being available. This contradicts the maximality of $T_{i-1}$.

Let $k$ be an index in $T_{m}$. Then
$\mathbf{b}_{k}\in{\langle{B_{T_{m}}}\rangle}\subseteq{\langle{B_{T_{m-1}}}\rangle}\subseteq\cdots\subseteq{\langle{B_{T_{1}}}\rangle}$,
so there must exist subsets $S_{1},\ldots,S_{m}$ of $T_{1},\ldots,T_{m}$ for
which $B\mathbf{s}_{i}=\mathbf{b}_{k}$. The sets $\\{S_{i}\\}_{i=1}^{m}$ are
pairwise disjoint because the sets $\\{T_{i}\\}_{i=1}^{m}$ are. Let
$\mathbf{r}$ be the first $d$ coordinates of $\mathbf{b}_{k}$; then for all
$i\in[m]$, $A\mathbf{s}_{i}=\mathbf{r}$. Therefore, $\\{S_{i}\\}_{i=1}^{m}$ is
$A$-uniform. Finally, since the last coordinate of $\mathbf{b}_{k}$ is $1$ and
the last row of $B$ is $\mathbf{1}^{\mathsf{T}}$, for each $i\in[m]$,
$\mathbf{1}^{\mathsf{T}}\mathbf{s}_{i}=1$, so $|S_{i}|$ is odd. ∎

######  Lemma 3.3 (Round elimination lemma).

Let $\Pi$ be a deterministic $k$-round $\mathbb{Z}_{2}$-LQP for
$\textsc{elemx}^{(2)}_{n}$, where $k\geq 1$. Then there exists a deterministic
$(k-1)$-round $\mathbb{Z}_{2}$-LQP $\Upsilon$ for $\textsc{elemx}^{(2)}_{m}$,
such that

  1. (3.3.1)

$\Upsilon$ shadows $\Pi$ through a (cost-preserving, injective) protocol
homomorphism $\varphi_{\Upsilon}\colon\Upsilon\to\Pi$;

  2. (3.3.2)

$m\geq{\lceil{n/(d+1)}\rceil}$, where $d$ is the cost of the root of $\Pi$.

###### Proof.

Let $A\in\mathbb{Z}_{2}^{d\times n}$ be the label of the root of $\Pi$. Let
$S_{1},\ldots,S_{m}$ be an $A$-uniform family of size
$m\geq{\lceil{n/(d+1)}\rceil}$ with each $|S_{i}|$ odd, as guaranteed by Lemma
3.2. Let the lifting matrix $L$ be as given by eq. 6 and let
$\mathbf{r}=A\mathbf{s}_{1}$. We know that $\Pi$ correctly solves
$\textsc{elemx}^{(2)}_{n}$ on inputs in $\mathcal{Z}:=\\{Z\subseteq[n]:\,|Z|$
odd$\\}$. Invoking Lemma 2.8, we obtain a $(k-1)$-round $\mathbb{Z}_{2}$-LQP
$\Upsilon$ that shadows $\Pi$ as required.

It remains to show that $\Upsilon$ solves $\textsc{elemx}^{(2)}_{m}$. The
guarantee of Lemma 2.8 is that $\Upsilon$ correctly solves
$\textsc{elemx}_{m}$ on the input set $\mathcal{W}_{\mathbf{r}}$ defined
there. Thus, it suffices to show that if an input $W\subseteq[m]$ satisfies
the promise of $\textsc{elemx}^{(2)}_{m}$—i.e., $|W|$ is odd—then
$W\in\mathcal{W}_{\mathbf{r}}$. We reason as follows:

$\displaystyle|W|\text{ odd}$
$\displaystyle\implies|L\mathbf{w}|=\left|\sum_{i\in
W}\mathbf{s}_{i}\right|\equiv 1{\@displayfalse\pmod{2}}$
$\displaystyle\lhd\text{ each $|S_{i}|$ is odd}$ $\displaystyle\implies
L\mathbf{w}\in\mathcal{Z}\,;$ $\displaystyle\lhd\text{ definition of
$\mathcal{Z}$}$ and $\displaystyle|W|\text{ odd}$ $\displaystyle\implies
AL\mathbf{w}=A\sum_{i\in W}\mathbf{s}_{i}=|W|\cdot
A\mathbf{s}_{1}=|W|\cdot\mathbf{r}=\mathbf{r}\,.$ $\displaystyle\lhd\text{
definition of $A$-uniformity}$

This completes the proof, by definition of $\mathcal{W}_{\mathbf{r}}$. ∎

The next step of the proof is to repeatedly invoke the above round elimination
lemma and carefully control parameters. To perform a sharp analysis, we
introduce the following concept.

######  Definition 3.4.

A division sequence for $n$ is a finite sequence of positive integers
$d_{1}\ldots d_{j}$ for which

$\displaystyle\left\lceil\cdots\left\lceil\left\lceil
n\cdot\frac{1}{d_{1}+1}\right\rceil\frac{1}{d_{1}+1}\right\rceil\cdots\frac{1}{d_{j}+1}\right\rceil=1\,.$
(7)

######  Lemma 3.5.

Let $d_{1},\ldots,d_{j}$ be a division sequence for $n$ minimizing
$\sum_{h=1}^{j}d_{h}$. Then

$\displaystyle jn^{1/j}-j\leq\sum_{h=1}^{j}d_{h}\leq j\lceil
n^{1/j}\rceil-j\,.$

###### Proof.

For the upper bound, let $d_{1}=\ldots=d_{j}=\lceil n^{1/j}\rceil-1$. For the
lower bound, remove the ceiling operations in eq. 7 to get

$\displaystyle\frac{n}{\prod_{h=1}^{j}(d_{h}+1)}\leq 1\,,$
$\displaystyle\qquad\text{which implies}\quad
n^{1/j}\leq\smash{\left(\prod_{h=1}^{j}(d_{h}+1)\right)^{1/j}}\,.$

By the AM-GM inequality,

$\sum_{h=1}^{j}d_{h}=j\left(\frac{1}{j}\sum_{h=1}^{j}(d_{h}+1)-1\right)\geq\smash{j\left(\left(\prod_{h=1}^{j}(d_{h}+1)\right)^{1/j}-1\right)}\geq
j(n^{1/j}-1)\,.\qed$

This brings us to the main result of this section: a rounds-vs-queries
tradeoff.

######  Theorem 3.6 (Restatement of Theorem 1.3).

$\operatorname{LQ}_{\mathbb{Z}_{2}}^{k}(\textsc{elemx}^{(2)}_{n})\geq
k(n^{1/k}-1)$.

###### Proof.

Suppose that $\Pi$ is a deterministic $k$-round $\mathbb{Z}_{2}$-LQP for
$\textsc{elemx}^{(2)}_{n}$. Repeatedly applying Lemma 3.3, we obtain a
sequence of protocols $\Pi=\Pi_{1},\Pi_{2},\ldots,\Pi_{j+1}$, which solve
$\textsc{elemx}^{(2)}$ on progressively smaller input sizes, until $\Pi_{j+1}$
is a degenerate depth-0 protocol (in which no queries occur).

Let $d_{i}$ be the cost of the root $\rho_{i}$ of $\Pi_{i}$, for $1\leq i\leq
j$. As Property (3.3.1) gives protocol homomorphisms
$\varphi_{\Pi_{i+1}}:\Pi_{i+1}\to\Pi_{i}$, we find the the roots of each
$\Pi_{i}$ correspond to nodes
$u_{i}=(\varphi_{\Pi_{2}}\circ\cdots\circ\varphi_{\Pi_{i}})(\rho_{i})$ in
$\Pi$. In fact, the vertices $u_{1},u_{1},\ldots,u_{j+1}$ form a path from the
root $\rho=u_{1}$ of $\Pi$ to the leaf $u_{j+1}$. The inputs of $\Pi_{j+1}$
lift to inputs of $\Pi$ which reach $u_{j+1}$. Lower bounding the query cost
of $\Pi$ using this branch gives

$\displaystyle\operatorname{cost}(\Pi)\geq\sum_{i=1}^{j}\operatorname{cost}(u_{i})=\sum_{i=1}^{j}d_{i}\,.$
(8)

Using property (3.3.2) repeatedly, $\Pi_{j+1}$ must solve
$\textsc{elemx}^{(2)}_{m}$, for some integer

$\displaystyle m\geq\left\lceil\cdots\left\lceil\left\lceil
n\cdot\frac{1}{d_{1}+1}\right\rceil\frac{1}{d_{2}+1}\right\rceil\cdots\frac{1}{d_{j}+1}\right\rceil\,.$

However, as $\Pi_{j+1}$ solves $\textsc{elemx}^{(2)}_{m}$ without performing
any queries, there must be a fixed index which is a valid output for all
inputs $Z\in 2^{[m]}$ of odd size. This is only possible when $m=1$; for any
larger $m$, the inputs $Z=\\{1\\}$ and $Z^{\prime}=\\{2\\}$ must produce
different outputs.

Therefore, the integers $d_{1},\ldots,d_{j}$ form a division sequence for $n$.
Applying Lemma 3.5 to eq. 8,

$\displaystyle\operatorname{cost}(\Pi)\geq\sum_{i=1}^{j}d_{i}\geq
jn^{1/j}-j\geq k(n^{1/k}-1)\,,$

where the last inequality follows from the fact that
$\frac{d}{dz}\left[z(n^{1/z}-1)\right]\leq 0$ for all $z\geq 0$. ∎

##  4 Linear Queries Modulo q

First, we use Theorem 2.4 to show that $\textsc{elemx}_{n}$ is hard for
$\mathbb{Z}_{q}$-LQPs.

######  Proposition 4.1 (Restatement of Proposition 1.2).

For every $q\geq 3$, we have
$\operatorname{LQ}_{\mathbb{Z}_{q}}(\textsc{elemx}_{n})\geq n/(2q\ln q)$.

###### Proof.

This is proven with the same strategy as for Proposition 1.1. Assume for sake
of contradiction that $\operatorname{cost}(\Pi)\leq\frac{n}{2q\ln q}$. Let
$\nu$ be the leaf $\ell(\Pi(\mathbf{0}))$. Let $A\in\mathbb{Z}_{q}^{d\times
n}$ be the matrix containing all queries along the path from the root of $\Pi$
to $\nu$.

By Theorem 2.4, since the group $\mathbb{Z}_{q}^{d}$ has order $q^{d}$, and
exponent $q$, any sequence of $D\leq q\left(1+\ln(\frac{q^{d}}{q})\right)$
elements in $\mathbb{Z}_{q}^{d}$ has a nontrivial subsequence summing to
$\mathbf{0}$. As $q\geq 3$, $dq\ln q\geq D$. Thus, since $n\geq 2dq\ln q$,
picking disjoint subsets $I$ and $J$ of sizes $dq\ln q$ each, and applying the
theorem implies there exist disjoint nonempty subsets $Z_{1}$ and $Z_{2}$ of
$[n]$ for which the corresponding columns of $A$ sum to $\mathbf{0}$. In other
words, $\Pi$ reaches the same leaf given $\mathbf{z}_{1}$ and
$\mathbf{z}_{2}$, but the leaf cannot be assigned an output consistent with
both. ∎

A similar strategy proves a lemma analogous to Lemma 3.2:

######  Lemma 4.2.

Every matrix $A\in\mathbb{Z}_{q}^{d\times n}$, admits an $A$-uniform family
$S_{1},\ldots,S_{m}$ where

  1. (4.2.1)

$\displaystyle m\geq\frac{n}{(d+1)q\ln q}-1$, and

  2. (4.2.2)

each cardinality $|S_{i}|\equiv-1\pmod{q}$.

###### Proof.

To be able to enforce constraints on the values $|S_{i}|$, we define
$B:=\left[\mathbf{1}\mid
A^{\mathsf{T}}\right]^{\mathsf{T}}\in\mathbb{Z}_{q}^{(d+1)\times n}$, and let
$\mathbf{b}_{1},\ldots,\mathbf{b}_{n}$ be its column vectors. We partition the
columns of the matrix $B$ into disjoint subsets $D_{1},\ldots,D_{k}$ of $[n]$
by the following iterative procedure. In the procedure, let $P$ be the set of
indices of $[n]$ not yet chosen. Each set $D_{i}$ starts out as $\varnothing$;
then beginning with $i=1$, each set $D_{i}$ is expanded by picking an index
$j$ from $P$ for which no subset $H\subseteq(D_{i}\cup\\{j\\})$ has the
property that $\sum_{h\in H}\mathbf{b}_{h}=\mathbf{0}$; adding $j$ to $D_{i}$
and removing $j$ from $P$; until no more such indices can be found. When
$D_{i}$ is done, start filling $D_{i+1}$, etc.

When $q=2$, each $D_{i}$ corresponds to a basis of a subspace of
$\mathbb{Z}_{2}^{d+1}$, so $|D_{i}|\leq d+1<(d+1)2\ln 2$. For $q\geq 3$, we
apply Theorem 2.4, using the fact that the group $\mathbb{Z}_{q}^{d+1}$ has
order $q^{d+1}$ and exponent $q$. The maximum possible size of each set
$D_{i}$ is then $\leq q\left(1+\ln(\frac{q^{d+1}}{q})\right)-1$. The upper
bound $(d+1)q\ln q$ also holds here. Consequently, the number $k$ of sets
formed is $\geq\frac{n}{(d+1)q\ln q}$. Pick some $t\in D_{k}$; for any $i<k$,
since $t$ was not picked when $D_{i}$ was constructed, it must be the case
that there is a subset $S_{i}\subseteq D_{i}$ for which $\sum_{h\in
S_{i}}\mathbf{b}_{h}+\mathbf{b}_{t}=\mathbf{0}$. This implies
$B\mathbf{s}_{i}=\sum_{h\in S_{i}}\mathbf{b}_{h}=-\mathbf{b}_{t}$. Since the
first row of $B$ is $\mathbf{1}$, we have $|S_{i}|\equiv\sum_{h\in
S_{i}}1\equiv-1\pmod{q}$, so all the sets $S_{i}$ have size $-1\pmod{q}$. Let
$\mathbf{r}$ be the last $d$ entries of $-\mathbf{b}_{t}$; then for all $i$,
$B\mathbf{s}_{i}=\mathbf{r}$. There are $m=k-1\geq\frac{n}{(d+1)q\ln q}-1$
sets in total. ∎

Compared to $\textsc{elemx}^{(2)}$, there is a slight weakening of the main
round elimination lemma, which is a direct consequence of the weakened Lemma
4.2. Instead of directly lower bounding the cost of
$\textsc{elemx}^{(q)}_{n}$, we prove separate lower bounds for each
$\textsc{elemx}^{(q,h)}_{n}$, for all $h\in\\{1,\ldots,q-1\\}$, and take their
maximum. The search problem $\textsc{elemx}^{(q,h)}_{n}$ is
$\textsc{elemx}_{n}$ with the additional promise that the input set $Z$ has
size $\equiv h\pmod{q}$.

######  Lemma 4.3 (Round elimination lemma).

Let $\Pi$ be a $k$-round $\mathbb{Z}_{q}$-LQP for
$\textsc{elemx}^{(q,h)}_{n}$, where $k\geq 1$ and $h\in\\{1,\ldots,q-1\\}$.
Then there exists a $(k-1)$-round $\mathbb{Z}_{q}$-LQP $\Upsilon$ for
$\textsc{elemx}_{m}^{(q,-h)}$, such that

  1. (4.3.1)

$\Upsilon$ shadows $\Pi$ through a protocol homomorphism
$\varphi_{\Upsilon}\colon\Upsilon\to\Pi$;

  2. (4.3.2)

$\displaystyle m\geq\frac{n}{(d+1)q\ln q}-1$, where $d$ is the cost of the
root of $\Pi$.

###### Proof.

Let $A\in\mathbb{Z}_{q}^{d\times n}$ be the label of the root of $\Pi$. Lemma
4.2 guarantees that there exists an $A$-uniform family of size $m$, where $m$
satisfies property (4.3.2), and
$A\mathbf{s}_{1}=\ldots=A\mathbf{s}_{m}=\mathbf{x}$, and
$|S_{1}|\equiv\ldots\equiv|S_{m}|\equiv-1\pmod{q}$. Let $L$ be the lifting
matrix from eq. 6, and $\mathbf{r}=-h\mathbf{x}$. Applying Lemma 2.8 to $\Pi$,
$L$ and $\mathbf{r}$, we obtain a $(k-1)$-round $\mathbb{Z}_{q}$-LQP
$\Upsilon$ that shadows $\Pi$, and solves $\textsc{elemx}_{m}$ on all inputs
$W\subseteq[m]$ for which $AL\mathbf{w}=\mathbf{r}$ and $|L\mathbf{w}|\equiv
h\pmod{q}$. If $W$ fulfills the promise of $\textsc{elemx}^{(q,-h)}_{n}$, that
$|W|\equiv-h\pmod{q}$, then:

$\displaystyle|L\mathbf{w}|$ $\displaystyle=\left|\bigcup_{i\in
W}S_{i}\right|=\sum_{i\in W}|S_{i}|=|W|\cdot(-1)=h\pmod{q}\,,$ $\displaystyle
AL\mathbf{w}$ $\displaystyle=\sum_{i\in
W}A\mathbf{s}_{i}=|W|\mathbf{x}=-h\mathbf{x}=\mathbf{r}\,,$

which proves that $\Upsilon$ is correct on $W$. ∎

This brings us to the main result of this section, which essentially
generalizes the modulo-$2$ result from the previous section.

######  Theorem 4.4 (Restatement of Theorem 1.4).

For each $q\geq 2$, we have

$\operatorname{LQ}_{\mathbb{Z}_{q}}^{k}(\textsc{elemx}^{(q)}_{n})\geq\frac{1}{3.67q^{1+1/k}\ln^{2}q}k(n^{1/k}-1)\,.$

###### Proof.

Suppose that $\Pi$ is a deterministic $\mathbb{Z}_{q}$-LQP for
$\textsc{elemx}^{(q,h)}_{n}$. Repeatedly applying Lemma 4.3, we construct a
sequence of protocols $\Pi=\Pi_{1},\Pi_{2},\ldots,\Pi_{j+1}$, which
respectively solve $\textsc{elemx}^{(q,h)}$, $\textsc{elemx}_{n}^{(q,-h)}$,
$\textsc{elemx}^{(q,h)},\ldots\,$ on progressively smaller input sizes, until
$\Pi_{j+1}$ is a degenerate depth-0 protocol (in which no queries occur), for
$\textsc{elemx}_{n}^{(q,(-1)^{j}h)}$. As in Section 3, the roots $\rho_{i}$ of
the protocols $\Pi_{i}$, $1\leq i\leq j$, which have cost $d_{i}$, correspond
to a branch of $\Pi$ formed by corresponding nodes $u_{i}$ and ending at a
leaf corresponding to the root of $\Pi_{j+1}$. Then

$\displaystyle\operatorname{cost}(\Pi)\geq\sum_{i=1}^{j}\operatorname{cost}(u_{i})=\sum_{i=1}^{j}d_{i}\,.$
(9)

Let $\delta_{i}:=(d_{i}+1)q\ln q$. By Lemma 4.3, $\Pi_{i}$ solves
$\textsc{elemx}^{(q,(-1)^{i-1}h)}_{m_{i}}$, where $m_{1}=n$, and:

$\displaystyle m_{i+1}$ $\displaystyle\geq\frac{m_{i}}{(d_{i}+1)q\ln
q}-1=\frac{m_{i}-\delta_{i}}{\delta_{i}}\,.$ (10)

As $\Pi_{j+1}$ solves $\textsc{elemx}^{(q,(-1)^{j}h)}_{m_{i}}$ without any
queries, the problem must be trivial, necessitating $m_{j+1}\leq q$. Combining
eq. 10 for $i$ between $1$ and $j$ and rearranging:

$\displaystyle
q\geq\frac{n-\sum_{i=1}^{j}{\prod_{\ell=1}^{i}{\delta_{\ell}}}}{\prod_{\ell=1}^{j}{\delta_{\ell}}}\quad\implies\quad
n$ $\displaystyle\leq
q\prod_{\ell=1}^{j}{\delta_{\ell}}+\sum_{i=1}^{j}{\prod_{\ell=1}^{i}{\delta_{\ell}}}\leq(q+j)\prod_{\ell=1}^{j}{\delta_{\ell}}\,.$

Further rearrangement lets us use AM-GM and an inequality derived from
$(q+j)q^{j}\leq(q+1)^{j}q$:

$\displaystyle\left(\frac{1}{j}\sum_{i=1}^{j}{\delta_{i}}\right)\geq\left(\prod_{i=1}^{j}{\delta_{i}}\right)^{1/j}\geq\left(\frac{n}{q+j}\right)^{1/j}\geq\frac{q}{q+1}\left(\frac{n}{q}\right)^{1/j}\,.$
(11)

We can now lower bound the query cost of $\Pi$:

$\displaystyle\operatorname{cost}(\Pi)$
$\displaystyle\geq\sum_{i=1}^{j}(d_{i}+1)-j=\frac{1}{q\ln
q}\sum_{i=1}^{j}\delta_{i}-j$ $\displaystyle\lhd\text{ by
\lx@cref{creftype~refnum}{eq:zq-lincost-sum}}$ $\displaystyle\geq
j\left(\frac{1}{(q+1)\ln q}\left(\frac{n}{q}\right)^{1/j}-1\right)$
$\displaystyle\lhd\text{ by \lx@cref{creftype~refnum}{eq:zq-lincost-amgm}}$
$\displaystyle\geq k\left(\frac{1}{(q+1)\ln
q}\left(\frac{n}{q}\right)^{1/k}-1\right)\,.$ $\displaystyle\lhd\text{ since
$\frac{d}{ds}[s(r^{1/s}-1)]\leq 0$}$ (12)

This lower bound becomes negative for sufficiently large $k$. To obtain a
bound that remains positive for all $k$, we combine it with an unconditional
lower bound. First, we note that eq. 12 also applies to protocols solving
$\textsc{elemx}^{(q)}_{n}$, since $\textsc{elemx}^{(q,h)}_{n}$ was an easier
case. For $\textsc{elemx}^{(q)}_{n}$, the set of possible transcripts of any
protocol $\Psi$ forms a $q$-ary prefix code of maximum length $d$. If
$q^{d}<n$, then by the pigeonhole principle $\Psi$ must treat identically some
pair of $\\{1\\},\\{2\\},\ldots,\\{n\\}$, which is a contradiction; thus
$\operatorname{cost}(\Pi)\geq\ln n/\ln q$. Combining this lower bound with eq.
12 and applying Lemma 8.1, we obtain

$\operatorname{cost}(\Pi)\geq\max\left\\{\frac{\ln n}{\ln
q},\,k\left(\frac{1}{q^{1/k}(q+1)\ln
q}n^{1/k}-1\right)\right\\}\geq\frac{k(n^{1/k}-1)}{q^{1/k}(q+1)(\ln q+1)\ln
q}\geq\frac{k(n^{1/k}-1)}{3.67q^{1+1/k}\ln^{2}q}\,.\qed$

##  5 Linear Queries Over the Integers

For $\mathbb{Z}$-LQPs, our main result is a 2-round lower bound for
$\textsc{elemx}_{n}$. We require a careful accounting of the query cost of a
protocol, to adjust for the fact that the (bit) size of the query results
depends on the maximum entry value in a given query matrix. This motivates the
following definition and observation.

######  Definition 5.1.

A $\mathbb{Z}$-LQP is said to be $M$-bounded if each linear measurement can
take at most $M$ distinct values. In particular, if the inputs to a
$\mathbb{Z}_{[-B,B]}$-LQP $\Pi$ lie in $\\{0,1\\}^{n}$, then $\Pi$ is
$(Bn+1)$-bounded.

Recall the problem $\textsc{elemx}^{1/4}_{n}$ defined in eq. 5. For $n$
divisible by $4$, this is simply $\textsc{elemx}_{n}$ under the additional
promise that $|Z|=n/4$. We first prove a $1$-round lower bound for this
problem, under a slight additional assumption on $n$.

######  Lemma 5.2.

Let $n=4r$ where $r$ is a prime power. If $\Pi$ is an $M$-bounded one-round
protocol for $\textsc{elemx}^{1/4}_{n}$,

$\displaystyle\operatorname{cost}(\Pi)\geq 0.14\frac{n}{\log M}\,.$

###### Proof.

Let $d=\operatorname{cost}(\Pi)$ and let $A\in\mathbb{Z}^{d\times n}$ be the
query performed by $\Pi$. We first consider what $\Pi$ does on inputs of
cardinality $n/2$, even though such inputs lie outside the promise region of
$\textsc{elemx}^{1/4}_{n}$. Soon, we shall see how this helps.

Since $\Pi$ is $M$-bounded, the mapping $\mathbf{z}\mapsto A\mathbf{z}$ from
domain $\binom{[n]}{n/2}$ to $\mathbb{Z}^{d}$ has no more than $M^{d}$
possible output values. By the pigeonhole principle, there exists a vector
$\mathbf{w}\in\mathbb{Z}^{d}$ for which

$\displaystyle\mathcal{F}_{\mathbf{w}}:=\left\\{\mathbf{z}\in\binom{[n]}{n/2}:\,A\mathbf{z}=\mathbf{w}\right\\}\qquad\text{
has }\qquad|\mathcal{F}_{\mathbf{w}}|\geq\binom{n}{n/2}M^{-d}\,.$

If there exist two distinct vectors
$\mathbf{x},\mathbf{y}\in\mathcal{F}_{\mathbf{w}}$ such that
$|\mathbf{x}\cap\mathbf{y}|=n/4$, then we can construct two disjoint vectors
which $\Pi$ can not distinguish, and thus cannot give a correct answer to
$\textsc{elemx}^{1/4}_{m}$ in both cases. Specifically,
$|\mathbf{x}\smallsetminus\mathbf{y}|=|\mathbf{y}\smallsetminus\mathbf{x}|=n/4$
and

$\displaystyle
A(\mathbf{x}\smallsetminus\mathbf{y})=A\mathbf{x}-A(\mathbf{x}\cap\mathbf{y})=\mathbf{w}-A(\mathbf{x}\cap\mathbf{y})=A\mathbf{y}-A(\mathbf{x}\cap\mathbf{y})=A(\mathbf{y}\smallsetminus\mathbf{x})\,.$

By Theorem 2.6, if there does not exist such a pair $\mathbf{x},\mathbf{y}$,
then we have an upper bound on $|\mathcal{F}|$, and can derive

$\displaystyle\binom{n}{n/2}M^{-d}$
$\displaystyle\leq|\mathcal{F}|\leq\binom{n}{n/4-1}\,.$

Therefore, $\binom{n}{n/2}M^{-d}\leq\binom{n}{n/4}$ and we obtain

$d\geq\frac{\log{\binom{n}{n/2}}-\log{\binom{n}{n/4}}}{\log
M}\geq\frac{\log{\binom{4}{2}}-\log\binom{4}{1}}{4}\frac{n}{\log M}\geq
0.14\frac{n}{\log M}\,.\qed$

It should be noted that without the promise that $|Z|=n/4$, a one-round lower
bound would follow very easily. By a standard “decoding” argument, a one-round
protocol for elemx can be used to recover the entire unknown input
$\mathbf{z}$. For completeness, we give the easy proof below. The reason we
needed the much more complicated argument in Lemma 5.2 above is that the
promise in $\textsc{elemx}^{1/4}_{n}$ prevents us from performing such a
decoding.

######  Proposition 5.3 (Essentially a restatement of Proposition 1.5).

If $\Pi$ is an $M$-bounded one-round protocol for $\textsc{elemx}_{n}$, then
$\operatorname{cost}(\Pi)\geq n/\log M-1$.

###### Proof.

Modify $\Pi$ to add the query $\mathbf{1}^{\mathsf{T}}$, which reports $|Z|$;
this increases $\operatorname{cost}(\Pi)$ by one. Let
$A\in\mathbb{Z}^{(d+1)\times n}$ be the modified query matrix. Since $\Pi$ is
correct, $A\mathbf{z}$ determines an index $i_{1}\in Z$. Let
$\mathbf{e}_{i_{1}}$ be the indicator vector for $i_{1}$; since we know
$\mathbf{e}_{i_{1}}$, we can compute $A(\mathbf{z}-\mathbf{e}_{i_{1}})$
without making another query; this is enough to find an index $i_{2}\in
Z\smallsetminus\\{i_{1}\\}$. Repeating this $|Z|$ times, we can reconstruct
$Z$ from $A\mathbf{z}$ alone. (This works for all $Z\neq\varnothing$; since we
query $\mathbf{1}^{\mathsf{T}}$, we can also detect when $|Z|=0$.) By the
pigeonhole principle, the number of possible values of $A\mathbf{z}$ must be
at least the number of valid inputs, so $M^{d+1}\geq 2^{n}$, which implies
$d\geq n/\log M-1$. ∎

For our round elimination argument, we require the following claim, similar to
Lemma 3.2 and Lemma 4.2. Even though the claim looks similar, the round
elimination argument will be subtly different from its $\mathbb{Z}_{2}$ and
$\mathbb{Z}_{q}$ predecessors.

######  Claim 5.4.

Every matrix $A\in\mathbb{Z}^{d\times n}$ admits an $A$-uniform family
$S_{1},\ldots,S_{m}$ of size $m\geq n/(c_{0}d\log n\log M)-1$, for some
absolute constant $c_{0}$.

###### Proof.

Put $t={\lceil{d\log M}\rceil}$. Since $\Pi$ is $M$-bounded, the mapping
$\mathbf{x}\mapsto A\mathbf{x}$ sends the vectors in
$\\{\mathbf{x}\in\\{0,1\\}^{n}:\,|\mathbf{x}|=t\\}$ to vectors in
$\mathbb{Z}^{d}$ where each entry comes from a set of cardinality $M$. By the
pigeonhole principle, there exists a vector
$\mathbf{\tilde{r}}\in\mathbb{Z}^{d}$ such that

$\displaystyle\mathcal{F}:=\\{\mathbf{x}\in\\{0,1\\}^{n}:\,|\mathbf{x}|=t\text{
and }A\mathbf{x}=\mathbf{\tilde{r}}\\}\text{~{}~{}has
cardinality~{}~{}}|\mathcal{F}|\geq\dbinom{n}{t}M^{-d}\,.$ (13)

We claim that $\mathcal{F}$ contains an $m$-sunflower for some integer $m$.
Indeed, take $m$ to be the largest integer satisfying

$\displaystyle mt\log n<\frac{n}{2c_{1}}\,,\qquad\text{ which ensures that
}\qquad m\geq\frac{n}{c_{0}d\log n\log M}-1\,.$ (14)

This satisfies the claimed bound upon taking $c_{0}=2c_{1}$ (say). Continuing
from eq. 13,

$\displaystyle|\mathcal{F}|$
$\displaystyle\geq\left(\frac{n}{t}\right)^{t}M^{-d}$ $\displaystyle\lhd\text{
standard estimate}$ $\displaystyle\geq\left(\frac{n}{2t}\right)^{t}$
$\displaystyle\lhd\text{ definition of $t$}$ $\displaystyle\geq(c_{1}m\log
n)^{t}$ $\displaystyle\lhd\text{ by
\lx@cref{creftype~refnum}{eq:m-constraint}}$
$\displaystyle\geq(c_{1}m\log(mt))^{t}\,,$ $\displaystyle\lhd\text{ by
\lx@cref{creftype~refnum}{eq:m-constraint}, again}$

whence the required sunflower exists, by Theorem 2.5.

Let $\widetilde{S}_{1},\ldots,\widetilde{S}_{m}$ be sets constituting such an
$m$-sunflower and let $V=\bigcap_{i=1}^{m}\widetilde{S}_{i}$ be the common
pairwise intersection. Define $S_{i}=\widetilde{S}_{i}\smallsetminus V$, for
each $i\in[m]$. We then have
$A\mathbf{s}_{i}=A(\mathbf{\tilde{s}}_{i}-\mathbf{v})=\mathbf{\tilde{r}}-A\mathbf{v}$
for each $i$, whence $S_{1},\ldots,S_{m}$ is an $A$-uniform family. ∎

######  Lemma 5.5 (Round elimination lemma).

Let $\Pi$ be a $k$-round $M$-bounded $\mathbb{Z}$-LQP for
$\textsc{elemx}_{n}$, where $k\geq 1$ and $n$ is an integer. Then there exists
a $(k-1)$-round $M$-bounded $\mathbb{Z}$-LQP $\Upsilon$ for
$\textsc{elemx}^{1/4}_{m}$, such that

  1. (5.5.1)

$\Upsilon$ shadows $\Pi$ through a homomorphism
$\varphi_{\Upsilon}\colon\Upsilon\to\Pi$;

  2. (5.5.2)

$m/4$ is a prime number and

$\displaystyle m\geq\frac{n}{2c_{0}d\log n\log M}-2\,,$

where $d$ is the cost of the root of $\Pi$, and $c_{0}$ the constant from 5.4.

###### Proof.

Let $A\in\mathbb{Z}^{d\times n}$ be the label of the root of $\Pi$. By 5.4,
there is an $A$-uniform family $S_{1},\ldots,S_{m^{\prime}}$ of size
$m^{\prime}$. By Bertrand’s postulate, there exists a prime number $p$ between
between $m^{\prime}/8$ and $m^{\prime}/4$; let $m=4p$. Let
$\mathbf{x}=A\mathbf{s}_{1}$, $\mathbf{r}=(m/4)\mathbf{x}$ and let $L$ be the
lifting matrix defined from $\\{S_{i}\\}_{i=1}^{m}$ according to eq. 6. Using
Lemma 2.8 on $\Pi$, $L$, and $\mathbf{r}$, we obtain a $(k-1)$-round
$\mathbb{Z}$-LQP $\Upsilon$ that shadows $\Pi$, and solves
$\textsc{elemx}_{m}$ on all inputs $W\subseteq[m]$ for which
$L\mathbf{w}\neq\mathbf{0}$ and $AL\mathbf{w}=\mathbf{r}$. While the queries
performed by $\Upsilon$ may have larger coefficients than those of $\Pi$, the
construction of $\Upsilon$ described in Section 2.3 only restricts the
possible results of each individual linear measurement performed, so
$\Upsilon$ is still $M$-bounded. Finally, if $|W|=m/4$, then since $L$ has
full rank, $L\mathbf{w}\neq\mathbf{0}$; and furthermore

$\displaystyle AL\mathbf{w}=\sum_{i\in
W}A\mathbf{s}_{i}=|W|\mathbf{x}=\frac{m}{4}\mathbf{x}=\mathbf{r}\,.$

This implies that $\Upsilon$ gives the correct output for $W\subseteq[m]$
fulfilling the promise of $\textsc{elemx}^{1/4}_{m}$. ∎

The preceding round elimination lemma has a key limitation: it requires a
protocol for $\textsc{elemx}_{n}$ to create one for
$\textsc{elemx}^{1/4}_{m}$. Because of this, it is not possible to apply the
lemma to its own output, and thereby obtain a $k$-round lower bound. Say we
were to try, and $A$ were the matrix at the root of the protocol $\Pi$ for
$\textsc{elemx}^{1/4}_{n}$. Then if $A$ contained an all-ones row, 5.4 might
produce an $A$-uniform family with all set sizes $|S_{i}|$ equal to some
constant $b$ which is not a factor of $n/4$. Then lifting inputs $W$ of size
$m/4$ to inputs $Z$ of size $n/4$ would fail, because $n/4=|Z|=b|W|$ would
imply that $b$ divides $n/4$, a contradiction.

With that said, we now use our round elimination lemma in a one-shot fashion
to obtain our main result for integer LQPs.

######  Theorem 5.6 (Restatement of Theorem 1.6).

$\operatorname{LQ}_{\mathbb{Z}_{[-B,B]}}^{2}(\textsc{elemx}_{n})=\Omega(\sqrt{n}/(\log^{3/2}(nB)))$.

###### Proof.

Suppose that $\Pi$ is a deterministic 2-round $\mathbb{Z}_{[-B,B]}$-LQP for
$\textsc{elemx}_{n}$, whose root has cost $d_{1}$. By Lemma 5.5, there is a
one round $O(nB)$-bounded protocol for $\textsc{elemx}^{1/4}_{m}$ with cost
$d_{2}$. Combining the following three equations:

$\displaystyle\operatorname{cost}(\Pi)$ $\displaystyle\geq d_{1}+d_{2}$
$\displaystyle d_{2}$ $\displaystyle\geq\frac{0.14m}{\log M}$
$\displaystyle\lhd\text{ from \lx@cref{creftypecap~refnum}{lem:int-quarter-
oneround}}$ $\displaystyle m$ $\displaystyle\geq\frac{n}{2c_{0}d_{1}\log n\log
M}-2$ $\displaystyle\lhd\text{ from \lx@cref{creftypecap~refnum}{lem:zz-round-
elim}}$

gives

$\operatorname{cost}(\Pi)\geq 0.19\sqrt{\frac{n}{c_{0}\log
n\log^{2}M}}-2=\Omega\left(\frac{\sqrt{n}}{\log^{3/2}(nB)}\right)\,.\qed$

##  6 Upper Bounds

For the sake of completeness, we provide details of the LQPs attaining various
upper bounds referenced throughout the paper. For the most part, these upper
bounds are simple observations or extensions of well-known existing results.

###  6.1 Deterministic _k_ -round LQP for elemx

The following family of protocols works both when $D=\mathbb{Z}_{[0,1]}$ on
the problem $\textsc{elemx}_{n}$, and when $D=\mathbb{Z}_{q}$ on the problem
$\textsc{elemx}^{(q)}_{n}$. The algorithm appears to be well known, and
versions of it are described in Lemma 4.1 of [ACK20] and Section 2.2 of
[KUW88].

Let $d_{1},\ldots,d_{k}$ be a division sequence (see Lemma 3.5) for $n$, which
minimizes $\sum_{i=1}^{k}d_{i}$. Algorithm 1 makes no more than $d_{r}$
queries in each round $r$.

Algorithm 1 Outline of deterministic query protocol on $\mathbf{z}$

1:$[u,v]\leftarrow[1,n]$

2:for $r=1,\ldots,k$ do

3: Split the interval $[u,v]$ into $d_{r}+1$ intervals
$J_{1},\ldots,J_{d_{r}+1}$, each of size
$\leq\lceil\frac{v-u+1}{d_{r}+1}\rceil$

4: Query with matrix $A\in D^{d_{r}\times n}$, where $A_{i,j}$ is $1$ if $j\in
J_{i}$ and $0$ otherwise.

5: If $A\mathbf{z}$ is not all zero, let $i\in[d_{r}]$ be the index of any
nonzero entry; otherwise, let $i=d_{r}+1$.

6: Update $[u,v]\leftarrow J_{i}$.

7:Report $u$ as the index where $u\in Z$.

Since $d_{1},\ldots,d_{k}$ is a division sequence for $n$, the final interval
$[u,v]$ must have $u=v$. The total cost of the protocol is
$\sum_{i=1}^{k}d_{i}$, which by Lemma 3.5 lies in the interval
$[k(n^{1/k}-1),k(\lceil n^{1/k}\rceil-1)]$. Note that when $n=2^{k}$, the
algorithm cost is exactly $k$.

Write $\mathbf{1}_{S}$ to denote the indicator vector in $D^{n}$ for a given
set $S\subseteq[n]$. To prove that the algorithm is correct, it suffices to
verify that $\mathbf{1}^{\mathsf{T}}_{[u,v]}\mathbf{z}\neq 0$ in each round.
Since $\mathbf{1}^{\mathsf{T}}\mathbf{z}\neq 0$, this is true at the start.
For any given round, the matrix $A$ queries
$\mathbf{1}_{J_{1}},\ldots,\mathbf{1}_{J_{d_{r}}}$. Since
$\mathbf{1}_{[u,v]}=\sum_{i=1}^{d_{r}+1}\mathbf{1}_{J_{i}}$, and
$\mathbf{1}^{\mathsf{T}}_{[u,v]}\mathbf{z}\neq 0$, there must be some first
index $i$ for which $\mathbf{1}^{\mathsf{T}}_{J_{i}}\mathbf{z}\neq 0$. If
$i<d_{r}+1$, the index is shown in the query response; if $i=d_{r}+1$, then no
other intervals $J_{h}$ have $\mathbf{1}^{\mathsf{T}}_{J_{h}}\mathbf{z}\neq
0$, so $A\mathbf{z}$ is all zeros. In either case, the algorithm correctly
identifies the interval $J_{i}$ for which
$\mathbf{1}^{\mathsf{T}}_{J_{i}}\mathbf{z}\neq 0$.

###  6.2 Randomized 1-round LQP for elemx

The $\ell_{0}$-sampling algorithm from [JST11] relies on a standard result on
the exact recovery of sparse vectors in $\mathbb{R}^{n}$, which (paraphrasing)
states that $O(s)$ $\mathbb{R}$-linear queries suffice to exactly recover any
$s$-sparse vector $\mathbf{v}$ in $\mathbb{R}^{n}$, or if $\mathbf{v}$ is not
sparse, say that the output is dense with high probability. The
$\ell_{0}$-sampling algorithm then chooses subsets
$\\{T_{i}\\}_{i=1}^{\lceil\log n\rceil}$ where each $T_{i}$ is uniformly
randomly drawn from the set of all subsets of $[n]$ of size $2^{i}$. To obtain
a constant final error probability, for each set $T_{i}$, the
$\ell_{0}$-sampler runs the sparse recovery method on the coordinates given by
$T_{i}$ with $s=O(1)$. The sampler then returns a random index from the first
sparse recovery instance to successfully recover a nonzero vector. With high
probability, at least one of the sets $T_{i}$ will contain fewer than $O(1)$
entries of $Z$, and the algorithm succeeds.

Recovering $s$-sparse vectors in $\\{0,1\\}^{n}$ is easier than recovering
general $s$-sparse vectors in $\mathbb{R}^{n}$ or $\mathbb{Z}^{n}$, so
directly adapting [JST11]’s $\ell_{0}$-sampling algorithm to elemx means only
$O(\log n)$ queries are needed for $\mathbb{Z}_{[-B,B]}$ with
$B=O(\operatorname{poly}(n))$, and $O(\log^{2}n/\log q)$ for $\mathbb{Z}_{q}$.
This follows from the costs of $s$-sparse recovery and detection with
$D$-linear queries and $\\{0,1\\}^{n}$, addressed in the following lemma. We
spell out this result and its proof for the sake of completeness: though it
may be folklore, it appears not to have been published in quite this form.

######  Lemma 6.1 (Discrete $s$-sparse recovery).

There exists a query matrix $H\in\mathbb{Z}_{[-B,B]}^{r\times n}$ for
$r=O(s\log n/\log B)$ for which the query $Hv$ returns a unique value for all
$V\subseteq[n]$ with $|V|\leq s$. The same holds true for $\mathbb{Z}_{q}$
with $r=O(s\log n/\log q)$.

###### Proof.

Call a matrix in $A\in D^{r\times t}$ full-$[-1,1]$-rank if there does not
exist a nonzero vector $\mathbf{v}\in\\{-1,0,1\\}^{t}$ for which
$A\mathbf{v}=\mathbf{0}$. If we choose a matrix $B\in D^{r\times t}$ uniformly
at random, then it is full-$[-1,1]$-rank with probability $\geq
1-3^{t}/|D|^{r}$. One way to prove this is to consider columns the
$\mathbf{b}_{1}\ldots\mathbf{b}_{t}$ of $B$ one by one, and note that if each
$\mathbf{b}_{i}$ is not contained in the set
$F_{i}:=\\{\sum_{j=1}^{i-1}a_{i}\mathbf{b}_{i}:a\in\\{-1,0,1\\}^{i-1}\\}$,
then $B$ has full-$[-1,1]$-rank. Since $B$ is chosen uniformly at random, each
column is independent of the the earlier ones, so

$\displaystyle\Pr[\text{D doesn't have full $[-1,1]$-rank}]$
$\displaystyle\leq\sum_{i=1}^{t}\Pr[\mathbf{b}_{i}\notin
F_{i}]\leq\sum_{i=1}^{t}\frac{3^{i-1}}{|D|^{r}}\leq\frac{3^{t}}{|D|^{r}}\,.$

Let $r$ be chosen later; if we pick $\hat{H}\in D^{r\times n}$ uniformly at
random, then the expected number of sets $T\subseteq[n]$ with $|T|=2s$ for
which $\hat{H}_{T}$ (the submatrix of $\hat{H}$ with columns in $T$) has full
$[-1,1]$-rank is $\leq\binom{n}{2s}3^{2s}/|D|^{n}$. Letting $r=\lceil
2s\log(3n)/\log(|D|)\rceil$ makes this less than $1$. Consequently, there must
exist a specific matrix $H$ for which every such submatrix $H_{T}$ has full
$[-1,1]$-rank. Then for any two distinct vectors
$\mathbf{u},\mathbf{v}\in\\{0,1\\}^{n}$ with $|U|,|V|\leq s$, we cannot have
$H\mathbf{u}=H\mathbf{v}$, because that would imply there exists $T\supseteq
U\cup V$ with $|T|=2s$ for which $H_{T}(bu-bv)=0$, contradicting the full
$[-1,1]$-rank assumption. ∎

Detecting whether a $\\{0,1\\}^{n}$ vector is not $s$-sparse is also easier
than in $\mathbb{R}^{n}$. For $\mathbb{Z}_{[-B,B]}$-LQPs, querying with the
vector $\mathbf{1}\in\mathbb{Z}^{d}$ suffices. For $\mathbb{Z}_{q}$, because
Lemma 6.1 ensures that if a vector $\mathbf{z}$ is s-sparse, it can be
recovered exactly, it is enough to query $O(1)$ random vectors in
$\mathbb{Z}_{q}^{n}$. Let $\mathbf{r}$ be such a random vector, and let
$\mathbf{w}$ be the $s$-sparse vector in $\\{0,1\\}$ recovered using $H$; if
$\mathbf{z}$ was s-sparse, then $\mathbf{z}=\mathbf{w}$ and
$\mathbf{r}^{\mathsf{T}}\mathbf{z}=\mathbf{r}^{\mathsf{T}}\mathbf{w}$;
otherwise, $\mathbf{r}^{\mathsf{T}}\mathbf{z}$ does not equal
$\mathbf{r}^{\mathsf{T}}\mathbf{w}$ with probability $1-1/q$.

##  7 Connections Between $\mathbb{Z}_{2}$-LQPs and Circuit Complexity

A weaker version of Theorem 1.3 can be proven by combining existing results.
As shown in the following lemma, a given $k$-round $\mathbb{Z}_{2}$-LQP $\Pi$
for $\textsc{elemx}^{(2)}$ can be converted to a communication protocol
$\Upsilon$ for the Karchmer-Wigderson game on $\textsc{parity}_{n}$, with the
communication cost $C$ of $\Upsilon$ being $\leq 2\operatorname{cost}(\Pi)$.
By a slight adaptation of the proof of Theorem 5 in [NW93], we can convert
$\Upsilon$ into an unbounded fan-in boolean formula with depth $k+1$ and no
more than $2^{C}-1$ AND/OR gates that computes $\textsc{parity}_{n}$.
Relatively tight lower bounds on the size of such a formula date back to
[Has86], but we use a result of [Ros15], which says that a depth-$(k+1)$
unbounded fan-in formula computing $\textsc{parity}_{n}$ must have at least
$2^{\Omega(k(n^{1/k}-1)}$ AND/OR gates. Thus
$\operatorname{cost}(\Pi)\geq\frac{1}{2}C\geq\Omega(k(n^{1/k}-1))$.

######  Lemma 7.1.

Consider the Karchmer-Wigderson game for $\textsc{parity}_{n}$, in which Alice
has a set $X\in\\{0,1\\}^{n}$ with $|X|$ even, and Bob has a set
$Y\in\\{0,1\\}^{n}$ with $|Y|$ odd, and they seek to identify an index
$i\in[n]$ for which $\mathbf{x}_{i}\neq\mathbf{y}_{i}$. Let $\Pi$ be a
$k$-round $\mathbb{Z}_{2}$-LQP for $\textsc{elemx}^{(2)}_{n}$; then there
exists $\Upsilon$ a $k$-round communication protocol for this game, with cost
$\leq 2\operatorname{cost}(\Pi)$.

###### Proof.

Let $\rho$ be the root of $\Pi$, with label
$A_{\rho}\in\mathbb{Z}_{2}^{d_{\rho}\times n}$. In the first round of
$\Upsilon$, Alice sends $A_{\rho}\mathbf{x}$ to Bob. Then Bob computes
$A_{\rho}\mathbf{y}$, and uses Alice’s message to determine
$\mathbf{r}_{1}=A_{\rho}(\mathbf{x}+\mathbf{y})$. The value $\mathbf{r}_{1}$
determines a child node $\nu$ of $\rho$. If this is a leaf, Bob outputs its
label $o_{\nu}$. Otherwise, in the second round, Bob sends both
$A_{\rho}\mathbf{y}$ and $A_{\nu}\mathbf{y}$ to Alice. Given
$A_{\rho}\mathbf{y}$, Alice can determine $\nu$, and compute
$A_{\nu}\mathbf{x}$. With this, Alice can compute
$\mathbf{r}_{2}=A_{\nu}(\mathbf{x}+\mathbf{y})$, and identify the child node
$\mu$ of $\nu$. If this is a leaf, Alice outputs $o_{\mu}$; otherwise, in the
third round, Alice sends $A_{\nu}\mathbf{x}$ and $A_{\mu}\mathbf{x}$ to Bob;
the players continue in this fashion until a leaf is reached and the protocol
ends; since $\Pi$ has depth $k$, this takes at most $k$ rounds.

This protocol is correct, because it finds the leaf of $\Pi$ associated to the
input $\mathbf{x}+\mathbf{y}$. Since we are promised $\mathbf{x}$ has even
parity, and $\mathbf{y}$ odd, $\mathbf{x}+\mathbf{y}$ has odd parity and thus
fulfills the condition under which a protocol for $\textsc{elemx}^{(2)}_{n}$
must be correct. The output value is an index $i$ where
$\mathbf{x}_{i}+\mathbf{y}_{i}=1$, hence where
$\mathbf{x}_{i}\neq\mathbf{y}_{i}$, as required for the communication game.

Since $A_{\rho}\mathbf{x}\in\mathbb{Z}_{2}^{d_{\rho}}$, the round first
message uses exactly $d_{\rho}$ bits. The second, $d_{\rho}+d_{\nu}$, the
third, $d_{\nu}+d_{\mu}$, and so on. The communication needed on inputs
($\mathbf{x},\mathbf{y}$) is thus at most twice
$\operatorname{cost}(\Pi,\mathbf{x}+\mathbf{y})$, so the worst-case
communication cost of $\Upsilon$ is at most $2\operatorname{cost}(\Pi)$. ∎

##  8 Appendix

The following estimate was used in Section 4 during calculations in the proof
of our $\mathbb{Z}_{q}$-LQP lower bound.

######  Lemma 8.1.

Let $C,D$ be constants with $2C\leq D$ and $D\geq 1$. Then

$\displaystyle\max\left(\frac{\ln
n}{C},k\left(\frac{1}{D}n^{1/k}-1\right)\right)\geq\frac{1}{D(1+C)}k\left(n^{1/k}-1\right)\,.$
(15)

###### Proof.

Let $\gamma_{n}(k)=k(n^{1/k}-1)$. We have
$k\left(\frac{1}{D}n^{1/k}-1\right)\geq\frac{1}{D}\gamma_{n}(k)-k$. Since
$\gamma_{n}(k)$ is decreasing, let $k_{\star}$ be the unique solution to
$\frac{1}{D}\gamma_{n}(k_{\star})=\frac{1}{C}\ln n$. Since $\gamma_{n}(\ln
n)=(e-1)\ln n\leq 2\ln n\leq\frac{D}{C}\ln n$, it follows $k_{\star}\leq\ln
n$. Let $k_{\dagger}$ be the unique solution to
$\frac{1}{D}\gamma_{n}(k_{\dagger})-k_{\dagger}=\frac{1}{C}\ln n$. Since
$k_{\dagger}\leq k_{\star}$, $k_{\dagger}\leq\ln n$ as well. Evaluating the
right hand side of eq. 15 at $k_{\dagger}$ gives:

$\displaystyle\frac{1}{D(1+C)}\gamma_{n}(k_{\dagger})$
$\displaystyle=\frac{1}{D(1+C)}\left(\frac{D\ln n}{C}+Dk_{\dagger}\right)$
$\displaystyle\leq\frac{1}{D(1+C)}\left(\frac{D\ln n}{C}+D\ln n\right)$
$\displaystyle=\frac{\ln
n}{C}=\frac{1}{D}\gamma_{n}(k_{\dagger})-k_{\dagger}\,.$

Because the derivative of $\frac{1}{D(1+C)}\gamma_{n}(k)$ is less that of
$\frac{\ln n}{C}$ when $k\geq k_{\dagger}$, and greater than that of
$\frac{1}{D}\gamma_{n}(k)-k$ for $k\leq k_{\dagger}$, we can extend this
inequality to all $k\in(0,\infty)$, proving eq. 15. ∎

## References

  * [AAAK17] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna.  Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons.  In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 39–75. PMLR, 2017.
  * [AB19] Hasan Abasi and Nader Bshouty.  On learning graphs with edge-detecting queries.  In Algorithmic Learning Theory, pages 3–30. PMLR, 2019.
  * [ABB+17] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs.  Separations in query complexity based on pointer functions.  J. ACM, 64(5):32:1–32:24, 2017.
  * [ACK20] Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna.  Graph connectivity and single element recovery via linear and or queries.  arXiv preprint arXiv:2007.06098, 2020.
  * [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proc. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 459–467, 2012.
  * [ALWZ20] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang.  Improved bounds for the sunflower lemma.  In Proc. 52nd Annual ACM Symposium on the Theory of Computing, pages 624–630, 2020.
  * [BCW20] Tolson Bell, Suchakree Chueluecha, and Lutz Warnke.  Note on sunflowers.  CoRR, abs/2009.09327, 2020.
  * [BdW02] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theor. Comput. Sci., 288(1):21–43, 2002.
  * [BHPSR+20] Paul Beame, Sariel Har-Peled, Natarajan Sivaramakrishnan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha.  Edge estimation with independent set oracles.  ACM Trans. Alg., 16(4):1–27, 2020.
  * [BKS17] Paul Beame, Paraschos Koutris, and Dan Suciu.  Communication steps for parallel query processing.  J. ACM, 64(6):40:1–40:58, 2017.
  * [BS18] Eric Balkanski and Yaron Singer.  The adaptive complexity of maximizing a submodular function.  In Proc. 50th Annual ACM Symposium on the Theory of Computing, pages 1138–1151, 2018.
  * [Bsh09] Nader H. Bshouty.  Optimal algorithms for the coin weighing problem with a spring scale.  In COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009, 2009.
  * [CCM16] Amit Chakrabarti, Graham Cormode, and Andrew McGregor.  Robust lower bounds for communication and stream computation.  Theor. Comput., 12(1):1–35, 2016.  Preliminary version in Proc. 40th Annual ACM Symposium on the Theory of Computing, pages 641–649, 2008.
  * [CF14] Graham Cormode and Donatella Firmani.  A unifying framework for $\ell$0-sampling algorithms.  Distributed Parallel Databases, 32(3):315–335, 2014.
  * [CG18] Clément L. Cannone and Tom Gur.  An adaptivity hierarchy theorem for property testing.  computational complexity, 27(4):671–716, 2018.
  * [CK16] Amit Chakrabarti and Sagar Kale.  Strong fooling sets for multi-player communication with applications to deterministic estimation of stream statistics.  In Proc. 57th Annual IEEE Symposium on Foundations of Computer Science, pages 41–50, 2016.
  * [CR04] Amit Chakrabarti and Oded Regev.  An optimal randomised cell probe lower bound for approximate nearest neighbour searching.  In Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, pages 473–482, 2004.
  * [CW16] Amit Chakrabarti and Anthony Wirth.  Incidence geometries and the pass complexity of semi-streaming set cover.  In Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1365–1373, 2016.
  * [CY20] Graham Cormode and Ke Yi.  Small Summaries for Big Data.  Cambridge University Press, Cambridge, 2020.
  * [DL78] David P. Dobkin and Richard J. Lipton.  A lower bound of the ½n2 on linear search programs for the knapsack problem.  J. Comput. Syst. Sci., 16(3):413–417, 1978.
  * [Don06] David L. Donoho.  Compressed sensing.  IEEE Trans. Inf. Theory, 52(4):1289–1306, 2006.
  * [ER60] Paul Erdős and Richard Rado.  Intersection theorems for systems of sets.  Journal London Math. Soc., 35(1):85–90, 1960.
  * [ER63] Paul Erdős and Alfréd Rényi.  On two problems of information theory.  Publ. Math. Inst. Hung. Acad. Sci., Ser. A, 8:241–254, 1963.
  * [ER14] Yuval Emek and Adi Rosén.  Semi-streaming set cover.  In Proc. 41st International Colloquium on Automata, Languages and Programming, pages 453–464, 2014.
  * [FIS08] Gereon Frahling, Piotr Indyk, and Christian Sohler.  Sampling in dynamic data streams and applications.  Int. J. Comput. Geom. Appl., 18(1/2):3–28, 2008.
  * [FW81] Péter Frankl and Richard M. Wilson.  Intersection theorems with geometric consequences.  Combinatorica, 1(3):357–368, 1981.
  * [GG06] Weidong Gao and Alfred Geroldinger.  Zero-sum problems in finite abelian groups: A survey.  Expositiones Mathematicae, 24(4):337–369, 2006.
  * [GM09] Sudipto Guha and Andrew McGregor.  Stream order and order statistics: Quantile estimation in random-order streams.  SIAM J. Comput., 38(5):2044–2059, 2009.
  * [GO16] Venkatesan Guruswami and Krzysztof Onak.  Superlinear lower bounds for multipass graph processing.  Algorithmica, 76(3):654–683, November 2016.
  * [Has86] John Hastad.  Almost optimal lower bounds for small depth circuits.  In Proc. 18th Annual ACM Symposium on the Theory of Computing, pages 6–20, 1986.
  * [HHL18] Hamed Hatami, Kaave Hosseini, and Shachar Lovett.  Structure of protocols for XOR functions.  SIAM J. Comput., 47(1):208–217, 2018.
  * [HLY19] Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev.  Optimality of linear sketching under modular updates.  In Amir Shpilka, editor, Proc. 34th Annual IEEE Conference on Computational Complexity, volume 137 of LIPIcs, pages 13:1–13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [JST11] Hossein Jowhari, Mert Saglam, and Gábor Tardos.  Tight bounds for $l_{p}$ samplers, finding duplicates in streams, and related problems.  In Proc. 30th ACM Symposium on Principles of Database Systems, pages 49–58, 2011.
  * [KLM19] Daniel M. Kane, Shachar Lovett, and Shay Moran.  Near-optimal linear decision trees for k-sum and related problems.  J. ACM, 66(3):16:1–16:18, 2019.
  * [KMSY18] Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev.  Linear sketching over f_2.  In Rocco A. Servedio, editor, Proc. 33rd Annual IEEE Conference on Computational Complexity, volume 102 of LIPIcs, pages 8:1–8:37. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [KNP+17] Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, and Mobin Yahyazadeh.  Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams.  In Proc. 58th Annual IEEE Symposium on Foundations of Computer Science, pages 475–486, 2017.
  * [KNW10] Daniel M. Kane, Jelani Nelson, and David P. Woodruff.  An optimal algorithm for the distinct elements problem.  In Proc. 29th ACM Symposium on Principles of Database Systems, pages 41–52, 2010.
  * [KP19] Akshay Kamath and Eric Price.  Adaptive sparse recovery with limited adaptivity.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2729–2744, 2019.
  * [KUW88] Richard M. Karp, Eli Upfal, and Avi Wigderson.  The complexity of parallel search.  J. Comput. Syst. Sci., 36(2):225–253, 1988.
  * [KW90] Mauricio Karchmer and Avi Wigderson.  Monotone circuits for connectivity require super-logarithmic depth.  SIAM J. Disc. Math., 3(2):255–265, 1990.  Preliminary version in Proc. 20th Annual ACM Symposium on the Theory of Computing, pages 539–550, 1988.
  * [LNNW95] László Lovász, Moni Naor, Ilan Newman, and Avi Wigderson.  Search problems in the decision tree model.  SIAM J. Disc. Math., 8(1):119–132, 1995.
  * [LNW14] Yi Li, Huy L. Nguyen, and David P. Woodruff.  Turnstile streaming algorithms might as well be linear sketches.  In Proc. 46th Annual ACM Symposium on the Theory of Computing, pages 174–183, 2014.
  * [LPY16] Mingmou Liu, Xiaoyin Pan, and Yitong Yin.  Randomized approximate nearest neighbor search with limited adaptivity.  In Proc. 28th ACM Symposium on Parallelism in Algorithms and Architectures, page 23–33, 2016.
  * [MK13] Gianluca De Marco and Dariusz R. Kowalski.  Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non-adaptiveness.  Rand. Struct. Alg., 42(1):97–109, 2013.
  * [MNSW98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson.  On data structures and asymmetric communication complexity.  J. Comput. Syst. Sci., 57(1):37–49, 1998.  Preliminary version in Proc. 27th Annual ACM Symposium on the Theory of Computing, pages 103–111, 1995.
  * [Mut05] S. Muthukrishnan.  Data streams: Algorithms and applications.  Found. Trends Theor. Comput. Sci., 1(2):117–236, 2005.
  * [Nis21] Noam Nisan.  The demand query model for bipartite matching.  In Proc. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 592––599, 2021.
  * [NW93] Noam Nisan and Avi Wigderson.  Rounds in communication complexity revisited.  SICOMP, 22(1):211–219, 1993.  Preliminary version in Proc. 23rd Annu. ACM Symp. Theory Comput., pages 419–429, 1991.
  * [NY19] Jelani Nelson and Huacheng Yu.  Optimal lower bounds for distributed and streaming spanning forest computation.  In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1844–1860, 2019.
  * [Ols69] John Olson.  A combinatorial problem on finite abelian groups, i.  Journal of Number Theory, 1:8–10, 1969.
  * [PT07] Mihai Pǎtraşcu and Mikkel Thorup.  Randomization does not help searching predecessors.  In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 555–564, 2007.
  * [PW13] Eric Price and David P. Woodruff.  Lower bounds for adaptive sparse recovery.  In Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 652–663, 2013.
  * [Rao20] Anup Rao.  Coding for sunflowers.  Discrete Analysis, (2), 2020.
  * [Ros15] Benjamin Rossman.  The average sensitivity of bounded-depth formulas.  In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science, pages 424–430, 2015.
  * [Sen03] Pranab Sen.  Lower bounds for predecessor searching in the cell probe model.  In Proc. 18th Annual IEEE Conference on Computational Complexity, pages 73–83, 2003.
  * [Tao20] Terry Tao.  The sunflower lemma via Shannon entropy, 2020.  Blog post; available online at https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/.
  * [TZ97] Gábor Tardos and Uri Zwick.  The communication complexity of the universal relation.  In Proc. 12th Annual IEEE Conference on Computational Complexity, pages 247–259, 1997.
  * [vEBK69] P. van Emde Boas and Kruyswijk.  A combinatorial problem on finite abelian groups III.  Technical Report ZW 8, Mathematisch Centrum, Amsterdam, The Netherlands, 1969.
  * [Woo14] David P. Woodruff.  Sketching as a tool for numerical linear algebra.  Found. Trends Theor. Comput. Sci., 10(1-2):1–157, 2014.
  * [ZS10] Zhiqiang Zhang and Yaoyun Shi.  On the parity complexity measures of boolean functions.  Theor. Comput. Sci., 411(26-28):2612–2618, 2010.