  Given an $n \times d$ dimensional dataset $A$, a projection query specifies a
subset $C \subseteq [d]$ of columns which yields a new $n \times |C|$ array. We
study the space complexity of computing data analysis functions over such
subspaces, including heavy hitters and norms, when the subspaces are revealed
only after observing the data. We show that this important class of problems is
typically hard: for many problems, we show $2^{\Omega(d)}$ lower bounds.
However, we present upper bounds which demonstrate space dependency better than
$2^d$. That is, for $c,c' \in (0,1)$ and a parameter $N=2^d$ an
$N^c$-approximation can be obtained in space $\min(N^{c'},n)$, showing that it
is possible to improve on the na\"{i}ve approach of keeping information for all
$2^d$ subsets of $d$ columns. Our results are based on careful constructions of
instances using coding theory and novel combinatorial reductions that exhibit
such space-approximation tradeoffs.

Data Structures and Algorithms;Computational Complexity