  Klee's measure problem (computing the volume of the union of $n$
axis-parallel boxes in $\mathbb{R}^d$) is well known to have $n^{\frac{d}{2}\pm
o(1)}$-time algorithms (Overmars, Yap, SICOMP'91; Chan FOCS'13). Only recently,
a conditional lower bound (without any restriction to ``combinatorial''
algorithms) could be shown for $d=3$ (K\"unnemann, FOCS'22). Can this result be
extended to a tight lower bound for dimensions $d\ge 4$?
  In this paper, we formalize the technique of the tight lower bound for $d=3$
using a combinatorial object we call prefix covering design. We show that these
designs, which are related in spirit to combinatorial designs, directly
translate to conditional lower bounds for Klee's measure problem and various
related problems. By devising good prefix covering designs, we give the
following lower bounds for Klee's measure problem in $\mathbb{R}^d$, the depth
problem for axis-parallel boxes in $\mathbb{R}^d$, the
largest-volume/max-perimeter empty (anchored) box problem in $\mathbb{R}^{2d}$,
and related problems:
  - $\Omega(n^{1.90476})$ for $d=4$,
  - $\Omega(n^{2.22222})$ for $d=5$,
  - $\Omega(n^{d/3 + 2\sqrt{d}/9-o(\sqrt{d})})$ for general $d$,
  assuming the 3-uniform hyperclique hypothesis. For Klee's measure problem and
the depth problem, these bounds improve previous lower bounds of
$\Omega(n^{1.777...}), \Omega(n^{2.0833...})$ and $\Omega(n^{d/3 + 1/3 +
\Theta(1/d)})$ respectively.
  Our improved prefix covering designs were obtained by (1) exploiting a
computer-aided search using problem-specific insights as well as SAT solvers,
and (2) showing how to transform combinatorial covering designs known in the
literature to strong prefix covering designs. In contrast, we show that our
lower bounds are close to best possible using this proof technique.
