On the Power of Learning from $k$-Wise Queries
  Several well-studied models of access to data samples, including statistical
queries, local differential privacy and low-communication algorithms rely on
queries that provide information about a function of a single sample. (For
example, a statistical query (SQ) gives an estimate of $Ex_{x \sim D}[q(x)]$
for any choice of the query function $q$ mapping $X$ to the reals, where $D$ is
an unknown data distribution over $X$.) Yet some data analysis algorithms rely
on properties of functions that depend on multiple samples. Such algorithms
would be naturally implemented using $k$-wise queries each of which is
specified by a function $q$ mapping $X^k$ to the reals. Hence it is natural to
ask whether algorithms using $k$-wise queries can solve learning problems more
efficiently and by how much.
  Blum, Kalai and Wasserman (2003) showed that for any weak PAC learning
problem over a fixed distribution, the complexity of learning with $k$-wise SQs
is smaller than the (unary) SQ complexity by a factor of at most $2^k$. We show
that for more general problems over distributions the picture is substantially
richer. For every $k$, the complexity of distribution-independent PAC learning
with $k$-wise queries can be exponentially larger than learning with
$(k+1)$-wise queries. We then give two approaches for simulating a $k$-wise
query using unary queries. The first approach exploits the structure of the
problem that needs to be solved. It generalizes and strengthens (exponentially)
the results of Blum et al.. It allows us to derive strong lower bounds for
learning DNF formulas and stochastic constraint satisfaction problems that hold
against algorithms using $k$-wise queries. The second approach exploits the
$k$-party communication complexity of the $k$-wise query function.
