Imagine you're trying to figure out the shape of a puddle by dropping marbles into a gutter and watching where they roll to a stop. You can drop as many marbles as you want, but you only see their final resting positions — not the paths they took or the shape of the gutter. With enough marbles, you can sketch the puddle's outline, but every extra dimension of the gutter (width, slope, curvature) exponentially multiplies the marbles you need. This paper proves that no cleverness in how you read the final marble positions can escape that exponential tax. The committed claim: for sampling-based reachability analysis — a workhorse in robotics safety verification — the sample complexity to achieve Hausdorff accuracy r scales as Õ(2ⁿ·e^{nμT}·(R/r)ⁿ/(ρκ)), and a minimax lower bound matches these dependencies up to a factor of 2·4ⁿ and log terms. This means the exponential dependence on state dimension n, and on horizon T for expanding systems, is not an artifact of any particular algorithm. It is a fundamental property of the observation model — you're stuck with it regardless of your estimator. The architecture here is not computational but information-theoretic. The authors frame reachable set estimation as a support estimation problem under flow distortion. The initial set has a uniform lower bound on local volume density (κ) and the dynamics satisfy a one-sided Lipschitz condition (μ). They construct packing-based lower bounds using Le Cam's method, building families of initial sets whose images under the flow are statistically indistinguishable without exponentially many samples. The upper bound comes from ε-net covering arguments applied to the endpoint cloud directly. This is classical nonparametric statistics machinery applied to a controls problem — the bridge between the two communities is the paper's real contribution. On the ladder: existing guarantees in sampling-based reachability (from work by Devonport, Khaled, Gruenbacher, and others) typically control missed probability mass relative to the convex hull, or provide PAC-style containment bounds. Those results tell you about conservative outer approximations. This paper addresses a different, harder question — the geometric (Hausdorff) accuracy of the estimated set boundary itself. There is no direct SOTA to beat because the question wasn't previously formalized this tightly. The closest comparison is Devonport & Arcak (2021) on scenario-based reachability, which bounds containment probability but not Hausdorff error. So the ladder position is: new formalization with tight bounds, rather than improvement over a named competitor. Integrity is a genuine strength. The matching upper and lower bounds are mathematical proofs, not simulations claiming generality. The experiments (2D planar systems, 3-6 DOF robot arms) serve as illustrations of the theoretical predictions — they show corners increasing sample needs and contraction helping, as the theory predicts — not as the evidence base. The proofs carry explicit assumptions (uniform density lower bound, one-sided Lipschitz, domain large enough to accommodate the packing construction), and the authors are clear about where these assumptions bite. The factor-of-4ⁿ gap between upper and lower bounds is honestly stated rather than buried. The practical upshot is sobering for anyone building sampling-based safety verification for high-dimensional robotic systems. For a 6-DOF arm at Hausdorff accuracy r, the sample counts predicted by the theory are already enormous. The exponential wall means that for systems above roughly 10 dimensions, brute-force sampling-based reachability at fine geometric resolution is computationally infeasible — not because we lack a better algorithm, but because the observation model (independent endpoint samples) doesn't carry enough information. This is a clean impossibility result that redirects effort: you either need to change the observation model (structured samples, trajectory information, active sampling) or accept coarser accuracy guarantees. The robot-arm experiments in 3-6 DOF show empirical Hausdorff error scaling consistent with the theory. The planar experiments with corners and contracting dynamics confirm the predicted effects: corners increase the effective sample requirement, contraction (negative μ) helps. Code is released on GitHub, and the paper is an extended version of a CoRL 2026 submission, now submitted to IEEE TAC. The dual-venue strategy — conference for visibility, journal for the full proofs — is standard and appropriate here.
