  For a graph $G$, a $D$-diameter-reducing exact hopset is a small set of
additional edges $H$ that, when added to $G$, maintains its graph metric but
guarantees that all node pairs have a shortest path in $G \cup H$ using at most
$D$ edges. A shortcut set is the analogous concept for reachability. These
objects have been studied since the early '90s due to applications in parallel,
distributed, dynamic, and streaming graph algorithms.
  For most of their history, the state-of-the-art construction for either
object was a simple folklore algorithm, based on randomly sampling nodes to hit
long paths in the graph. However, recent breakthroughs of Kogan and Parter
[SODA '22] and Bernstein and Wein [SODA '23] have finally improved over the
folklore diameter bound of $\widetilde{O}(n^{1/2})$ for shortcut sets and for
$(1+\epsilon)$-approximate hopsets. For both objects it is now known that one
can use $O(n)$ hop-edges to reduce diameter to $\widetilde{O}(n^{1/3})$. The
only setting where folklore sampling remains unimproved is for exact hopsets.
Can these improvements be continued?
  We settle this question negatively by constructing graphs on which any exact
hopset of $O(n)$ edges has diameter $\widetilde{\Omega}(n^{1/2})$. This
improves on the previous lower bound of $\widetilde{\Omega}(n^{1/3})$ by Kogan
and Parter [FOCS '22]. Using similar ideas, we also polynomially improve the
current lower bounds for shortcut sets, constructing graphs on which any
shortcut set of $O(n)$ edges reduces diameter to $\widetilde{\Omega}(n^{1/4})$.
This improves on the previous lower bound of $\Omega(n^{1/6})$ by Huang and
Pettie [SIAM J. Disc. Math. '18]. We also extend our constructions to provide
lower bounds against $O(p)$-size exact hopsets and shortcut sets for other
values of $p$; in particular, we show that folklore sampling is near-optimal
for exact hopsets in the entire range of $p \in [1, n^2]$.
