hypotheses $D_{0},D_{1}$ of the models
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
and
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
given by Lemma H.5. ∎

###  H.4 Computational Lower Bounds: Packing Number of Manifold Classes

We now prove the computational lower bounds Theorems 5.3 and 5.6. For this,
and in order to apply Theorem G.2, we build explicit packings of the manifold
classes. To study the two models and the different regimes of parameters, we
exhibit two types of such packings. The first ones that we describe
(Proposition H.4) use translations of a fixed manifold $M_{0}$ in the ambient
space, and are called ambient packings (see Section H.4.1). The second ones
(Proposition H.5) use a local smooth bumping strategy based on a fixed
manifold $M_{0}$, and are called intrinsic packings (see Section H.4.2).
Finally, the proof of the computational lower bounds are presented in Section
H.4.3.

####  H.4.1 Global Ambient Packings

To derive the first manifold packing lower bound, we will use translations in
$\mathbb{R}^{n}$ and the following lemma.

######  Lemma H.6.

La $K$ be a compact subset of $\mathbb{R}^{n}$. Given $v\in\mathbb{R}^{n}$,
let $K_{v}=\left\\{{p+v,p\in K}\right\\}$ be the translation of $K$ by the
vector $v$. Then $\mathrm{d_{H}}(K,K_{v})=\left\|v\right\|$.

###### Proof of Lemma H.6.

If $v=0$, the result is straightforward, so let us assume that $v\neq 0$.
Since $K$ is compact, the map $g$ defined for $p\in K$ by
$g(p)=\left\langle{v/\left\|v\right\|},{p}\right\rangle$ attains its maximum
at some $p_{0}\in K$. But by definition of $K_{v}$, $p_{0}+v\in K_{v}$, so

$\displaystyle\mathrm{d_{H}}(K,K_{v})$
$\displaystyle\geq\mathrm{d}(p_{0}+v,K)$ $\displaystyle=\min_{p\in
K}\left\|(p_{0}+v)-p\right\|$ $\displaystyle\geq\min_{p\in
K}\left\langle{\frac{v}{\left\|v\right\|}},{(p_{0}+v)-p}\right\rangle$
$\displaystyle=\left\|v\right\|+\min_{p\in
K}\left\langle{\frac{v}{\left\|v\right\|}},{p_{0}-p}\right\rangle$
$\displaystyle=\left\|v\right\|.$

On the other hand, for all $p\in K$ we have $p+v\in K_{v}$, yielding
$\mathrm{d}(p,K_{v})\leq\left\|v\right\|$, and symmetrically
$\mathrm{d}(p+v,K)\leq\left\|v\right\|$. Therefore
$\mathrm{d_{H}}(K,K_{v})\leq\left\|v\right\|$, which concludes the proof. ∎

As a result, packings of sets in $\mathbb{R}^{n}$ naturally yields packings in
the manifold space, by translating a fixed manifold
$M_{0}\subset\mathbb{R}^{n}$. With this remark in mind, we get the following
ambient packing lower bound.

######  Proposition H.4.

Assume that $\mathrm{rch}_{\min}\leq R/24$. Writing
$C_{d}=9(2^{d}\sigma_{d-1})$, let $\mathcal{V}>0$ be such that

$1\leq\frac{\mathcal{V}}{C_{d}\mathrm{rch}_{\min}^{d}}\leq\max_{1\leq k\leq
n}\left(\frac{R}{48\mathrm{rch}_{\min}\sqrt{k}}\right)^{k}.$

Then for all $\varepsilon\leq R/2$,

$\displaystyle\log\mathrm{pk}_{\bigl{(}\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}}(\varepsilon)\geq
n\log\left(\frac{R}{4\varepsilon}\right),$

and such a packing can be chosen so that all its elements $M$ have volume
$\mathcal{V}/6\leq\mathcal{H}^{d}(M)\leq\mathcal{V}$.

###### Proof of Proposition H.4.

Let $z_{1},\dots,z_{N}\in\mathrm{B}(0,R/2)$ be a $r$-packing of
$\mathrm{B}(0,R/2)$. From Proposition B.4, such a packing can be taken so that
$N\geq(R/(4r))^{n}$. Applying Proposition H.2 with parameters
$\mathrm{rch}_{\min}$, $\mathcal{V}$ and $R^{\prime}=R/2$, we get the
existence of some $M_{0}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ such
that $\mathcal{V}/6\leq\mathcal{H}^{d}(M_{0})\leq\mathcal{V}$ and
$M_{0}\subseteq\mathrm{B}(0,R/2)$. Note that for all $z\in\mathrm{B}(0,R/2)$,
the translation $M_{z}=\left\\{{p+z,p\in M_{0}}\right\\}$ belongs to
$\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$, has the same volume as $M_{0}$,
and satisfies
$M_{z}\subseteq\mathrm{B}(0,R/2+\left\|z\right\|)\subseteq\mathrm{B}(0,R)$. In
addition, Lemma H.6 asserts that for all $z,z^{\prime}\in\mathrm{B}(0,R/2)$,
$\mathrm{d_{H}}(M_{z},M_{z^{\prime}})=\left\|z-z^{\prime}\right\|$. In
particular, for all $i\neq j\in\left\\{{1,\dots,N}\right\\}$,
$\mathrm{d_{H}}(M_{z_{i}},M_{z_{j}})=\left\|z_{i}-z_{j}\right\|>2r$. As a
result, the family $\left\\{{M_{z_{i}}}\right\\}_{1\leq i\leq N}$ provides us
with an $r$-packing of
$\bigl{(}\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}$
with cardinality $N\geq(R/(4r))^{n}$, and composed of submanifold with volume
$\mathcal{V}/6\leq\mathcal{H}^{d}(M)\leq\mathcal{V}$, which concludes the
proof. ∎

####  H.4.2 Local Intrinsic Packings

In the same spirit as Proposition H.3 for informational lower bounds, the
following result allows to build packings of manifold classes by small
perturbations of a base submanifold $M_{0}$. Note, again, that the larger the
volume $\mathcal{H}^{d}(M_{0})$, the stronger the result.

######  Proposition H.5.

For all $M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$ and
$r\leq\mathrm{rch}_{\min}/(2^{34}d^{2})$, there exists a family of
submanifolds $\left\\{{M_{s}}\right\\}_{1\leq
s\leq\mathcal{N}}\subseteq\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ with
cardinality $\mathcal{N}$ such that

$\log\mathcal{N}\geq
n\frac{\mathcal{H}^{d}(M_{0})}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{19}r}\right)^{d/2},$

and that satisfies:

  * •

$M_{0}$ and $\left\\{{M_{s}}\right\\}_{1\leq s\leq\mathcal{N}}$ have a point
in common: $M_{0}\cap\bigl{(}\cap_{1\leq
s\leq\mathcal{N}}M_{s}\bigr{)}\neq\emptyset$.

  * •

For all $s\in\left\\{{1,\dots,\mathcal{N}}\right\\}$,

$\mathrm{d_{H}}(M_{0},M_{s})\leq 23r\text{ and
}\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{s})\leq
2\mathcal{H}^{d}(M_{0}).$

  * •

For all $s\neq s^{\prime}\in\left\\{{1,\dots,\mathcal{N}}\right\\}$
$\mathrm{d_{H}}(M_{s},M_{s^{\prime}})>2r$.

###### Proof of Proposition H.5.

For $\delta\leq\mathrm{rch}_{\min}/8$ to be chosen later, let
$\left\\{{p_{i}}\right\\}_{1\leq i\leq N}$ be a maximal $\delta$-packing of
$M_{0}$. From Proposition B.3, this maximal packing has cardinality
$N\geq\frac{\mathcal{H}^{d}(M_{0})}{\omega_{d}(4\delta)^{d}}$.

Let $\eta>0$ be a parameter to be chosen later. Given a family of unit vectors
$\mathbf{w}=(w_{i})_{1\leq i\leq N}\in\left(\mathbb{R}^{n}\right)^{N}$ normal
at the $p_{i}$’s, i.e. $w_{i}\in\left(T_{p_{i}}M\right)^{\perp}$ and
$\left\|w_{i}\right\|=1$, we let $\Phi_{\mathbf{w}}$ be the function defined
in Lemma H.1, that maps any $x\in\mathbb{R}^{n}$ to

$\displaystyle\Phi_{\mathbf{w}}(x)$
$\displaystyle=x+\eta\left(\sum_{i=1}^{N}\phi\left(\frac{x-p_{i}}{\delta}\right)w_{i}\right),$

where $\phi:\mathbb{R}^{n}\to\mathbb{R}$ is the real bump function
$\phi(y)=\exp\left(-{\left\|y\right\|^{2}}/{(1-\left\|y\right\|^{2})}\right)\mathbbm{1}_{\mathrm{B}(0,1)}(y)$
of Lemma H.1. We let $M_{\mathbf{w}}=\Phi_{\mathbf{w}}(M_{0})$ be the image of
$M_{0}$ by $\Phi_{\mathbf{w}}$. The set
$M_{\mathbf{w}}\subseteq\mathbb{R}^{n}$ hence coincides with $M_{0}$, except
in the $\delta$-neighborhoods of the $p_{i}$’s, where it has a bump of size
$\eta$ towards direction $w_{i}$. Note by now that up to rotations of its
coordinates, the vector $\mathbf{w}=(w_{i})_{1\leq i\leq N}$ belongs to
$\mathcal{S}^{n-d}(0,1)^{N}$. Combining Proposition H.1 and Lemma H.1, we see
that $M_{\mathbf{w}}\in\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ and
$\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{\mathbf{w}})\leq
2\mathcal{H}^{d}(M_{0})$ as soon as

$\displaystyle\frac{5\eta}{2\delta}\leq\frac{1}{10d}\text{ and
}\frac{23\eta}{\delta^{2}}\leq\frac{1}{4\mathrm{rch}_{\min}}.$

In the rest of the proof, we will work with these two inequalities holding
true. In particular, because
$\left\|\Phi_{\mathbf{w}}-I_{n}\right\|_{\infty}\leq\eta$, we immediately get
that $\mathrm{d_{H}}(M_{0},M_{\mathbf{w}})\leq\eta$. We note also that all the
$\Phi_{\mathbf{w}}$’s coincide with the identity map on (say)
$M_{0}\cap\partial\mathrm{B}(p_{1},\delta)$, so that
$M_{0}\cap\bigl{(}\cap_{\mathbf{w}}M_{\mathbf{w}}\bigr{)}$ contains
$M_{0}\cap\partial\mathrm{B}(x_{1},\delta)$ and is hence non-empty.

We now take two different families of unit normal vectors $\mathbf{w}$ and
$\mathbf{w}^{\prime}$ (i.e.
$w_{i},w_{i}^{\prime}\in\left(T_{p_{i}}M_{0}\right)^{\perp}$ and
$\left\|w_{i}\right\|=\left\|w_{i}^{\prime}\right\|=1$ for $1\leq i\leq N$),
and we will show that their associated submanifolds $M_{\mathbf{w}}$ and
$M_{\mathbf{w}^{\prime}}$ are far away in Hausdorff distance as soon as
$\max_{1\leq i\leq N}\left\|w_{i}-w_{i}^{\prime}\right\|$ is large enough. To
this aim, we first see that by construction,
$\Phi_{\mathbf{w}}(p_{i})=p_{i}+\eta
w_{i}\in\Phi_{\mathbf{w}}(M_{0})=M_{\mathbf{w}}$ for all
$i\in\left\\{{1,\dots,N}\right\\}$. In particular,

$\displaystyle\mathrm{d_{H}}(M_{\mathbf{w}},M_{\mathbf{w}^{\prime}})$
$\displaystyle\geq\max_{1\leq i\leq N}\mathrm{d}(p_{i}+\eta
w_{i},M_{\mathbf{w}^{\prime}}).$

Let us fix a free parameter $\lambda_{i}\in[0,1]$ to be chosen later. As
$\left\|\Phi_{\mathbf{w^{\prime}}}-I_{n}\right\|_{\infty}\leq\eta$, we can
write for all $i\in\left\\{{1,\dots,N}\right\\}$ that

$\displaystyle\mathrm{d}(p_{i}+\eta w_{i},M_{\mathbf{w}^{\prime}})$
$\displaystyle=\mathrm{d}\left(p_{i}+\eta
w_{i},\Phi_{\mathbf{w}^{\prime}}(M_{0})\right)$
$\displaystyle=\mathrm{d}\left(p_{i}+\eta
w_{i},\Phi_{\mathbf{w}^{\prime}}(M_{0}\setminus\mathrm{B}(p_{i},\lambda_{i}\delta))\right)\wedge\mathrm{d}\bigl{(}p_{i}+\eta
w_{i},\Phi_{\mathbf{w}^{\prime}}(M_{0}\cap\mathrm{B}(p_{i},\lambda_{i}\delta))\bigr{)}$
$\displaystyle\geq(\lambda_{i}\delta-\eta)\wedge\mathrm{d}\bigl{(}p_{i}+\eta
w_{i},\Phi_{\mathbf{w}^{\prime}}(M_{0}\cap\mathrm{B}(p_{i},\lambda_{i}\delta))\bigr{)}.$

Further investigating the term $\mathrm{d}\left(p_{i}+\eta
w_{i},\Phi_{\mathbf{w}^{\prime}}(M_{0}\cap\mathrm{B}(p_{i},\lambda_{i}\delta))\right)$,
we see that for all $x\in
M_{0}\cap\mathrm{B}(p_{i},\lambda_{i}\delta)\subseteq\mathrm{B}(p_{i},\delta)$,
$\Phi_{\mathbf{w}^{\prime}}(x)=x+\eta\phi\left(\frac{x-p_{i}}{\delta}\right)w_{i}$.
But from [Fed59, Theorem 4.18], $\mathrm{rch}_{M_{0}}\geq
2\mathrm{rch}_{\min}$ ensures that any $x\in
M_{0}\cap\mathrm{B}(p_{i},\lambda_{i}\delta)$ can be written as $x=p_{i}+v+u$,
where $v\in T_{p_{i}}M_{0}$ with $\left\|v\right\|\leq\lambda_{i}\delta$, and
$u\in\bigl{(}T_{p_{i}}M_{0}\bigr{)}^{\perp}$ with
$\left\|u\right\|\leq(\lambda_{i}\delta)^{2}/(4\mathrm{rch}_{\min})$. As a
result, we have

$\displaystyle\mathrm{d}$ $\displaystyle\left(p_{i}+\eta
w_{i},\Phi_{\mathbf{w}^{\prime}}(M_{0}\cap\mathrm{B}(p_{i},\lambda_{i}\delta))\right)$
$\displaystyle\geq\min_{\begin{subarray}{c}v\in
T_{p_{i}}M_{0},\left\|v\right\|\leq\lambda_{i}\delta\\\
u\in(T_{p_{i}}M_{0})^{\perp},\left\|u\right\|\leq(\lambda_{i}\delta)^{2}/(4\mathrm{rch}_{\min})\end{subarray}}\left\|v+u+\eta\left(\phi\left(\frac{v+u}{\delta}\right)w^{\prime}_{i}-w_{i}\right)\right\|.$

But in the above minimum, $v$ is orthogonal to $u,w_{i}$ and $w_{i}^{\prime}$,
so

$\displaystyle\left\|v+u+\eta\left(\phi\left(\frac{v+u}{\delta}\right)w^{\prime}_{i}-w_{i}\right)\right\|\geq\left\|u+\eta\left(\phi\left(\frac{v+u}{\delta}\right)w^{\prime}_{i}-w_{i}\right)\right\|.$

Additionally, $\phi\left(\frac{v+u}{\delta}\right)$ ranges in (a subset of)
$[0,1]$ since $0\leq\phi\leq 1$. In particular,

$\displaystyle\mathrm{d}\left(p_{i}+\eta
w_{i},\Phi_{\mathbf{w}^{\prime}}(M_{0}\cap\mathrm{B}(p_{i},\lambda_{i}\delta))\right)$
$\displaystyle\geq\min_{\begin{subarray}{c}u\in(T_{p_{i}}M_{0})^{\perp},\left\|u\right\|\leq(\lambda_{i}\delta)^{2}/(4\mathrm{rch}_{\min})\\\
0\leq t\leq
1\end{subarray}}\left\|u+\eta\left(tw^{\prime}_{i}-w_{i}\right)\right\|$
$\displaystyle\geq\min_{0\leq t\leq
1}\eta\left\|tw^{\prime}_{i}-w_{i}\right\|-\frac{(\lambda_{i}\delta)^{2}}{4\mathrm{rch}_{\min}}$
$\displaystyle=\eta\left\|\left(0\vee\left\langle{w_{i}},{w^{\prime}_{i}}\right\rangle\right)w^{\prime}_{i}-w_{i}\right\|-\frac{(\lambda_{i}\delta)^{2}}{4\mathrm{rch}_{\min}}$
$\displaystyle\geq\eta\frac{\left\|w^{\prime}_{i}-w_{i}\right\|}{2}-\frac{(\lambda_{i}\delta)^{2}}{4\mathrm{rch}_{\min}},$

where the second line follows from triangle inequality, and the last two from
elementary calculations. Putting everything together, we have shown that for
all $\lambda_{1},\dots,\lambda_{N}\in[0,1]$,

$\displaystyle\mathrm{d_{H}}(M_{\mathbf{w}},M_{\mathbf{w}^{\prime}})$
$\displaystyle\geq\max_{1\leq i\leq
N}\left\\{{(\lambda_{i}\delta-\eta)\wedge\left(\eta\frac{\left\|w^{\prime}_{i}-w_{i}\right\|}{2}-\frac{(\lambda_{i}\delta)^{2}}{4\mathrm{rch}_{\min}}\right)}\right\\}.$

One easily checks that under the above assumptions on the parameters,

$\lambda_{i}:=\frac{\sqrt{\sqrt{2}\mathrm{rch}_{\min}\left\|w^{\prime}_{i}-w_{i}\right\|\eta}}{\delta}$

provides valid choices of $\lambda_{i}\in[0,1]$. Plugging these values in the
previous bound yields

$\displaystyle\mathrm{d_{H}}(M_{\mathbf{w}},M_{\mathbf{w}^{\prime}})$
$\displaystyle\geq\max_{1\leq i\leq
N}\left\\{{\left(\sqrt{\sqrt{2}\mathrm{rch}_{\min}\left\|w^{\prime}_{i}-w_{i}\right\|\eta}-\eta\right)\wedge\left(\eta\frac{\left\|w^{\prime}_{i}-w_{i}\right\|}{8}\right)}\right\\},$

so that if we further assume that $\left\|w^{\prime}_{i}-w_{i}\right\|\geq
4\sqrt{2}\eta/\mathrm{rch}_{\min}$, we obtain

$\displaystyle\mathrm{d_{H}}(M_{\mathbf{w}},M_{\mathbf{w}^{\prime}})$
$\displaystyle\geq\max_{1\leq i\leq
N}\left\\{{\eta\wedge\left(\eta\frac{\left\|w^{\prime}_{i}-w_{i}\right\|}{8}\right)}\right\\}$
$\displaystyle=\frac{\eta}{8}\max_{1\leq i\leq
N}\left\|w^{\prime}_{i}-w_{i}\right\|,$

where the last line follows from
$\left\|w_{i}-w^{\prime}_{i}\right\|\leq\left\|w_{i}\right\|+\left\|w^{\prime}_{i}\right\|\leq
2$.

Setting $\eta=\delta^{2}/(92\mathrm{rch}_{\min})$, which is a value that
satisfies all the requirements above as soon as
$\delta\leq\mathrm{rch}_{\min}/(2300d)$, we have built a family of
submanifolds $\left\\{{M_{\mathbf{w}}}\right\\}_{\mathbf{w}}$ of
$\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ indexed by
$\mathbf{w}\in\mathcal{S}^{n-d}(0,1)^{N}$, such that
$\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{\mathbf{w}})\leq
2\mathcal{H}^{d}(M_{0})$, and which are guaranteed to satisfy

$\displaystyle\mathrm{d_{H}}(M_{\mathbf{w}},M_{\mathbf{w}^{\prime}})$
$\displaystyle>\frac{\delta^{2}}{8(92\mathrm{rch}_{\min})}\times\frac{1}{4}\geq
2\left(\frac{\delta^{2}}{2082\mathrm{rch}_{\min}}\right),$

provided that $\max_{1\leq i\leq
N}\left\|w^{\prime}_{i}-w_{i}\right\|>1/4=2/8$. As a result, if we consider
$(1/8)$-packings of the unit spheres
$\mathcal{S}_{(T_{p_{i}}M_{0})^{\perp}}(0,1)=\mathcal{S}^{n-d}(0,1)$ for
$i\in\left\\{{1,\dots,N}\right\\}$, then for all
$\delta\leq\mathrm{rch}_{\min}/(2300d)$, it naturally defines a
$\left(\frac{\delta^{2}}{2082\mathrm{rch}_{\min}}\right)$-packing of
$\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ with cardinality $\mathcal{N}$ a
least

$\displaystyle\mathcal{N}$
$\displaystyle\geq\mathrm{pk}_{\mathcal{S}^{n-d}(0,1)}(1/8)^{N}\geq\mathrm{pk}_{\mathcal{S}^{n-d}(0,1)}(1/8)^{\frac{\mathcal{H}^{d}(M_{0})}{\omega_{d}(4\delta)^{d}}},$

and which consists of elements $M_{\mathbf{w}}$ such that
$\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{\mathbf{w}})\leq
2\mathcal{H}^{d}(M_{0})$ and
$\mathrm{d_{H}}(M_{0},M_{\mathbf{w}})\leq\eta=\delta^{2}/(92\mathrm{rch}_{\min})$.
In particular, by setting $r=\frac{\delta^{2}}{2082\mathrm{rch}_{\min}}$, then
for all $0<r\leq\mathrm{rch}_{\min}/(2^{34}d^{2})$, we have exhibited a
$r$-packing of $\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ of cardinality
$\mathcal{N}$ with

$\displaystyle\log\mathcal{N}$
$\displaystyle\geq\frac{\mathcal{H}^{d}(M_{0})}{\omega_{d}(4\sqrt{2082\mathrm{rch}_{\min}r})^{d}}\log\mathrm{pk}_{\mathcal{S}^{n-d}(0,1)}(1/8),$

composed of submanifolds having volume as above, and
$\mathrm{d_{H}}(M_{0},M_{\mathbf{w}})\leq 2082r/92\leq 23r$. From Proposition
B.4, $\log\mathrm{pk}_{\mathcal{S}^{n-d}(0,1)}(1/8)\geq(n-d)\log 2$. Finally,
by considering the cases $d\leq n/2$ and $d\geq n/2$, one easily checks that
$(n-d)\geq n/(2d)$. In all, we obtain the announced bound

$\displaystyle\log\mathcal{N}$
$\displaystyle\geq\frac{\mathcal{H}^{d}(M_{0})}{\omega_{d}(4\sqrt{2082\mathrm{rch}_{\min}r})^{d}}\frac{n\log
2}{2d}$ $\displaystyle\geq
n\frac{\mathcal{H}^{d}(M_{0})}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{19}r}\right)^{d/2},$

which yields the announced result. ∎

Applying the technique of Proposition H.5 with manifolds $M_{0}$ having a
large prescribed volume
$\left\\{{0}\right\\}\sqcup\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ and
$\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$
respectively yields the following result.

######  Proposition H.6.

Let $\mathcal{V}>0$ and $\varepsilon\leq\mathrm{rch}_{\min}/(2^{34}d^{2})$.

  * •

Assume that

$1\leq\frac{\mathcal{V}}{2^{d+1}\sigma_{d}\mathrm{rch}_{\min}^{d}}.$

Then,

$\displaystyle\log\mathrm{pk}_{\bigl{(}\left\\{{0}\right\\}\sqcup\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}}(\varepsilon)\geq
n\frac{\mathcal{V}}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{21}\varepsilon}\right)^{d/2}.$

Furthermore, this packing can be chosen so that all its elements $M$ satisfy

$\mathcal{V}/4\leq\mathcal{H}^{d}(M)\leq\mathcal{V}.$

  * •

Assume that $\mathrm{rch}_{\min}\leq R/144$. Writing
$C_{d}^{\prime}=9(2^{2d+1}\sigma_{d-1})$, assume that

$1\leq\frac{\mathcal{V}}{2^{d+1}C_{d}^{\prime}\mathrm{rch}_{\min}^{d}}\leq\max_{1\leq
k\leq n}\left(\frac{R}{192\mathrm{rch}_{\min}\sqrt{k}}\right)^{k}.$

Then,

$\displaystyle\log\mathrm{pk}_{\bigl{(}\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}}(\varepsilon)\geq
n\frac{\mathcal{V}}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{31}\varepsilon}\right)^{d/2}.$

Furthermore, this packing can be chosen so that all its elements $M$ satisfy

$\mathcal{V}/96\leq\mathcal{H}^{d}(M)\leq\mathcal{V}.$

###### Proof of Proposition H.6.

For both models, the idea is to first build a manifold
$M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$ with prescribed volume
close to $\mathcal{V}$, and then consider the variations of it given by
Proposition H.5.

  * •

Let $M_{0}$ be the centered $d$-dimensional sphere of radius
$r_{0}=\left(\frac{\mathcal{V}/2}{\sigma_{d}}\right)^{1/d}$ in
$\mathbb{R}^{d+1}\times\left\\{{0}\right\\}^{n-(d+1)}\subseteq\mathbb{R}^{n}$.
By construction, $\mathrm{rch}_{M_{0}}=r_{0}\geq 2\mathrm{rch}_{\min}$, so
that $M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$. Furthermore, one
easily checks that $\mathcal{H}^{d}(M_{0})=\mathcal{V}/2$. From Proposition
H.5, there exists a family of submanifolds $\left\\{{M_{s}}\right\\}_{1\leq
s\leq\mathcal{N}}\subseteq\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ with
cardinality $\mathcal{N}$ such that

$\displaystyle\log\mathcal{N}$ $\displaystyle\geq
n\frac{\mathcal{V}/2}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{19}\varepsilon}\right)^{d/2}$
$\displaystyle\geq
n\frac{\mathcal{V}}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{21}\varepsilon}\right)^{d/2},$

that all share a point $x_{0}\in\cap_{1\leq s\leq\mathcal{N}}M_{s}$, and such
that $\mathrm{d_{H}}(M_{s},M_{s^{\prime}})>2\varepsilon$ for all $s\neq
s^{\prime}\in\left\\{{1,\dots,\mathcal{N}}\right\\}$, with volumes
$\mathcal{V}/4=\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{s})\leq
2\mathcal{H}^{d}(M_{0})=\mathcal{V}$. As a result, the family given by the
translations $M^{\prime}_{s}=M_{s}-x_{0}$ clearly provides the existence of
the announced $\varepsilon$-packing of
$\bigl{(}\left\\{{0}\right\\}\sqcup\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}$.

  * •

Let $M_{0}\subseteq\mathbb{R}^{n}$ be a submanifold given by Proposition H.2
applied with parameters $\mathrm{rch}_{\min}^{\prime}=2\mathrm{rch}_{\min}$,
$\mathcal{V}^{\prime}=\mathcal{V}/2$ and $R^{\prime}=R/2$. That is,
$M_{0}\in\mathcal{M}^{{n},{d}}_{2\mathrm{rch}_{\min}}$ is such that
$\mathcal{V}/48\leq\mathcal{H}^{d}(M_{0})\leq\mathcal{V}/2$ and
$M_{0}\subseteq\mathrm{B}(0,R/2)$. From Proposition H.5, there exists a family
of submanifolds $\left\\{{M_{s}}\right\\}_{1\leq
s\leq\mathcal{N}}\subseteq\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ with
cardinality $\mathcal{N}$ such that

$\displaystyle\log\mathcal{N}$ $\displaystyle\geq
n\frac{\mathcal{V}/48}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{19}\varepsilon}\right)^{d/2}$
$\displaystyle\geq
n\frac{\mathcal{V}}{\omega_{d}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{31}\varepsilon}\right)^{d/2},$

with $\mathrm{d_{H}}(M_{0},M_{s})\leq 23\varepsilon$ and
$\mathrm{d_{H}}(M_{s},M_{s^{\prime}})>2\varepsilon$ for all $s\neq
s^{\prime}\in\left\\{{1,\dots,\mathcal{N}}\right\\}$, and volumes
$\mathcal{V}/96\leq\mathcal{H}^{d}(M_{0})/2\leq\mathcal{H}^{d}(M_{s})\leq
2\mathcal{H}^{d}(M_{0})\leq\mathcal{V}$. Because
$M_{0}\subseteq\mathrm{B}(0,R/2)$ and $\mathrm{d_{H}}(M_{0},M_{s})\leq
23\varepsilon$ for all $s\in\left\\{{1,\dots,\mathcal{N}}\right\\}$, we
immediately get that
$M_{s}\subseteq\mathrm{B}(0,R/2+23\varepsilon)\subseteq\mathrm{B}(0,R)$. As a
result, this family clearly provides the existence of the announced
$\varepsilon$-packing of
$\bigl{(}\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},\mathrm{d_{H}}\bigr{)}$.

∎

####  H.4.3 Proof of the Computational Lower Bounds for Manifold Estimation

We are now in position to prove the computational lower bounds presented in
this work. First, we turn to the infeasibiliy result of manifold estimation
using statistical queries in the unbounded model
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
(Proposition 2.1).

###### Proof of Proposition 2.1.

Since $\sigma_{d}f_{\min}\mathrm{rch}_{\min}^{d}\leq 1$, the uniform
probability distribution $D_{0}$ over the centered unit $d$-sphere
$M_{0}\subseteq\mathbb{R}^{d+1}\times\left\\{{0}\right\\}^{n-(d+1)}$ of radius
$\mathrm{rch}_{\min}$ belongs to
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$.
Given a unit vector $v\in\mathbb{R}^{n}$, the invariance of the model by
translation yields that the uniform distributions $D_{k}$ over
$M_{k}=\left\\{{p+(3k\varepsilon)v,p\in M_{0}}\right\\}$, for
$k\in\mathbb{Z}$, also belong to
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$. But
for all $k\neq k^{\prime}\in\mathbb{Z}$,
$\mathrm{d_{H}}(M_{k},M_{k^{\prime}})=3|k-k^{\prime}|\varepsilon>2\varepsilon$.
Hence, writing

$\mathcal{M}=\left\\{{\mathrm{Supp}(D),D\in\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})}\right\\},$

we see that the family $\left\\{{M_{k}}\right\\}_{k\in\mathbb{Z}}$ forms an
infinite $\varepsilon$-packing of $(\mathcal{M},\mathrm{d_{H}})$. From Theorem
G.2, we get that the statistical query complexity of manifold estimation over
the model
$\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$ with
precision $\varepsilon$ is infinite, which concludes the proof. ∎

We finally come to the proofs of the computational lower bounds over the fixed
point model
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
(Theorem 5.3) and the bounding ball model
$\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
(Theorem 5.6).

###### Proof of Theorem 5.3 and Theorem 5.6.

For both results, the idea is to exhibit large enough $\varepsilon$-packings
of $\mathcal{M}=\left\\{{\mathrm{Supp}(D),D\in\mathcal{D}}\right\\}$, and
apply Theorem G.2. In each case, the assumptions on the parameters
$f_{\min},f_{\max}$, $\mathrm{rch}_{\min}$ and $d$ ensure that the uniform
distributions over the manifolds given by the packings of Proposition H.6 (and
Proposition H.4 for Theorem 5.6) applied with $\mathcal{V}=1/f_{\min}$ belong
to the model, and hence that $\mathcal{M}$ contain these packings.

  * •

To prove Theorem 5.3, let us write

$\mathcal{M}_{0}:=\left\\{{\mathrm{Supp}(D),D\in\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})}\right\\}\subseteq\left\\{{0}\right\\}\sqcup\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}.$

From Theorem G.2, any randomized SQ algorithm estimating $M=\mathrm{Supp}(D)$
over the model
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$
with precision $\varepsilon$ and with probability of success at least
$1-\alpha$ must make at least

$q\geq\frac{\log\bigl{(}(1-\alpha)\mathrm{pk}_{(\mathcal{M}_{0},\mathrm{d_{H}})}(\varepsilon)\bigr{)}}{\log(1+\left\lfloor
1/\tau\right\rfloor)}$

queries to $\mathrm{STAT}(\tau)$. Furthermore, let
$\left\\{{M_{i}}\right\\}_{1\leq i\leq\mathcal{N}}$ be an
$\varepsilon$-packing of
$\left\\{{0}\right\\}\sqcup\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}}$ given
by Proposition H.6, that we apply with volume $\mathcal{V}=1/f_{\min}$. Recall
that these manifolds are guaranteed to have volumes
$1/(4f_{\min})\leq\mathcal{H}^{d}(M_{i})\leq 1/f_{\min}$. From the assumptions
on the parameters of the model, we get that the uniform distributions
$\left\\{{D_{i}:=\mathbbm{1}_{M_{i}}\mathcal{H}^{d}/\mathcal{H}^{d}(M_{i})}\right\\}_{1\leq
i\leq\mathcal{N}}$ over the $M_{i}$’s all belong to
$\left\\{{0}\right\\}\sqcup\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})$.
In particular, the family $\left\\{{M_{i}}\right\\}_{1\leq i\leq\mathcal{N}}$
is also an $\varepsilon$-packing of $\mathcal{M}_{0}$, and therefore

$\displaystyle\log\bigl{(}\mathrm{pk}_{(\mathcal{M}_{0},\mathrm{d_{H}})}(\varepsilon)\bigr{)}$
$\displaystyle\geq\log\mathcal{N}\geq
n\frac{1}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{21}\varepsilon}\right)^{d/2},$

which yields the announced result.

  * •

Similarly, to prove Theorem 5.6, write

$\mathcal{M}_{R}:=\left\\{{\mathrm{Supp}(D),D\in\mathrm{B}(0,R)\sqcap\mathcal{D}^{{n},{d}}_{\mathrm{rch}_{\min}}({f_{\min}},{f_{\max}},{L})}\right\\}\subseteq\mathrm{B}(0,R)\sqcap\mathcal{M}^{{n},{d}}_{\mathrm{rch}_{\min}},$

and apply Theorem G.2 to get

$q\geq\frac{\log\bigl{(}(1-\alpha)\mathrm{pk}_{(\mathcal{M}_{R},\mathrm{d_{H}})}(\varepsilon)\bigr{)}}{\log(1+\left\lfloor
1/\tau\right\rfloor)}.$

The assumptions on the parameters ensure that the packings exhibited in
Proposition H.4 and Proposition H.6 applied with volume
$\mathcal{V}=1/f_{\min}$ are included in $\mathcal{M}_{R}$, so that

$\displaystyle\log\bigl{(}\mathrm{pk}_{(\mathcal{M}_{R},\mathrm{d_{H}})}(\varepsilon)\bigr{)}$
$\displaystyle\geq
n\max\left\\{{\log\left(\frac{R}{4\varepsilon}\right),\frac{1}{\omega_{d}f_{\min}\mathrm{rch}_{\min}^{d}}\left(\frac{\mathrm{rch}_{\min}}{2^{31}\varepsilon}\right)^{d/2}}\right\\},$

which concludes the proof.

∎

## References

  * [ACLZ17] Ery Arias-Castro, Gilad Lerman, and Teng Zhang.  Spectral clustering based on local PCA.  J. Mach. Learn. Res., 18:Paper No. 9, 57, 2017.
  * [ACP13] Ery Arias-Castro and Bruno Pelletier.  On the convergence of maximum variance unfolding.  J. Mach. Learn. Res., 14:1747–1770, 2013.
  * [AGY20] Srinivasan Arunachalam, Alex B. Grilo, and Henry Yuen.  Quantum statistical query learning.  CoRR, abs/2002.08240, 2020.
  * [AK21] Eddie Aamari and Alexander Knop.  Statistical query complexity of manifold estimation.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, page 116–122, New York, NY, USA, 2021. Association for Computing Machinery.
  * [AKC+19] Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, and Larry Wasserman.  Estimating the reach of a manifold.  Electron. J. Stat., 13(1):1359–1399, 2019.
  * [AL18] Eddie Aamari and Clément Levrard.  Stability and minimax optimality of tangential Delaunay complexes for manifold reconstruction.  Discrete Comput. Geom., 59(4):923–971, 2018.
  * [AL19] Eddie Aamari and Clément Levrard.  Nonasymptotic rates for manifold, tangent space and curvature estimation.  Ann. Statist., 47(1):177–204, 2019.
  * [Alm86] F. Almgren.  Optimal isoperimetric inequalities.  Indiana Univ. Math. J., 35(3):451–547, 1986.
  * [AS21] Yariv Aizenbud and Barak Sober.  Non-Parametric Estimation of Manifolds from Noisy Data.  arXiv e-prints, page arXiv:2105.04754, May 2021.
  * [BBI01] Dmitri Burago, Yuri Burago, and Sergei Ivanov.  A course in metric geometry, volume 33 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2001.
  * [BD98] Shai Ben-David and Eli Dichterman.  Learning with restricted focus of attention.  J. Comput. Syst. Sci., 56(3):277–298, 1998.
  * [BFJ+94] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, and Steven Rudich.  Weakly learning DNF and characterizing statistical query learning using fourier analysis.  In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94, page 253–262, New York, NY, USA, 1994. Association for Computing Machinery.
  * [BG14] Jean-Daniel Boissonnat and Arijit Ghosh.  Manifold reconstruction using tangential Delaunay complexes.  Discrete Comput. Geom., 51(1):221–267, 2014.
  * [BHHS22] Clément Berenfeld, John Harvey, Marc Hoffmann, and Krishnan Shankar.  Estimating the reach of a manifold via its convexity defect function.  Discrete Comput. Geom., 67(2):403–438, 2022.
  * [BKW19] Jean-Daniel Boissonnat, Siargey Kachanovich, and Mathijs Wintraecken.  Sampling and Meshing Submanifolds in High Dimension.  working paper or preprint, November 2019.
  * [BLW19] Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken.  The reach, metric distortion, geodesic convexity and the variation of tangent spaces.  J. Appl. Comput. Topol., 3(1-2):29–58, 2019.
  * [Byl94] Tom Bylander.  Learning linear threshold functions in the presence of classification noise.  In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, COLT 1994, New Brunswick, NJ, USA, July 12-15, 1994, pages 340–347, 1994.
  * [CF97] Antonio Cuevas and Ricardo Fraiman.  A plug-in approach to support estimation.  Ann. Statist., 25(6):2300–2312, 1997.
  * [dC92] Manfredo Perdigão do Carmo.  Riemannian geometry.  Mathematics: Theory & Applications. Birkhäuser Boston, Inc., Boston, MA, 1992.  Translated from the second Portuguese edition by Francis Flaherty.
  * [Dey07] Tamal K. Dey.  Curve and surface reconstruction: algorithms with mathematical analysis, volume 23 of Cambridge Monographs on Applied and Computational Mathematics.  Cambridge University Press, Cambridge, 2007.
  * [DFT+15] Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, and Karl Wimmer.  Approximate resilience, monotonicity, and the complexity of agnostic learning.  In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 498–511. SIAM, 2015.
  * [Div21a] Vincent Divol.  Minimax adaptive estimation in manifold inference.  Electron. J. Stat., 15(2):5888–5932, 2021.
  * [Div21b] Vincent Divol.  Reconstructing measures on manifolds: an optimal transport approach.  arXiv e-prints, page arXiv:2102.07595, February 2021.
  * [DKS17] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart.  Statistical query lower bounds for robust estimation of high-dimensional gaussians and gaussian mixtures.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 73–84. IEEE Computer Society, 2017.
  * [DMGZ94] Giuseppe De Marco, Gianluca Gorni, and Gaetano Zampieri.  Global inversion of functions: an introduction.  NoDEA Nonlinear Differential Equations Appl., 1(3):229–248, 1994\.
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In Theory of cryptography, volume 3876 of Lecture Notes in Comput. Sci., pages 265–284. Springer, Berlin, 2006.
  * [DV08] John Dunagan and Santosh S. Vempala.  A simple polynomial-time rescaling algorithm for solving linear programs.  Math. Program., 114(1):101–114, 2008.
  * [DW21] David B Dunson and Nan Wu.  Inferring Manifolds From Noisy Data Using Gaussian Processes.  arXiv e-prints, page arXiv:2110.07478, October 2021.
  * [EGS03] Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant.  Limiting privacy breaches in privacy preserving data mining.  In Proceedings of the Twenty-Second ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 9-12, 2003, San Diego, CA, USA, pages 211–222. ACM, 2003.
  * [FCRP08] Maryam Fazel, Emmanuel Candès, Benjamin Recht, and Pablo Parrilo.  Compressed sensing and robust recovery of low rank matrices.  In in Proc. 40th Asilomar Conf. Signals, Systems and Computers, 2008\.
  * [Fed59] Herbert Federer.  Curvature measures.  Trans. Amer. Math. Soc., 93:418–491, 1959.
  * [Fed69] Herbert Federer.  Geometric measure theory.  Die Grundlehren der mathematischen Wissenschaften, Band 153. Springer-Verlag New York Inc., New York, 1969.
  * [Fel17] Vitaly Feldman.  A general characterization of the statistical query complexity.  In Proceedings of Machine Learning Research, volume 65, pages 785–830, Amsterdam, Netherlands, 2017.
  * [FGR+17] Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, and Ying Xiao.  Statistical algorithms and a lower bound for detecting planted cliques.  J. ACM, 64(2):8:1–8:37, 2017.
  * [FGV21] Vitaly Feldman, Cristóbal Guzmán, and Santosh Vempala.  Statistical query algorithms for mean vector estimation and stochastic convex optimization.  Math. Oper. Res., 46(3):912–945, 2021.
  * [FILN19] Charles Fefferman, Sergei Ivanov, Matti Lassas, and Hariharan Narayanan.  Fitting a manifold of large reach to noisy data.  arXiv e-prints, page arXiv:1910.05084, October 2019.
  * [FPV18] Vitaly Feldman, Will Perkins, and Santosh S. Vempala.  On the complexity of random satisfiability problems with planted solutions.  SIAM J. Comput., 47(4):1294–1338, 2018.
  * [GPPVW12a] Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman.  Manifold estimation and singular deconvolution under Hausdorff loss.  Ann. Statist., 40(2):941–963, 2012.
  * [GPPVW12b] Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman.  Minimax manifold estimation.  J. Mach. Learn. Res., 13:1263–1291, 2012.
  * [Hat02] Allen Hatcher.  Algebraic topology.  Cambridge University Press, Cambridge, 2002.
  * [HTF09] Trevor Hastie, Robert Tibshirani, and Jerome Friedman.  The elements of statistical learning.  Springer Series in Statistics. Springer, New York, second edition, 2009\.  Data mining, inference, and prediction.
  * [Jar19] DR. Ron Jarmin.  Census bureau adopts cutting edge privacy protections for 2020 census, 2019.  available at https://www.census.gov/newsroom/blogs/random-samplings/2019/02/census_bureau_adopts.html.
  * [JNS18] Noah M. Johnson, Joseph P. Near, and Dawn Song.  Towards practical differential privacy for SQL queries.  Proc. VLDB Endow., 11(5):526–539, 2018.
  * [Kea98] Michael J. Kearns.  Efficient noise-tolerant learning from statistical queries.  J. ACM, 45(6):983–1006, 1998.
  * [KLN+11] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith.  What can we learn privately?  SIAM J. Comput., 40(3):793–826, 2011.
  * [KZ15] Arlene K. H. Kim and Harrison H. Zhou.  Tight minimax rates for manifold estimation under Hausdorff loss.  Electron. J. Stat., 9(1):1562–1582, 2015.
  * [LC87] William E. Lorensen and Harvey E. Cline.  Marching cubes: A high resolution 3d surface construction algorithm.  In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH ’87, page 163–169, New York, NY, USA, 1987. Association for Computing Machinery.
  * [Liu11] Yi-Kai Liu.  Universal low-rank matrix recovery from pauli measurements.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
  * [LV07] John A. Lee and Michel Verleysen.  Nonlinear dimensionality reduction.  Information Science and Statistics. Springer, New York, 2007.
  * [NSW08] Partha Niyogi, Stephen Smale, and Shmuel Weinberger.  Finding the homology of submanifolds with high confidence from random samples.  Discrete Comput. Geom., 39(1-3):419–441, 2008.
  * [PS22] Nikita Puchkin and Vladimir Spokoiny.  Structure-adaptive manifold estimation.  Journal of Machine Learning Research, 23(40):1–62, 2022.
  * [RS00] Sam T. Roweis and Lawrence K. Saul.  Nonlinear dimensionality reduction by locally linear embedding.  Science, 290(5500):2323–2326, 2000.
  * [RSP+20] Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad.  Linkedin’s audience engagements API: A privacy preserving data analytics system at scale.  CoRR, abs/2002.05839, 2020.
  * [She08] Alexander A. Sherstov.  Halfspace matrices.  Comput. Complex., 17(2):149–178, 2008.
  * [SVW16] Jacob Steinhardt, Gregory Valiant, and Stefan Wager.  Memory, communication, and statistical queries.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 1490–1516. JMLR.org, 2016.
  * [Ten97] Joshua B. Tenenbaum.  Mapping a manifold of perceptual observations.  In Michael I. Jordan, Michael J. Kearns, and Sara A. Solla, editors, Advances in Neural Information Processing Systems 10, [NIPS Conference, Denver, Colorado, USA, 1997], pages 682–688. The MIT Press, 1997\.
  * [Val84] Leslie G. Valiant.  A theory of the learnable.  Commun. ACM, 27(11):1134–1142, 1984.
  * [Ver90] Karsten A. Verbeurgt.  Learning DNF under the uniform distribution in quasi-polynomial time.  In Mark A. Fulk and John Case, editors, Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT 1990, University of Rochester, Rochester, NY, USA, August 6-8, 1990, pages 314–326. Morgan Kaufmann, 1990.
  * [Wai14] Martin J. Wainwright.  Constrained forms of statistical minimax: computation, communication, and privacy.  In Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, pages 273–290. Kyung Moon Sa, Seoul, 2014.
  * [War65] Stanley L. Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  Journal of the American Statistical Association, 60(309):63–69, 1965.
  * [Was18] Larry Wasserman.  Topological data analysis.  Annu. Rev. Stat. Appl., 5:501–535, 2018.
  * [Yu97] Bin Yu.  Assouad, fano, and le cam.  In Festschrift for Lucien Le Cam, pages 423–435. Springer, 1997\.
  * [YWS15] Y. Yu, T. Wang, and R. J. Samworth.  A useful variant of the Davis-Kahan theorem for statisticians.  Biometrika, 102(2):315–323, 2015.