This dissertation is based upon two papers and one manuscript. The first paper ``A Lower Bound for Jumbled Indexing''
examines the problem of jumbled indexing: Given an input string $S$ on an alphabet $\Sigma = \{\sigma_1, \dots \sigma_\delta\}$,
store it in a data structure such that given frequencies $f_1,\dots f_\delta$, report all substrings of $S$
where the frequency of character $\sigma_i$ is equal to $f_i$. In other words the problem is a matter of matching the
occurrences of letters as opposed to their relative position in the substring. We present the first unconditional lower bound
for the problem and furthermore we present the first lower bound which holds for the binary alphabet. We show that if a data structure
has a query time of $O(n^{0.5-o(1)} +k)$, where $k$ is the size of the output, then the data structure must use $\Omega(n^{2-o(1)})$ space.
This shows that reporting the substrings matching a frequency is significantly harder than deciding
whether such a match exists, even for a binary alphabet.

In the second paper ``Rectangle Stabbing and Orthogonal Range Reporting Lower Bounds in Moderate Dimensions'' we study classical
problems within computational geometry, namely Rectangle Stabbing, Orthogonal Range Reporting and Dominance Reporting, although in
an unusual setting, namely when the dimension is $c\log(n)$ (for some constant $c$). We show that if a data structure achieves
$Q(n) = O(n^{1-\gamma})$ query time, for $\gamma \geq \frac{2}{2+ \log c}$, then the space usage must be $\Omega\left(n^{1-\gamma} n^{\sqrt{c \gamma}/e - o(\sqrt{c \gamma})}\right)$. This overcomes shortcomings of previous proofs in which results could not be extended past
$d = \Omega(\sqrt{\log n})$.

The manuscript ``Hierarchical Categories in Colored Range Searching'' extends the problem of colored range counting. In colored range counting, the
colors are assumed to be independent and in this body of work we investigate different ways of assigning a hierarchy among the colors.
We study two natural variants and when the underlying hierarchy has a tree structure, we show interesting connections to some well-established
problems. When the hierarchy is a general DAG we show a conditional lower bound by reducing the orthogonal vectors problem to both variants.
This shows that neither problem can be solved in less than quadratic time unless the well established Strong Exponential Time Hypothesis fails. Interestingly for one of the variants, we
give a data structure which uses quadratic preprocessing time, $O(n^{3/2})$ space and $O(\log n)$ query time. This is one of the rare instances where there is a polynomial gap between the preprocessing time and the space usage of a data structure.