k-1}|\det(A[\ell_{1},\ell_{2},\ldots,\ell_{k}])||\det(C[\ell_{1},\ell_{2},\ldots,\ell_{k}])|$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{0\leq\ell_{1}<\ell_{2}<\ldots<\ell_{k},\ell_{k}\neq
k-1}(k!)^{2}B^{k}(10\delta k^{2})^{\sum_{i=1}^{k}\ell_{i}}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{\tau=1+2+\ldots+(k-3)+(k-2)+k}^{\infty}\tau^{k}(k!)^{2}B^{k}(10\delta
k^{2})^{\tau}$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
2\tau_{0}^{k}(k!)^{2}B^{k}(10\delta k^{2})^{\tau_{0}},$

where $\tau_{0}=\binom{k}{2}+1$. This completes part (2). Now, we do part (3).
By Lemma 5.17,

$\displaystyle|\det(M)|$
$\displaystyle\geq|\det(A[0,1,\ldots,k-1])||\det(C[0,1,\ldots,k-1])|$
$\displaystyle-\sum_{0\leq\ell_{1}<\ell_{2}<\ldots<\ell_{k},\ell_{k}\neq
k-1}|\det(A[\ell_{1},\ldots,\ell_{k}])||\det(C[\ell_{1},\ldots,\ell_{k}])|$

Plugging in the part (1) lower bound and the part (2) upper bound yields

$\displaystyle|\det(M)|$
$\displaystyle\geq\delta^{\tau_{0}-1}\rho(k)^{k}-2\tau_{0}^{k}(k!)^{2}B^{k}(10\delta
k^{2})^{\tau_{0}}$
$\displaystyle=\delta^{\tau_{0}-1}\left(\rho(k)^{k}-2\delta\tau_{0}^{k}(k!)^{2}B^{k}(10k^{2})^{\tau_{0}}\right)$
$\displaystyle>\delta^{\tau_{0}-1}\rho(k)^{k}/2$
$\displaystyle>\rho(k)^{k}(\rho(k)/(Bk^{2}(200k)^{k}))^{10k^{3}}$

as desired. ∎

######  Lemma 5.24 (Step 5: Cramer’s rule-based bound on error in linear
system).

Let $M$ be an invertible $k$ by $k$ matrix with $|M_{ij}|\leq B$ for all
$i,j\in[k]$. Let $b$ be a $k$-dimensional vector for which
$|b_{i}|\leq\varepsilon$ for all $i\in[k]$. Then,
$\|M^{-1}b\|_{\infty}\leq\varepsilon k!B^{k}/|\det(M)|$.

###### Proof.

Cramer’s rule says that, for each $i\in[k]$, the entry $i$ of the vector
$M^{-1}b$ is given by

$(M^{-1}b)_{i}=\frac{\det(M_{i})}{\det(M)},$

where $M_{i}$ is the matrix which one gets by replacing column $i$ of $M$ by
$b$. Let us upper-bound $|\det(M_{i})|$. We are given that each entry of
$M_{i}$ in column $i$ has magnitude at most $\varepsilon$, and each entry in
every other column has magnitude at most $B$. Hence, for any permutation
$\sigma\in S_{k}$ on $[k]$, we have

$\left|\prod_{j=1}^{k}(M_{i})_{j,\sigma(j)}\right|\leq\varepsilon\cdot
B^{k-1},$

and so

$|\det(M_{i})|\leq\sum_{\sigma\in
S_{k}}\left|\prod_{j=1}^{k}(M_{i})_{j,\sigma(j)}\right|\leq\varepsilon\cdot
B^{k-1}\cdot k!.$

It follows from Cramer’s rule that $|(M^{-1}b)_{i}|\leq\varepsilon\cdot
B^{k-1}\cdot k!/|\det(M)|$, as desired. ∎

######  Lemma 5.25 (Step 6: reduction).

Let $f:[0,1]\to{\mathbb{R}}$ be an analytic function on $[0,1]$, let
$\kappa:{\mathbb{N}}\to[0,1]$ be a nonincreasing function, and let
$\rho(\ell)=\left[\kappa(\ell)^{2}/(64B\ell
4^{2\ell+1}\cdot\ell!)\right]^{\ell+2}$ for any $\ell\in{\mathbb{N}}$ (as
discussed before). Suppose that, for infinitely many positive integers $k$,
there exists an $x_{k}$ for which $|f^{(k+1)}(x)|>\kappa(k)$.

Suppose that there is an algorithm for $\varepsilon$-approximate matrix-vector
multiplication by an $n\times n$ $f$-matrix for points in $[0,1]^{d}$ in
$T(n,d,\varepsilon)$ time. Then, there is a

$\displaystyle n\cdot\mathrm{poly}(d+\log(1/\kappa(d+1)))+O(d\cdot
T(2n,d+1,(\kappa(d+1))^{O(d^{4})})))$

time algorithm for exact bichromatic Hamming nearest neighbors on $n$-point
sets in dimension $d$.

###### Proof.

Let $x_{1},\ldots,x_{n}\in\\{0,1\\}^{d}$ be the input to the Hamming nearest
neighbors problem, so our goal is to compute $\min_{1\leq i<j\leq
n}\|x_{i}-x_{j}\|$. Let $t\in{\mathbb{Z}}_{\geq 0}^{d+1}$ be the 0-indexed
vector of nonnegative integers, where $t_{\ell}:=|\\{1\leq i<j\leq
n\mid\|x_{i}-x_{j}\|_{2}^{2}=\ell\\}|$ counts the number of pairs of input
points with distance $\ell$. Our goal will be to recover the vector $t$, from
which we can recover the answer to the Hamming nearest neighbors problem by
returning the smallest index where $t$ is nonzero.

Let $k=d+1$ and let $\varepsilon=(\kappa(k))^{\alpha\cdot k^{4}}$ for a
constant $\alpha>0$ to be picked later. In order to recover $t$, we will make
$d+1$ calls to our given algorithm. For $\ell\in\\{0,1,\ldots,d\\}$, the goal
of call $\ell$ is to compute a value $u_{\ell}$ which is an approximation,
with additive error at most $\varepsilon$, of entry $\ell$ of the vector $Mt$,
where $M$ is the counting matrix defined above.

Let us explain why this is sufficient to recover $t$. Suppose we have computed
this vector $u$. We claim that if we compute $M^{-1}u$, and round each entry
to the nearest integer, the result is the vector $t$. Indeed, by Lemma 5.24,
each entry of $M^{-1}u$ differs from the corresponding entry of $t$ by at most
an additive $\varepsilon\cdot B^{k-1}\cdot k!/|\det(M)|$, where the constant
$B$ is from Proposition 5.18 (since $|f(z)|\leq B$ for all $z\in[0,1]$).
Substituting our lower bound on $|\det(M)|$ from Lemma 5.23, we see this
additive error is at most $1/3$ as long as we’ve picked a sufficiently large
constant $\alpha>0$. Thus, rounding each entry to the nearest integer recovers
$t$, as desired.

It remains to show how to compute $u_{\ell}$, an approximation with additive
error at most $\varepsilon$ of entry $\ell$ of the vector $Mt$. In other
words, we need to approximate the sum

$\sum_{p=0}^{d}M_{\ell,p}\cdot t_{p}=\sum_{1\leq i<j\leq
k}f(c+(\rho(k)/(B(200k)^{k}))^{10k}\cdot\ell\cdot\|x_{i}-x_{j}\|_{2}^{2}/k^{2}).$

To do this, we will pick points
$y_{1},\ldots,y_{n},z_{1},\ldots,z_{n}\in[0,1]^{d+1}$ such that

$\displaystyle\|y_{i}-z_{j}\|_{2}^{2}=c+(\rho(k)/(B(200k)^{k}))^{10k}\cdot\ell\cdot\|x_{i}-x_{j}\|_{2}^{2}/k^{2}$

for all $i,j\in[n]$, and apply our given algorithm with error $\varepsilon$ to
these points. For $i\in[n]$, let
$x_{i}^{\prime}=(\rho(k)/(B(200k)^{k}))^{5k}\cdot\sqrt{\ell}\cdot x_{i}/k$ be
a rescaling of $x_{i}$. We pick $y_{i}$ to equal $x^{\prime}_{i}$ in the first
$d$ entries and $0$ in the last entry, and $z_{i}$ to equal $x^{\prime}_{i}$
in the first $d$ entries and $\sqrt{c}$ in the last entry. These points have
the desired distances, completing the proof. ∎

###### Step 7: proof of Theorem 5.15.

If the $\mathsf{KAdjE}$ problem for $\mathsf{K}(x,y)=f(\|x-y\|_{2}^{2})$ in
dimension $d$ and error $(\kappa(d+1))^{O(d^{4})}$ on $n=1.01^{d}$ points
could be solved in time time $n^{2-\delta}$ for any constant $\delta>0$, then
one could immediately substitute this into Lemma 5.25 to refute
$\mathsf{SETH}$ in light of Theorem 3.21. ∎

###  5.5 Lower Bounds in Low Dimensions

The landscape of algorithms available in low dimensions $d=o(\log n)$ is a
fair bit more complex. The Fast Multipole Method allows us to solve
$\mathsf{KAdjE}$ for a number of functions $f$, including
$\mathsf{K}(x,y)=\exp(-\|x-y\|_{2}^{2})$ and
$\mathsf{K}(x,y)=1/\|x-y\|_{2}^{2}$, for which we have a lower bound in high
dimensions. Classifying when these multipole methods apply to a function $f$
seems quite difficult, as researchers have introduced more and more tools to
expand the class of applicable functions. See Section 9, below, in which we
give a much more detailed overview of these methods.

That said, in this subsection, we prove lower bounds for a number of functions
$\mathsf{K}$ of interest. We show that for a number of functions $\mathsf{K}$
with applications to geometry and statistics, the $\mathsf{KAdjE}$ problem
seems to become hard even in dimension $d=3$ (see the end of this subsection
for a list of such $\mathsf{K}$).

We begin with the function $\mathsf{K}(x,y)=|\langle x,y\rangle|$. Here, the
$\mathsf{K}$ Adjacency Evaluation problem becomes hard even for very small
$d$. We give an $n^{1+o(1)}$ time algorithm only for $d\leq 2$. For $d=3$ we
show that such an algorithm would lead to a breakthrough in algorithms for the
${\mathbb{Z}}$-MaxIP problem, and for the only slightly super-constant
$d=2^{\Omega(\log^{*}n)}$, we show that a $n^{2-\varepsilon}$ time algorithm
would refute SETH.

######  Lemma 5.26.

For the function $\mathsf{K}(x,y)=|\langle x,y\rangle|$, the $\mathsf{KAdjE}$
problem (Problem 5.1) can be solved exactly in time $n^{1+o(1)}$ when $d=2$.

###### Proof.

Given as input $x_{1},\ldots,x_{n}\in{\mathbb{R}}^{2}$ and
$y\in{\mathbb{R}}^{n}$, our goal is to compute $z\in{\mathbb{R}}^{n}$ given by
$z_{i}:=\sum_{j\neq i}|\langle x_{i},x_{j}\rangle|\cdot y_{j}$. We will first
compute $z^{\prime}_{i}:=\sum_{j}|\langle x_{i},x_{j}\rangle|\cdot y_{j}$, and
then subtract $|\langle x_{i},x_{i}\rangle|\cdot y_{i}$ for each $i$ to get
$z_{i}$.

We first sort the input vectors by their polar coordinate angle, and relabel
so that $x_{1},\ldots,x_{n}$ are in sorted order. Let $\phi_{i}$ be the polar
coordinate angle of $x_{i}$. We will maintain two vectors
$x^{+},x^{-}\in{\mathbb{R}}^{2}$. We will ‘sweep’ an angle $\theta$ from $0$
to $2\pi$, and maintain that $x^{+}$ is the sum of the $y_{i}\cdot x_{i}$ with
$\langle x_{i},\theta\rangle>0$, and $x^{-}$ is the sum of the other
$y_{i}\cdot x_{i}$. Initially let $\theta=0$ and let $x^{+}$ be the sum of the
$y_{i}\cdot x_{i}$ with $\phi_{i}\in[-\pi/2,\pi/2)$, and $x^{-}$ be the sum of
the remaining $y_{i}\cdot x_{i}$. As we sweep, whenever $\theta$ is in the
direction of an $x_{i}$ we can set $z^{\prime}_{i}=\langle
x_{i},x^{+}-x^{-}\rangle$. Whenever $\theta$ is orthogonal to an $x_{i}$, we
swap $y_{i}\cdot x_{i}$ from one of $x^{+}$ or $x^{-}$ to the other. Over the
whole sweep, each point is swapped at most twice, so the total running time is
indeed $n^{1+o(1)}$. ∎

######  Lemma 5.27.

For the function $\mathsf{K}(x,y)=|\langle x,y\rangle|$, if the
$\mathsf{KAdjE}$ problem (Problem 5.1) with error $1/n^{\omega(1)}$ can be
solved in time $\mathcal{T}(n,d)$, and $n>d+1$, then ${\mathbb{Z}}$-MaxIP
(Problem 3.22) with $d$-dimensional vectors of integer entries of bit length
$O(\log n)$ can be solved in time $O(\mathcal{T}(n,d)\log^{2}n+nd)$.

###### Proof.

Let $x_{1},\ldots,x_{n}\in{\mathbb{Z}}^{d}$ be the input vectors. Let $M\leq
n^{O(1)}$ be the maximum magnitude of any entry of any input vector. Thus,
$\max_{i\neq j}\langle x_{i},x_{j}\rangle$ is an integer in the range
$[-dM^{2},dM^{2}]$. We will binary search for the answer in this interval. The
total number of binary search steps will be $O(\log(dM^{2}))\leq O(\log n)$.

We now show how to do each binary search step. Suppose we are testing whether
the answer is $\leq a$, i.e. testing whether $\langle x_{i},x_{j}\rangle\leq
a$ for all $i\neq j$. Let $S_{1},\ldots,S_{\log n}\subseteq\\{1,\ldots,n\\}$
be subsets such that for each $i\neq j$, there is a $k$ such that
$|S_{k}\cap\\{i,j\\}|=1$. For each $k\in\\{1,\ldots,\log n\\}$ we will show
how to test whether there are $i,j$ with $|S_{k}\cap\\{i,j\\}|=1$ such that
$\langle x_{i},x_{j}\rangle\leq a$, which will complete the binary search
step.

Define the vectors $x^{\prime}_{1},\ldots,x^{\prime}_{n}\in{\mathbb{Z}}^{d+1}$
by $(x^{\prime}_{i})_{j}=(x_{i})_{j}$ for $j\leq d$, and
$(x^{\prime}_{i})_{d+1}=a-1$ if $i\in P_{k}$, and $(x^{\prime}_{i})_{d+1}=-1$
if $i\notin P_{k}$. Hence, for $i,j$ with $|S_{k}\cap\\{i,j\\}|=1$ we have
$\langle x^{\prime}_{i},x^{\prime}_{j}\rangle=\langle x_{i},x_{j}\rangle-a+1$,
and so our goal is to test whether there are any such $i,j$ with $\langle
x^{\prime}_{i},x^{\prime}_{j}\rangle>0$.

Let $v_{k}\in\\{0,1\\}^{n}$ be the vector with $(v_{k})_{i}=1$ when $i\in
P_{k}$ and $(v_{k})_{i}=0$ when $i\notin P_{k}$. Use the given algorithm to
vector $v_{k}$, we can compute a $(a\pm n^{-\omega(1)})$ approximation to

$\displaystyle s_{1}:=\sum_{i\in P_{k}}\sum_{j\notin P_{k}}|\langle
x^{\prime}_{i},x^{\prime}_{j}\rangle|$

in time $O(\mathcal{T}(n,d))$. Similarly, using the fact that the
corresponding matrix has rank $d$ by definition, we can exactly compute

$\displaystyle s_{2}:=\sum_{i\in P_{k}}\sum_{j\notin P_{k}}\langle
x^{\prime}_{i},x^{\prime}_{j}\rangle$

in time $O(nd)$. Our goal is to determine whether $s_{1}=-s_{2}$. Since each
$s_{1}$ and $s_{2}$ is a polynomially-bounded integer, and we have a
superpolynomially low error approximation to each, we can determine this as
desired. ∎

Combining Lemma 5.27 with Theorem 3.23 we get:

######  Corollary 5.28.

Assuming SETH, there is a constant $c$ such that for the function
$\mathsf{K}(x,y)=|\langle x,y\rangle|$, the $\mathsf{KAdjE}$ problem (Problem
5.1) with error $1/n^{\omega(1)}$ and dimension $d=c^{\log^{*}n}$ vectors of
$O(\log n)$ bit entries requires time $n^{2-o(1)}$.

Similarly, combining with Theorem 3.24 we get:

######  Corollary 5.29.

For the function $\mathsf{K}(x,y)=|\langle x,y\rangle|$, if the
$\mathsf{KAdjE}$ problem (Problem 5.1) with error $1/n^{\omega(1)}$ and
dimension $d=3$ vectors of $O(\log n)$ bit entries can be solved in time
$n^{4/3-O(1)}$, then we would get a faster-than-known algorithm for
${\mathbb{Z}}$-${\sf MaxIP}$ (Problem 3.22) in dimension $d=3$.

The same proof, but using Theorem 3.25 instead of Theorem 3.23, can also show
hardness of thresholds of distance functions:

######  Corollary 5.30.

Corollary 5.28 also holds for the function
$\mathsf{K}(x,y)=\mathrm{TH}(\|x-y\|_{2}^{2})$, where $\mathrm{TH}$ is any
threshold function (i.e. $\mathrm{TH}(z)=1$ for $z\geq\theta$ and
$\mathrm{TH}(z)=0$ otherwise, for some $\theta\in{\mathbb{R}}_{>0}$).

Using essentially the same proof as for Lemma 8.4 in Section 8, we can further
extend Corollary 5.30 to any non-Lipschitz functions $f$:

######  Proposition 5.31.

Suppose $f:{\mathbb{R}}_{+}\to{\mathbb{R}}$ is any function which is not
$(C,L)$-multiplicatively Lipschitz for any constants $C,L\geq 1$. Then,
assuming SETH, the $\mathsf{KAdjE}$ problem (Problem 5.1) with error
$1/n^{\omega(1)}$ and dimension $d=c^{\log^{*}n}$ requires time $n^{2-o(1)}$.

###  5.6 Hardness of the $n$-Body Problem

We now prove Corollary 1.2 from the Introduction, showing that our hardness
results for the $\mathsf{KAdjE}$ problem (Problem 5.1) also imply hardness for
the $n$-body problem.

######  Corollary 5.32 (Restatement of Corollary 1.2).

Assuming $\mathsf{SETH}$, there is no

$\displaystyle\mathrm{poly}(d,\log(\alpha))\cdot n^{1+o(1)}$

-time algorithm for one step of the $n$-body problem.

###### Proof.

We reduce from the $\mathsf{K}$ graph Laplacian multiplication problem, where
$\mathsf{K}(u,v)=f(\|u-v\|_{2}^{2})$ and $f(z)=\frac{1}{(1+z)^{3/2}}$. A
$\mathsf{K}$ graph Laplacian multiplication instance consists of the
$\mathsf{K}$ graph $G$ on a set of $n$ points $X\subseteq\mathbb{R}^{d}$ and a
vector $y\in\\{0,1\\}^{n}$ for which we wish to compute $L_{G}y$. Think of $y$
as vector with coordinates in the set $X$. Compute this multiplication using
an $n$-body problem as follows:

  1. 1.

For each $b\in\\{0,1\\}$, let $X_{b}=\\{x\in X\leavevmode\nobreak\
|\leavevmode\nobreak\ y_{x}=b\\}$. Let $Z\subseteq\mathbb{R}^{d+1}$ be the set
of all $(x,0)$ for $x\in X_{0}$ and $(x,1)$ for $x\in X_{1}$.

  2. 2.

Solve the one-step $n$-body problem on $Z$ with unit masses. Let
$z\in\mathbb{R}^{n}$ be the vector of the $(d+1)$-th coordinate of these
forces, with forces negated for coordinates $x\in X_{0}$.

  3. 3.

Return $-z/G_{\text{grav}}$ (Note that $G_{\text{grav}}$ is the Gravitational
constant)

We now show that $z=L_{G}y$. For $x\in X_{b}$,
$(L_{G}y)_{x}=(-1)^{1-b}\sum_{x^{\prime}\in X_{1-b}}\mathsf{K}(x,x^{\prime})$.
We now check that $z_{x}$ is equal to this by going through pairs
$\\{x,x^{\prime}\\}$ individually. Note that the $(d+1)$-th coordinate of the
force between $(x,b)$ and $(x^{\prime},b)$ is 0. The $(d+1)$-th coordinate of
the force exerted by $(x^{\prime},1)$ on $(x,0)$ is

$\displaystyle\frac{G_{\text{grav}}}{\|(x,0)-(x^{\prime},1)\|_{2}^{2}}\cdot\frac{(1-0)}{\|(x,0)-(x^{\prime},1)\|_{2}}=G_{\text{grav}}\cdot\mathsf{K}(x,x^{\prime})$

Negating this gives the force exerted by $(x^{\prime},0)$ on $(x,1)$. All of
these contributions agree with the corresponding contributions to the sum
$(L_{G}y)_{x}$, so $-z/G_{\text{grav}}=L_{G}\cdot y$ as desired.

The runtime of this reduction is $O(n)$ plus the runtime of the $n$-body
problem. However, Theorem 1.1 shows that no almost-linear time algorithm
exists for $\mathsf{K}$-Laplacian multiplication, since $f$ is not
approximable by a polynomial with degree less than $\Theta(\log n)$.
Therefore, no almost-linear time algorithm exists for $n$-body either assuming
$\mathsf{SETH}$, as desired. ∎

###  5.7 Hardness of Kernel PCA

For any function
$\mathsf{K}:{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\to{\mathbb{R}}$, and any
set $P=\\{x_{1},\ldots,x_{n}\\}\subseteq{\mathbb{R}}^{d}$ of $n$ points,
define the matrix $K_{\mathsf{K},P}\in{\mathbb{R}}^{n\times n}$ by

$\displaystyle K_{\mathsf{K},P}[i,j]=\mathsf{K}(x_{i},x_{j})$

$A_{\mathsf{K},P}$ and $K_{\mathsf{K},P}$ differ only on their diagonal
entries, so a $n^{1+o(1)}$ time algorithm for multiplying by one can be easily
converted into such an algorithm for the other. Kernel PCA studies

######  Problem 5.33 ($\mathsf{K}$ PCA).

For a given function
$\mathsf{K}:{\mathbb{R}}^{d}\times{\mathbb{R}}^{d}\to{\mathbb{R}}$, the
$\mathsf{K}$ PCA problem asks: Given as input a set
$P=\\{x_{1},\ldots,x_{n}\\}\subseteq{\mathbb{R}}^{d}$ with $|P|=n$, output the
$n$ eigenvalues of the matrix $(I_{n}-J_{n})\times
K_{\mathsf{K},P}\times(I_{n}-J_{n})$, where $J_{n}$ is the $n\times n$ matrix
whose entries are all $1/n$. In $\varepsilon$-approximate $\mathsf{K}$ PCA, we
want to return a $(1\pm\varepsilon)$-multiplicative approximation to each
eigenvalue.

We can now show a general hardness result for $\mathsf{K}$ PCA:

######  Theorem 5.34 (Approximate).

For every function $f:\mathbb{R}\rightarrow\mathbb{R}$ which is equal to a
Taylor expansion $f(x)=\sum_{i=0}^{\infty}c_{i}x^{i}$ on an interval $(0,1)$,
if $f$ is not $\varepsilon$-approximated by a polynomial of degree $O(\log n)$
(Definition 5.6) on an interval $(0,1)$ for $\varepsilon=2^{-\log^{4}n}$,
then, assuming SETH, the $\varepsilon$-approximate $\mathsf{K}$ PCA problem
(Problem 5.1) in dimension $d=O(\log n)$ requires time $n^{2-o(1)}$.

###### Proof Sketch.

Theorem 5.34 follows almost directly from Theorem 5.14 when combined with the
reduction from [BCIS18, Section 5]. The idea is as follows: Suppose we are
able to estimate the $n$ eigenvalues of $(I_{n}-J_{n})\times
K_{\mathsf{K},P}\times(I_{n}-J_{n})$. Then, in particular, we can estimate
their sum, which is equal to:

$\mathrm{tr}((I_{n}-J_{n})\times
K_{\mathsf{K},P}\times(I_{n}-J_{n}))=\mathrm{tr}(K_{\mathsf{K},P}\times(I_{n}-J_{n})^{2})=\mathrm{tr}(K_{\mathsf{K},P}\times(I_{n}-J_{n}))=\mathrm{tr}(K_{\mathsf{K},P})-S(K_{\mathsf{K},P})/n,$

where $S(K_{\mathsf{K},P})$ denotes the sum of the entries of
$K_{\mathsf{K},P}$. We can compute $\mathrm{tr}(K_{\mathsf{K},P})$ exactly in
time $n^{1+o(1)}$, so we are able to get an approximation to
$S(K_{\mathsf{K},P})$. However, in the proof of Theorem 5.14, we showed
hardness for approximating $S(K_{\mathsf{K},P})$, which concludes our proof
sketch. ∎

##  6 Sparsifying Multiplicatively Lipschitz Functions in Almost Linear Time

Given $n$ points, let $\alpha$ denote

$\displaystyle\alpha=\frac{\max_{u,v\in P}(\|u-v\|_{2}^{2})}{\min_{u,v\in
P}(\|u-v\|_{2}^{2})}.$

In this section, we give an algorithm to compute sparsifiers for a large class
of kernels $\mathsf{K}$ in almost linear time in $nd$, with logarithmic
dependency on $\alpha$ and $1/\varepsilon^{2}$ dependence on $\varepsilon$.
When $d=\log n$, our algorithm runs in almost linear time in $n$. To formally
state our main theorem, we define multiplicatively Lipschitz functions:

######  Definition 6.1.

Let $C\geq 1$ and $L\geq 1$. A function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ is $(C,L)$-multiplicatively Lipschitz iff
for all $c\in[1/C,C]$, we have:

$\displaystyle\frac{1}{C^{L}}<\frac{f(cx)}{f(x)}<C^{L},\forall
x\in\mathbb{R}_{\geq 0}.$

Examples: Any polynomial with non-negative coefficients and maximum degree $q$
is $(1+\varepsilon,q)$ multiplicatively Lipschitz for any $\varepsilon>0$. The
function $f(x)=1$ when $x<1$ and $f(x)=2$ when $x\geq 1$ is $(2,1)$
multiplicatively Lipschitz.

The following lemma is a simple consequence of our definition of
multiplicatively Lipschitz functions:

######  Lemma 6.2.

Let $C\geq 1$ and $L>0$. Any function $f:{\mathbb{R}}_{\geq
0}\rightarrow{\mathbb{R}}_{\geq 0}$ that is $(C,L)$-multiplicatively Lipschitz
satisfies for all $c\in(0,1/C)\cup[C,+\infty)$ :

$\displaystyle\frac{1}{c^{2L}}<\frac{f(cx)}{f(x)}<c^{2L}.$

We now state the core theorem of this section:

######  Theorem 6.3.

Let $C\geq 1$ and $L\geq 1$. Consider any $(C,L)$-multiplicatively Lipschitz
function $f:{\mathbb{R}}\rightarrow{\mathbb{R}}$, and let
$\mathsf{K}(x,y)=f(\|x-y\|_{2}^{2})$. Let $P$ be a set of $n$ points in
$\mathbb{R}^{d}$. For any $k\in[\Omega(1),O(\log n)]$ such that
$C=n^{O(1/k)}$, there exists an algorithm
sparsify-$\mathsf{K}$-graph$(P,n,d,\mathsf{K},k,L)$ (Algorithm 3) that runs in
time:

$\displaystyle O(ndk)+\varepsilon^{-2}\cdot n^{1+O(L/k)}2^{O(k)}\log
n\cdot\log\alpha$

and outputs an $\varepsilon$-spectral sparsifier $H$ of the $\mathsf{K}$ graph
with $|E_{H}|=O(n\log n/\varepsilon^{2})$.

We give a corollary of this theorem.

######  Corollary 6.4.

Consider a $\mathsf{K}$ graph where $\mathsf{K}(x,y)=f(\|x-y\|_{2}^{2})$, and
$f$ is $(2,L)$-multiplicatively Lipschitz. Let $G$ denote the $\mathsf{K}$
graph from $n$ points in $\mathbb{R}^{d}$. There is an algorithm that takes in
time

$\displaystyle O(nd\sqrt{L\log n})+\varepsilon^{-2}\cdot n\cdot
2^{O(\sqrt{L\log n}\log\log n)}\cdot\log\alpha$

and outputs an $\varepsilon$-spectral sparsifier $H$ of $G$ with
$|E_{H}|=O(n\log n/\varepsilon^{2})$. If $L=o(\log n/(\log\log n)^{2})$, this
runs in time

$\displaystyle o(nd\log n)+\varepsilon^{-2}n^{1+o(1)}\log\alpha.$

###### Proof.

Set $k=\sqrt{L\log n}$, and the corollary follows from Theorem 6.3. ∎

This implies that if $f$ is a polynomial with non-negative coefficients, then
sparsifiers of the corresponding $\mathsf{K}$-graph can be found in almost
linear time. The same result holds if $f$ is the reciprocal of a polynomial
with non-negative coefficients.

We will need a few geometric preliminaries in order to present our core
algorithm of this section, Sparsify-$\mathsf{K}$-graph.

######  Definition 6.5 ($\varepsilon$-well separated pair).

Given two sets of points $A$ and $B$. We say $A,B$ is an $\varepsilon$-well
separated pair if the diameter of $A_{i}$ and $B_{i}$ are at most
$\varepsilon$ times the distance between $A_{i}$ and $B_{i}$.

######  Definition 6.6 ($\varepsilon$-well separated pair decomposition
[CK95]).

An $\varepsilon$-well separated pair decomposition
($\varepsilon$-$\mathrm{WSPD}$) of a given point set $P$ is a family of pairs
$\mathcal{F}=\\{(A_{1},B_{1}),\ldots(A_{s},B_{s})\\}$ with $A_{i},B_{i}\subset
P$ such that:

  * •

$\forall i\in[s]$, $A_{i}$, $B_{i}$ are $\varepsilon$-well separated pair
(Definition 6.5)

  * •

For any pair $p,q\in P$, there is a unique $i\in[s]$ such that $p\in A_{i}$
and $q\in B_{i}$

A famous theorem of Callahan and Kosaraju [CK95] states:

######  Theorem 6.7 (Callahan and Kosaraju [CK95]).

Given any point set $P\subset\mathbb{R}^{d}$ and $0\leq\varepsilon\leq 9/10$,
an $\varepsilon$-$\mathrm{WSPD}$ (Definition 6.6) of size
$O(n/\varepsilon^{d})$ can be found in $2^{O(d)}\cdot(n\log
n+n/\varepsilon^{d})$ time. Moreover, each vertex participates in at most
$2^{O(d)}\cdot\log\alpha$ $\varepsilon$-well separated pairs.

Well-separated pairs can be interpreted as complete bipartite graphs on the
vertex set, or bicliques. The biclique associated with a well-separated pair
is the bipartite graph connecting all vertices on one side of the pair to
another.

This concludes our definitions on well-separated pairs. We now give names to
some algorithms in past work, which will be used in our algorithm
sparsify-$k$-graph. We define the algorithm
$\textsc{GenerateWSPD}(P,\varepsilon)$ to output an $\varepsilon$-WSPD
(Definition 6.6) of $P$. We define the algorithm $\textsc{RandomProject}(P,k)$
to be a random projection of $P$ onto $k$ dimensions.

Let $\textsc{Biclique}(\mathsf{K},P,A,B)$ be the complete biclique on the
$\mathsf{K}$-graph of $P$ with one side of the biclique having verticese
corresponding to points in $A$, and the other side having vertices
corresponding to points in $B$. We store this biclique implicitly as $(A,B)$
rather than as a collection of edges.

Let $\textsc{RandSample}(G,s)$ be an algorithm uniformly at random sampling
$O(s)$ edges from $G$, where the big $O$ is the same constant as the big $O$
in the $n^{O(1/k)}$ from Lemma 3.15.

Let $\textsc{SpectralSparsify}(G,\varepsilon)$ be any nearly linear time
spectral sparsification algorithm that outputs a $(1+\varepsilon)$ spectral
sparsifier with $O(n\log n/\varepsilon^{2})$ edges, such as that in Theorem
3.7 from [SS11].

Algorithm 3

1:procedure Sparsify-$\mathsf{K}$-Graph($P,n,d,\mathsf{K},k,L,\varepsilon$)
$\triangleright$ Theorem 6.3

2: Input: A point set $P$ with $n$ points in dimension $d$, a kernel function
$\mathsf{K}(x,y)=f(\|x-y\|_{2}^{2})$, an integer variable $\Omega(1)\leq k\leq
O(\log n)$, and a variable $L$, and error $\varepsilon$.

3: Output: A candidate sparsifier of the $\mathsf{K}$-graph on $P$.

4: $P^{\prime}\leftarrow\textsc{RandomProject}(P,k)$

5: $H\leftarrow$ empty graph with $n$ vertices.

6:
$\\{(A_{1}^{\prime},B_{1}^{\prime}),\ldots(A_{t}^{\prime},B_{t}^{\prime})\\}\leftarrow\textsc{GenerateWSPD}(P^{\prime},n,d,1/2)$
$\triangleright$ $t=n\cdot 2^{d}$

7: for $i=1\to t$ do

8: Find $(A_{i},B_{i})$ corresponding to $(A_{i}^{\prime},B_{i}^{\prime})$,
where $A_{i},B_{i}\subset P$.

9: $Q\leftarrow\textsc{BiClique}(\mathsf{K},P,A_{i},B_{i})$.

10:
$s\leftarrow\varepsilon^{-2}n^{O(L/k)}(|A_{i}|+|B_{i}|)\log(|A_{i}|+|B_{i}|)$

11: $\overline{Q}\leftarrow\textsc{RandSample}(Q,s)$

12: $\overline{Q}\leftarrow\overline{Q}$ with each edge scaled by
$|A_{i}||B_{i}|/s$.

13: $H\leftarrow H+\overline{Q}$

14: end for

15: $H\leftarrow\textsc{SpectralSparsify}(H,\varepsilon)$ $\triangleright$
Corollary 3.8

16: Return $H$

17:end procedure

18:procedure GenerateWSPD($P,n,d,\varepsilon$) $\triangleright$ Theorem 6.7

19: … $\triangleright$ See details in [CK95]

20:end procedure

21:procedure RandSample($G,s$)

22: Sample $O(s)$ edges from $G$ and generate a new graph $\overline{G}$

23: return $\overline{G}$

24:end procedure

25:procedure RandomProject($P,d,k$)

26: $P^{\prime}\leftarrow\emptyset$

27: Choose a JL matrix $S\in{\mathbb{R}}^{k\times d}$

28: for $x\in P$ do

29: $x^{\prime}\leftarrow S\cdot x$

30: $P^{\prime}\leftarrow P^{\prime}\cup x^{\prime}$

31: end for

32: return $P^{\prime}$

33:end procedure

The rest of this section is devoted to proving Theorem 6.3.

###  6.1 High Dimensional Sparsification

We are nearly ready to prove Theorem 6.3. We start with a Lemma:

######  Lemma 6.8 ($(C,L)$ multiplicative Lipschitz functions don’t distort a
graph’s edge weights much).

Consider a complete graph $G$, and a complete graph $G^{\prime}$, where
vertices of $G$ are identified with vertices of $G^{\prime}$ (which induces an
identification between edges). Let $K\geq 1$. Suppose each edge in $G$
satisfies:

$\displaystyle\frac{1}{K}\cdot w_{G^{\prime}}(e)\leq w_{G}(e)\leq K\cdot
w_{G^{\prime}}(e)$

If $f$ is a $(C,L)$ multiplicative Lipschitz function, and $f(G)$ refers to
the graph $G$ where $f$ is applied to each edge length, and $C<K$ then:

$\displaystyle\frac{1}{K^{2L}}\cdot w_{G^{\prime}}(e)\leq w_{f(G)}(e)\leq
K^{2L}\cdot w_{G^{\prime}}(e).$

###### Proof.

This follows from Lemma 6.2. ∎

###### Proof.

(of Theorem 6.3): The Algorithm sparsify-$\mathsf{K}$-graph starts by
performing a random projection of point set $P$ into $k$ dimensions. Call the
new point set $P^{\prime}$. This runs in time $O(ndk)$, and incurs distortion
$n^{O(1/k)}$, as seen in Lemma 3.15. Next, our algorithm performs a
$1/2$-$\mathrm{WSPD}$ on $P^{\prime}$. As seen in Theorem 6.7, this runs in
time

$\displaystyle O(n\log n+n2^{O(k)})$

We view each well-separated pair $(A_{i}^{\prime},B_{i}^{\prime})$ on
$P^{\prime}$ as a biclique, where the edge length between any two points in
$P^{\prime}$ corresponds to the edge length between those two points in the
original $\mathsf{K}$-graph. By the guarantees of Theorem 6.7, the longest
edge divided by the shortest edge between two sides of a well-separated pair
in $P^{\prime}$ is at most $2$. Thus, the longest edge divided by the shortest
edge within any induced bipartite graph on the $\mathsf{K}$-graph is $2\cdot
n^{O(1/k)}$, by Lemma 6.8.

For each such biclique, the leverage score for each edge is overestimated by

$\displaystyle
n^{O(L/k)}\cdot(|A_{i}^{\prime}|+|B_{i}^{\prime}|)/(|A_{i}^{\prime}||B_{i}^{\prime}|).$

This comes from first applying Lemma 6.8 to upper bound the ratio of the
longest edge in a biclique divided by the shortest edge. This ratio comes out
to be $2n^{O(L/k)}$. Now recall the definition of leverage score on graphs as
$w_{e}R_{e}$, where $R_{e}$ is the effective resistance assuming conductances
of $w_{e}$ on the graph, and $w_{e}$ is the edge weight. Here, $w_{e}$ is
upper bounded by the longest edge length, and $R_{e}$ is upper bounded by the
leverage score of a biclique supported on the same edges, where all edges
lengths are equal to the shortest edge length (this is an underestimate of
effective resistance due to Rayleigh monotonicity, see [Chu97] for details).
Therefore, a leverage score overestimate of the graph can be obtained by
$n^{O(L/k)}\cdot(|A_{i}^{\prime}|+|B_{i}^{\prime}|)/(|A_{i}^{\prime}||B_{i}^{\prime}|)$,
as claimed. The union of these graphs is a spectral sparsifier of our
$\mathsf{K}$-graph.

Finally, our algorithm samples
$n^{O(L/k)}(|A_{i}^{\prime}|+|B_{i}^{\prime}|)\log(|A_{i}^{\prime}|+|B_{i}^{\prime}|)$
edges uniformly at random from each biclique, scaling each sampled edge’s
weight so that the expected value of the sampled graph is equal to the
original biclique. Each vertex participates in at most $\log\alpha 2^{O(k)}$
bicliques (see Theorem 6.7). Thus, this uniform sampling procedures’ run time
is bounded above by

$n^{1+O(L/k)}2^{O(k)}\log n\cdot\log\alpha.$

Finally, our algorithm runs a sparsification algorithm on our graph after
uniform sampling, which gets the edge count of the final graph down to
$O(n\log n/\varepsilon^{2})$. This completes our proof of Theorem 6.3. ∎

###  6.2 Low Dimensional Sparsification

We now present a result on sparsification in low dimensions, when $d$ is
assumed to be small or constant.

######  Theorem 6.9.

Let $L\geq 1$. Consider a $\mathsf{K}$-graph with $n$ vertices arising from a
point set in $d$ dimensions, and let $\alpha$ be the ratio of the maximum
Euclidean distance to the minimum Euclidean distance in the point set . Let
$f$ be a $(1+1/L,L)$ multiplicatively Lipschitz function. Then an
$\varepsilon$ spectral sparsifier of the $\mathsf{K}$-graph can be found in
time

$\displaystyle\varepsilon^{-2}\cdot n\cdot\log
n\cdot\log\alpha\cdot(2L)^{O(d)}$

###### Proof.

We roughly follow the proof of Theorem 6.3, except without the projection onto
low dimensions. Now, on the $d$ dimensional data, we create a
$1/L$-$\mathrm{WSPD}$. This takes time

$\displaystyle O(n\log n)+n\cdot(2L)^{O(d)}.$

Since $f$ is $(1+1/L,L)$-multiplicatively Lipschitz, it follows that within
each biclique of the $\mathsf{K}$-graph induced by the $\mathrm{WSPD}$
(Definition 6.6), the maximum edge length divided by the minimum edge length
is bounded above by $(1+1/L)^{O(L)}=O(1)$. Therefore, performing scaled and
reweighted uniform sampling on each biclique takes $O(s\log s)$ time if there
are $s$ vertices in the biclique, and gives a sparsified biclique with
$O(s\log s)$ edges.

Taking the union of this number over all bicliques gives an algorithm that
runs in time

$\displaystyle\varepsilon^{-2}\cdot n\cdot\log
n\cdot\log\alpha\cdot(2L)^{O(d)}$

as desired. ∎

##  7 Sparsifiers for $|\langle x,y\rangle|$

In this section, we construct sparsifiers for Kernels of the form $|\langle
x,y\rangle|$.

######  Lemma 7.1 (sparsification algorithm for inner product kernel).

Given a set of vectors $X\subseteq\mathbb{R}^{d}$ with $|X|=n$ and accuracy
parameter $\varepsilon\in(0,1/2)$, there is an algorithm that runs in
$\varepsilon^{-2}n\cdot\mathrm{poly}(d,\log n)$ time, and outputs a graph $H$
that satisfies both of the following properties with probability at least
$1-1/\mathrm{poly}(n)$:

  1. 1.

$(1-\varepsilon)L_{G}\preceq L_{H}\preceq(1+\varepsilon)L_{G}$;

  2. 2.

$|E(H)|\leq\varepsilon^{-2}\cdot n\cdot\mathrm{poly}(d,\log n)$.

where $G$ is the $\mathsf{K}$-graph on $X$, where $\mathsf{K}(x,y)=|\langle
x,y\rangle|$.

Throughout this section, we specify various values $C_{i}$. For each subscript
$i$, it is the case that $1\leq C_{i}\leq\text{poly}(d,\log n)$.

###  7.1 Existence of large expanders in inner product graphs

We start by showing that certain graphs that are related to unweighted
versions of $\mathsf{K}$-weighted graphs contain large expanders:

######  Definition 7.2 ($k$-dependent graphs).

For a positive integer $k>1$, call an unweighted graph $G$ $k$-_dependent_ if
no independent set with size at least $k+1$ exists in $G$.

We start by observing that inner product graphs are $(d+1)$-dependent.

######  Definition 7.3 (inner product graphs).

For a set of points $X\subseteq\mathbb{R}^{d}$, the _unweighted inner product
graph for_ $X$ is a graph $G$ with vertex set $X$ and unweighted edges
$\\{u,v\\}\in E(G)$ if and only if $|\langle
u,v\rangle|\geq\frac{1}{d+1}\|u\|_{2}\|v\|_{2}$. The _weighted inner product
graph for_ $X$ is a complete graph $G$ with edge weights $w_{e}$ for which
$w_{uv}=|\langle u,v\rangle|$.

We now show that these graphs are $k$-dependent:

######  Lemma 7.4.

Suppose $M\in{\mathbb{R}}^{n\times n}$ such that $M[i,i]=1$ for all $i\in[n]$,
and $|M[i,j]|<1/n$ for all $i\neq j$. Then, $M$ has full rank.

###### Proof.

Assume to the contrary that $M$ does not have full rank. Thus, there are
values $c_{1},\ldots,c_{n-1}\in{\mathbb{R}}$ such that for all $i\in[n]$ we
have $\sum_{j=1}^{n-1}c_{j}M[i,j]=M[i,n]$.

First, note that there must be a $j$ with $|c_{j}|\geq 1+1/n$. Otherwise, we
would have

$1=|M[n,n]|=\left|\sum_{j=1}^{n-1}c_{j}M[n,j]\right|<\frac{1}{n}\sum_{j=1}^{n-1}\left|c_{j}\right|<\frac{n-1}{n}(1+1/n)<1.$

Assume without loss of generality that $|c_{1}|\geq|c_{j}|$ for all
$j\in\\{2,3,\ldots,n-1\\}$, so in particular $|c_{1}|\geq 1+1/n$. Letting
$c_{n}=-1$, this means that $\sum_{j=1}^{n}c_{j}M[1,j]=0$, and so
$M[1,1]=-\sum_{j=2}^{n}(c_{j}/c_{1})M[1,j]$. Thus,

$\displaystyle
1=|M[1,1]|=\left|\sum_{j=2}^{n}\frac{c_{j}}{c_{1}}M[1,j]\right|\leq\sum_{j=2}^{n}\left|\frac{c_{j}}{c_{1}}M[1,j]\right|<\sum_{j=2}^{n}\left|M[1,j]\right|<(n-1)\cdot\frac{1}{n}<1,$

a contradiction as desired. ∎

######  Proposition 7.5.

The unweighted inner product graph for $X\subseteq\mathbb{R}^{d}$ is
$(d+1)$-dependent.

###### Proof.

For an independent set $S$ in the unweighted inner product graph $G$ for $X$,
define an $S\times S$ matrix $M$ with $M[i,j]=\langle s_{i},s_{j}\rangle$
where $S=\\{s_{1},s_{2},\ldots,s_{|S|}\\}$. Then Lemma 7.4 coupled with the
definition for edge presence in $G$ shows that $M$ is full rank. However, $M$
is a rank $d$ matrix because it is the matrix of inner products for dimension
$d$ vectors. Therefore, $d\geq|S|$, so no independent set has size greater
than $d$. ∎

Next, we show that $k$-dependent graphs are dense:

######  Proposition 7.6 (dependent graph is dense).

Any $k$-dependent graph $G$ has at least $n^{2}/(2k^{2})$ edges.

###### Proof.

Consider any $k+1$-tuple of vertices in $G$. There are $\binom{n}{k+1}$ such
$k+1$-tuples. By definition of $k$-dependence, there must be some edge with
endpoints in any $k+1$-tuple. The number of $k$-tuples that any given edge can
be a part of is at most $\binom{n-2}{k-1}$. Therefore, the number of edges in
the graph is at least

$\displaystyle\frac{\binom{n}{k+1}}{\binom{n-2}{k-1}}\geq\frac{n(n-1)}{(k+1)k}\geq\frac{n^{2}}{2k^{2}}$

as desired. ∎

Next, we argue that unweighted inner product graphs have large expanders:

######  Proposition 7.7 (every dense graph has a large expander).

Consider an unweighted graph $G$ with $n$ vertices and at least $n^{2}/c$
edges for some $c>1$. Then, there exists a set $S\subseteq V(G)$ with the
following properties:

  1. 1.

(Size) $|S|\geq n/(40c)$

  2. 2.

(Expander) $\Phi_{G[S]}\geq 1/(100c\log n)$

  3. 3.

(Degree) The degree of each vertex in $S$ within $G[S]$ is at least
$n/(10000c)$

###### Proof.

We start by partitioning the graph as follows:

  1. 1.

Initialize $\mathcal{F}=\\{V(G)\\}$

  2. 2.

While there exists a set $U\in\mathcal{F}$ with (a) a partition $U=U_{1}\cup
U_{2}$ with $U_{1}$ cut having conductance $\leq 1/(100c\log n)$ or (b) a
vertex $u$ with degree less than $n/(10000c)$ in $G[U]$

    1. (a)

If (a), replace $U$ in $\mathcal{F}$ with $U_{1}$ and $U_{2}$

    2. (b)

Else if (b), replace $U$ in $\mathcal{F}$ with $U\setminus\\{u\\}$ and
$\\{u\\}$

We now argue that when this procedure stops,

$\sum_{U\in\mathcal{F}}|E(G[U])|\geq n^{2}/(2c)$

To prove this, think of each splitting of $U$ into $U_{1}$ and $U_{2}$ as
deleting the edges in $E(U_{1},U_{2})$ from $G$. Design a charging scheme that
assigns deleted edges due to (a) steps to edges of $G$ as follows. Let $c_{e}$
denote the charge assigned to an edge $e$ and initialize each charge to 0.
When $U$ is split into $U_{1}$ and $U_{2}$, let $U_{1}$ denote the set with
$|E(U_{1})|\leq|E(U_{2})|$. When $U$ is split, increase the charge $c_{e}$ for
each $e\in E(U_{1})\cup E(U_{1},U_{2})$ by $|E(U_{1},U_{2})|/|E(U_{1})\cup
E(U_{1},U_{2})|$.

We now bound the charge assigned to each edge at the end of the algorithm. By
construction, $\sum_{e\in E(G)}c_{e}$ is the number of edges deleted over the
course of the algorithm of type (a). Each edge is assigned charge at most
$\log|E(G)|\leq 2\log n$ times, because
$|E(U_{1})|\leq\frac{|E(U_{1})|+|E(U_{2})|}{2}\leq\frac{|E(U)|}{2}$ when
charge is assigned to edges in $U_{1}$. Furthermore, the amount of charge
assigned is the conductance of the cut deleted, which is at most $1/(100c\log
n)$. Therefore,

$\displaystyle c_{e}\leq\frac{2\log n}{100c\log n}=\frac{1}{50c}$

for all edges in $G$, which means that the total number of edges deleted of
type (a) was at most $n^{2}/(100c)$. Each type (b) deletion reduces the number
of edges in $G$ by at most $n/(10000c)$, so the total number of type (b) edge
deletions is at most $n^{2}/(10000c)$. Therefore, the total number of edges
remaining is at least

$\displaystyle\frac{n^{2}}{c}-\frac{n^{2}}{100c}-\frac{n^{2}}{10000c}>\frac{n^{2}}{2c},$

as desired.

By the stopping condition of the algorithm, each connected component of $G$
after edge deletions is a graph with all cuts having conductance at least
$1/(100c\log n)$ and all vertices having degree at least $n/(10000c)$. Next,
we show that some set in $\mathcal{F}$ has at least $n/(40c)$ vertices. If
this is not the case, then

$\displaystyle\sum_{U\in\mathcal{F}}|E(G[U])|\leq$
$\displaystyle\leavevmode\nobreak\ \sum_{U\in\mathcal{F}}|U|^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sum_{U\in\mathcal{F}}\frac{n}{40c}|U|$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\
assuming\leavevmode\nobreak\ all\leavevmode\nobreak\ }|U|\leq n/(40c)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ \frac{n^{2}}{40c}$
$\displaystyle\text{\leavevmode\nobreak\ by\leavevmode\nobreak\ }|U|\leq n$
$\displaystyle<$ $\displaystyle\leavevmode\nobreak\ \frac{n^{2}}{2c}$

which leads to a contradiction. Therefore, there must be some connected
component with at least $n/(40c)$ vertices. Let $S$ be this component. By
definition $S$ satisfies the _Size_ guarantee. By the stopping condition for
$\mathcal{F}$, $S$ satisfies the other two guarantees as well, as desired. ∎

Proposition 7.7 does not immediately lead to an efficient algorithm for
finding $S$. Instead, we give an algorithm for finding a weaker but sufficient
object:

######  Proposition 7.8 (algorithm for finding sets with low effective
resistance diameter).

For any set of vectors $X\subseteq\mathbb{R}^{d}$ with $n=|X|$ and unweighted
inner product graph $G$ for $X$, there is an algorithm
$\textsc{LowDiamSet}(X)$ that runs in time

$\mathrm{poly}(d,\log n)n$

and returns a set $Q$ that has the following properties with probability at
least $1-1/\mathrm{poly}(n)$:

  1. 1.

(Size) $|Q|\geq n/C_{1}$, where $C_{1}=320d^{2}$

  2. 2.

(Low effective resistance diameter) For any pair of vertices $u,v\in Q$,
$\mathtt{Reff}_{G}(u,v)\leq\frac{C_{2}}{n}$, where $C_{2}=(10d\log n)^{1}0$

We prove this proposition in Section 7.2.

###  7.2 Efficient algorithm for finding sets with low effective resistance
diameter

In this section, we prove Proposition 7.8. We implement LowDiamSet by picking
a random vertex $v$ and checking to see whether or not it belongs to a set
with low enough effective resistance diameter. We know that such a set exists
by Proposition 7.7 and the fact that dense expander graphs have low effective
resistance diameter. One could check that $v$ lies in this set in
$\widetilde{O}(n^{2})$ time by using the effective resistance data structure
of [SS11]. Verifying that $v$ is in such a set in $\mathrm{poly}(d,\log n)n$
time is challenging given that $G$ is dense. We instead use the following data
structure, which is implemented by uniformly sampling sparse subgraphs of $G$
and using [SS11] on those subgraphs:

######  Proposition 7.9 (Sampling-based effective resistance data structure).

Consider a set $X\subseteq\mathbb{R}^{d}$, let $n=|X|$, let $G$ be the
unweighted inner product graph for $X$, and let $S\subseteq X$ be a set with
the following properties:

  1. 1.

(Size) $|S|\geq n/C_{3a}$, where $C_{3a}=40\cdot 8d$

  2. 2.

(Expander) $\Phi_{G[S]}\geq 1/C_{3b}$, where $C_{3b}=800d\log n$

  3. 3.

(Degree) The degree of each vertex in $S$ within $G[S]$ is at least
$n/C_{3c}$, where $C_{3c}=10000\cdot 8d$.

There is a data structure that, when given a pair of query points $u,v\in X$,
outputs a value $\textsc{ReffQuery}(u,v)\in\mathbb{R}_{\geq 0}$ that satisfies
the following properties with probability at least $1-1/\mathrm{poly}(n)$:

  1. 1.

(Upper bound) For any pair $u,v\in S$, $\textsc{ReffQuery}(u,v)\leq
C_{4}\mathtt{Reff}_{G}(u,v)$, where $C_{4}=10$

  2. 2.

(Lower bound) For any pair $u,v\in X$,
$\textsc{ReffQuery}(u,v)\geq\mathtt{Reff}_{G}(u,v)/2$.

The preprocessing method $\textsc{ReffPreproc}(X)$ takes $\mathrm{poly}(d,\log
n)n$ time and ReffQuery takes $\mathrm{poly}(d,\log n)$ time.

We now implement this data structure. ReffPreproc uniformly samples $O(\log
n)$ subgraphs of $G$ and builds an effective resistance data structure for
each one using [SS11]. ReffQuery queries each data structure and returns the
maximum:

1:procedure ReffPreproc($X$)

2: Input: $X\subseteq\mathbb{R}^{d}$ with unweighted inner product graph $G$

3: $C_{5}\leftarrow 1000\log n$

4: $C_{6}\leftarrow 80000CC_{3a}^{2}C_{3b}^{2}C_{3c}^{2}$, where $C$ is the
constant in Theorem 3.6

5: for $i$ from 1 through $C_{5}$ do

6: $H_{i}\leftarrow$ uniformly random subgraph of $G$; sampled by picking
$C_{6}n$ uniformly random pairs $(u,v)\in X\times X$ and adding the
$e=\\{u,v\\}$ edge to $H_{i}$ if and only if $\\{u,v\\}\in E(G)$ (that is when
$|\langle u,v\rangle|\geq\frac{1}{d+1}\|u\|_{2}\|v\|_{2}$).

7: For each edge $e\in E(H_{i})$, let $w_{e}=\frac{|E(G)|}{|E(H_{i})|}$.

8: $f_{i}\in\mathbb{R}^{X\times X}\leftarrow$ approximation to
$\mathtt{Reff}_{H_{i}}(u,v)$ given by the data structure of Theorem 3.7 for
$\varepsilon=1/6$.

9: end for

10:end procedure

11:procedure ReffQuery($u,v$)

12: Input: A pair of points $u,v\in X$

13: Output: An estimate for the $u$-$v$ effective resistance in $G$

14: return $\max_{i=1}^{C_{5}}f_{i}(u,v)$

15:end procedure

Bounding the runtime of these two routines is fairly straightforward. We now
outline how we prove the approximation guarantee for ReffQuery. To obtain the
upper bound, we use Theorem 3.6 to show that $H_{i}$ contains a sparsifier for
$G[S]$, so effective resistances are preserved within $S$. To obtain the lower
bound, we use the following novel Markov-style bound on effective resistances:

######  Lemma 7.10.

Let $G$ be a $w$-weighted graph with vertex set $X$ and assign numbers
$p_{e}\in[0,1]$ to each edge. Sample a reweighted subgraph $H$ of $G$ by
independently and identically selecting $q$ edges, with an edge chosen with
probability proportional to $p_{e}$ and added to $H$ with weight
$tw_{e}/(p_{e}q)$, where $t=\sum_{e\in G}p_{e}$. Fix a pair of vertices $u,v$.
Then for any $\kappa>1$,

$\displaystyle\Pr\left[\mathtt{Reff}_{H}(u,v)\leq\mathtt{Reff}_{G}(u,v)/\kappa\right]\leq
1/\kappa.$

###### Proof.

For two vertices $u,v$, define the (folklore) _effective conductance_ between
$u$ and $v$ in the graph $I$ to be

$\displaystyle\mathtt{Ceff}_{I}(u,v):=\min_{q\in\mathbb{R}^{n}:q_{u}=0,q_{v}=1}\sum_{\text{
edges }\\{x,y\\}\in I}w_{xy}(q_{x}-q_{y})^{2}.$

It is well-known that $\mathtt{Ceff}_{I}(u,v)=1/\mathtt{Reff}_{I}(u,v)$.

Let

$\displaystyle
q^{*}=\arg\min_{q\in\mathbb{R}^{n}:q_{u}=0,q_{v}=1}\sum_{\\{x,y\\}\in
E(G)}w_{xy}(q_{x}-q_{y})^{2}.$

Using $q^{*}$ as a feasible solution in the $\mathtt{Ceff}_{H}$ optimization
problem shows that

$\displaystyle\textbf{E}[\mathtt{Ceff}_{H}(u,v)]$
$\displaystyle\leq\textbf{E}\left[\sum_{\\{x,y\\}\in
E(G)}w_{xy}^{H}(q^{*}_{x}-q^{*}_{y})^{2}\right]$
$\displaystyle=\sum_{\\{x,y\\}\in
E(G)}\textbf{E}[w_{xy}^{H}](q^{*}_{x}-q^{*}_{y})^{2}$
$\displaystyle=\sum_{\\{x,y\\}\in
E(G)}\frac{p_{xy}}{t}\sum_{i=1}^{q}(\frac{tw_{xy}^{G}}{qp_{xy}})(q^{*}_{x}-q^{*}_{y})^{2}$
$\displaystyle=\sum_{\\{x,y\\}\in E(G)}w_{xy}^{G}(q^{*}_{x}-q^{*}_{y})^{2}$
$\displaystyle=\mathtt{Ceff}_{G}(u,v)$

where $w^{I}_{e}$ denotes the weight of the edge $e$ in the graph $I$.

Finally, we have

$\displaystyle\Pr[\mathtt{Reff}_{H}(u,v)<\mathtt{Reff}_{G}(u,v)/\kappa]=$
$\displaystyle\leavevmode\nobreak\
\Pr[\mathtt{Ceff}_{H}(u,v)>\kappa\cdot\mathtt{Ceff}_{G}(u,v)]$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ 1/\kappa,$

where the first step follows from
$\mathtt{Reff}_{G}(u,v)=1/\mathtt{Ceff}_{G}(u,v)$, and the last step follows
from Markov’s inequality. ∎

We now prove Proposition 7.9:

###### Proof of Proposition 7.9.

Runtime. We start with preprocessing. Sampling $C_{6}n$ pairs and checking if
each pair satisfies the edge presence condition for $G$ takes
$O(dC_{6}n)=\mathrm{poly}(d,\log n)n$ time. Preprocessing for the function
$f_{i}$ takes $\mathrm{poly}(d,\log n)n$ time by the preprocessing guarantee
of Theorem 3.7. Since there are $C_{5}\leq\mathrm{poly}(d,\log n)$ different
$i$s, the total preprocessing time is $\mathrm{poly}(d,\log n)n$, as desired.

Next, we reason about query time. This follows immediately from the query time
bound of Theorem 3.7, along the the fact that $C_{5}\leq\mathrm{poly}(d,\log
n)$.

Upper bound. Let $p_{e}^{\text{upper}}=C_{7}/n$ for each edge $e\in E(G[S])$,
where $C_{7}=2C_{3a}C_{3b}^{2}$. We apply Theorem 3.6 to argue that $H_{i}[S]$
is a sparsifier for $G[S]$ for each $i$. By choice of $C_{7}$ and the _Size_
condition on $|S|$, $p_{u,v}^{\text{upper}}\geq\frac{2}{\Phi_{G[S]}^{2}|S|}$.
By Lemma 3.5 and the _Expander_ condition on $G[S]$,
$\frac{2}{\Phi_{G[S]}^{2}|S|}\geq\mathtt{Reff}_{G[S]}(u,v)$ for each pair
$u,v\in S$. Therefore, the second condition of Theorem 3.6 is satisfied by the
probabilities $p_{e}$. Let
$q=10000C(n^{2}/(C_{3a}C_{3c}))\log(n^{2}/(C_{3a}C_{3c}))(C_{7}/n)$, where $C$
is the constant in Theorem 3.6. This value of $q$ satisfies the first
condition of Theorem 3.6.

To apply Theorem 3.6, we just need to show that $H_{i}[S]$ has at least $q$
edges with probability at least $1-1/\mathrm{poly}(n)$. First, note that for
uniformly random $u,v\in X$

$\displaystyle\Pr_{u,v\in X}[\\{u,v\\}\in E(G[S])]$
$\displaystyle=\Pr[\\{u,v\\}\in E(G[S]),u,v\in S]$
$\displaystyle=\Pr[\\{u,v\\}\in E(G[S])|u,v\in S]\Pr[u\in S]\Pr[v\in S]$
$\displaystyle\geq\frac{1}{2C_{3c}}\frac{1}{C_{3a}^{2}}$

by the _Degree_ and _Size_ conditions on $S$. Since at least $C_{6}n$ pairs in
$X\times X$ are chosen, $\textbf{E}[|E(H_{i}[S])|]\geq
C_{6}n(\frac{1}{2C_{3c}})(\frac{1}{C_{3a}^{2}})\geq 2q$. By Chernoff bounds,
this means that $|E(H_{i}[S])|\geq q$ with probability at least
$1-1/\mathrm{poly}(n)$. Therefore, Theorem 3.6 applies and shows that
$H_{i}[S]$ with edge weights $|E(G[S])|/|E(H_{i}[S])|$ is a $(1/6)$-sparsifier
for $G[S]$ with probability at least $1-1/\mathrm{poly}(n)$. By Chernoff
bounds, $|E(G[S])|/|E(H_{i}[S])|\geq|E(G)|/(2|E(H_{i})|)$, so
$\mathtt{Reff}_{H_{i}[S]}(u,v)\leq\mathtt{Reff}_{G[S]}(u,v)(1+1/6)2\leq
C_{4}\mathtt{Reff}_{G[S]}(u,v)$ for all $u,v\in S$ by the sparsification
accuracy guarantee. Since this holds for each $i$, the maximum over all $i$
satisfies the guarantee as well, as desired.

Lower bound. Let $p_{e}^{\text{lower}}=1/|E(G)|$ for each edge $e$. Note that
$t=1$, so with $q=|E(H_{i})|$, all edges in the sampled graph should have
weight $tw_{e}/(p_{e}q)=|E(G)|/|E(H_{i})|$. Therefore, by Lemma 7.10, for a
pair $u,v\in X$

$\Pr[\mathtt{Reff}_{H_{i}}(u,v)\leq 4\mathtt{Reff}_{G}(u,v)/5]\leq\frac{4}{5}$

for each $i$. Since the $H_{i}$s are chosen independently and identically,

$\Pr[\max_{i}\mathtt{Reff}_{H_{i}}(u,v)\leq
4\mathtt{Reff}_{G}(u,v)/5]\leq\left(\frac{4}{5}\right)^{C_{5}}\leq\frac{1}{n^{100}}$

Union bounding over all pairs shows that

$\textsc{ReffQuery}(u,v)>(6/7)(4/5)\mathtt{Reff}_{G}(u,v)>\mathtt{Reff}_{G}(u,v)/2$

for all $u,v\in X$ with probability at least
$1-1/n^{98}=1-1/\mathrm{poly}(n)$, as desired. ∎

We now describe the algorithm LowDiamSet. This algorithm simply picks random
vertices $v$ and queries the effective resistance data structure to check that
$v$ is in a set with the desired properties:

1:procedure LowDiamSet($X$)

2: $\textsc{ReffPreproc}(X)$

3: while true do

4: Pick a uniformly random vertex $v$ from $X$

5: $Q_{v}\leftarrow\\{u\in X:\textsc{ReffQuery}(u,v)\leq C_{2}/(2n)\\}$

6: Return $Q_{v}$ if $|Q_{v}|\geq n/C_{1}$

7: end while

8:end procedure

We now prove that this algorithm suffices:

###### Proof of Proposition 7.8.

Size and Low effective resistance diameter. Follows immediately from the
return condition and the fact that for every $u\in Q_{v}$ for the returned
$Q_{v}$,

$\mathtt{Reff}_{G}(u,v)\leq 2\textsc{ReffQuery}(u,v)\leq C_{2}/n$

by the _Lower bound_ guarantee of Proposition 7.9.

Runtime. We start by showing that the while loop terminates after
$\mathrm{poly}(d,\log n)$ iterations with probability at least
$1-1/\mathrm{poly}(n)$. By Proposition 7.5, $G$ is $(d+1)$-dependent. By
Proposition 7.6, $G$ has at least $n^{2}/(8d^{2})$ edges. By Proposition 7.7,
$G$ has a set of vertices $S$ for which $|S|\geq n/(320d^{2})$,
$\Phi_{G[S]}\geq 1/(800d^{2}\log n)$, and for which the minimum degree of
$G[S]$ is at least $n/(80000d^{2})$. By the first condition on $S$,

$\Pr[v\in S]\geq 1/(320d^{2})$

so the algorithm picks a $v$ in $S$ with probability at least
$1-1/\mathrm{poly}(n)$ after at most $32000d^{2}\log n\leq\mathrm{poly}(d,\log
n)$ iterations. By Lemma 3.5 applied to $S$,

$\mathtt{Reff}_{G}(x,y)\leq\mathtt{Reff}_{G[S]}(x,y)\leq\left(\frac{1}{d_{S}(x)}+\frac{1}{d_{S}(y)}\right)\frac{1}{\Phi_{G[S]}^{2}}$

for any $x,y\in S$, where $d_{S}(w)$ denotes the degree of the vertex $w$ in
$G[S]$. By the third property of $S$, $d_{S}(x)\geq n/(80000d^{2})$ and
$d_{S}(y)\geq n/(80000d^{2})$. By this and the second property of $S$,

$\mathtt{Reff}_{G}(x,y)\leq 102400000000d^{6}(\log^{2}n)/n\leq
C_{2}/(2C_{4}n)$

for any $x,y\in S$. $S$ satisfies the conditions required of Proposition 7.9
by choice of the values $C_{3a}$, $C_{3b}$, and $C_{3c}$. Therefore, by the
_Upper bound_ guarantee of Proposition 7.9,

$\textsc{ReffQuery}(u,v)\leq C_{2}/(2n)$

for every $u\in S$ if $v\in S$. Since $|S|\geq n/C_{1}$ by choice of $C_{1}$,
the return statement returns $Q_{v}$ with probability at least
$1-1/\mathrm{poly}(n)$ when $v\in S$. Therefore, the algorithm returns a set
$Q_{v}$ with probability at least $1-1/\mathrm{poly}(n)$ after at most
$\mathrm{poly}(d,\log n)$ iterations.

Each iteration consists of $O(n)$ ReffQuery calls and $O(n)$ additional work.
Therefore, the total work done by the while loop is $\mathrm{poly}(d,\log n)n$
with probability at least $1-1/\mathrm{poly}(n)$. $\textsc{ReffPreproc}(X)$
takes $\mathrm{poly}(d,\log n)n$ by Proposition 7.9. Thus, the total runtime
is $\mathrm{poly}(d,\log n)n$, as desired. ∎

###  7.3 Using low-effective-resistance clusters to sparsify the unweighted IP
graph

In this section, we prove the following result:

######  Proposition 7.11 (Unweighted inner product sparsification).

There is a $\mathrm{poly}(d,\log n)n/\varepsilon^{2}$-time algorithm for
constructing an $\varepsilon$-sparsifier with $O(n/\varepsilon^{2})$ for the
unweighted inner product graph of a set of $n$ points
$X\subseteq\mathbb{R}^{d}$.

To sparsify an unweighted inner product graph, it suffices to apply
Proposition 7.8 repeatedly to partition the graph into $\mathrm{poly}(d,\log
n)$ clusters, each with low effective resistance diameter. We can use this
structure to get a good bound on the leverage scores of edges between
clusters:

######  Proposition 7.12 (bound leverage scores of edges between clusters).

For a $w$-weighted graph $G$ with vertex set $X$ and $n=|X|$, let
$S_{1},S_{2}\subseteq X$ be two sets of vertices, let $R_{1}=\max_{u,v\in
S_{1}}\mathtt{Reff}_{G}(u,v)$, and let $R_{2}=\max_{u,v\in
S_{2}}\mathtt{Reff}_{G}(u,v)$. Then, for any $u\in S_{1}$ and $v\in S_{2}$,

$\displaystyle\mathtt{Reff}_{G}(u,v)\leq 3R_{1}+3R_{2}+\frac{3}{\sum_{x\in
S_{1},y\in S_{2}}w_{xy}}.$

where $w_{xx}=\infty$ for all $x\in X$

###### Proof.

Let $\chi\in\mathbb{R}^{n}$ be the vector with $\chi_{u}=1$, $\chi_{v}=-1$,
and $\chi_{x}=0$ for all $x\in X$ with $x\neq u$ and $x\neq v$. For each
vertex $x\in S_{1}$, let $s_{x}=\sum_{y\in S_{2}}w_{xy}$. For each vertex
$y\in S_{2}$, let $s_{y}=\sum_{x\in S_{1}}w_{xy}$. Let $\tau=\sum_{x\in
S_{1}}s_{x}=\sum_{y\in S_{2}}s_{y}=\sum_{x\in S_{1},y\in S_{2}}w_{xy}$. Write
$\chi$ as a sum of three vectors $d^{(1)},d^{(12)},d^{(2)}\in\mathbb{R}^{n}$
as follows:

$d_{x}^{(1)}=\begin{cases}1-\frac{s_{x}}{\tau}&x=u\\\ -\frac{s_{x}}{\tau}&x\in
S_{1}\setminus\\{u\\}\\\ 0&\text{ otherwise}\\\ \end{cases}$
$d_{x}^{(2)}=\begin{cases}\frac{s_{x}}{\tau}-1&x=v\\\ \frac{s_{x}}{\tau}&x\in
S_{2}\setminus\\{v\\}\\\ 0&\text{ otherwise}\\\ \end{cases}$
$d_{x}^{(12)}=\begin{cases}\frac{s_{x}}{\tau}&x\in S_{1}\\\
-\frac{s_{x}}{\tau}&x\in S_{2}\\\ 0&\text{ otherwise}\\\ \end{cases}$

Notice that $d^{(1)}+d^{(2)}+d^{(12)}=\chi$. Furthermore, notice that
$d^{(1)}=\sum_{x\in S_{1}}p_{x}\chi^{(ux)}$ and $d^{(2)}=\sum_{y\in
S_{2}}q_{y}\chi^{(yv)}$, where $\chi^{(ab)}$ is the signed indicator vector of
the edge from $a$ to $b$ and $\sum_{x\in S_{1}}p_{x}=1$, $\sum_{y\in
S_{2}}q_{y}=1$, and $p_{x}\geq 0$ and $q_{y}\geq 0$ for all $x\in S_{1},y\in
S_{2}$. The function $f(d)=d^{\top}L^{{\dagger}}d$ is convex, so by Jensen’s
Inequality,

$\displaystyle(d^{(1)})^{\top}L_{G}^{{\dagger}}(d^{(1)})$
$\displaystyle\leq\sum_{x\in
S_{1}}p_{x}(\chi^{(ux)})^{\top}L_{G}^{{\dagger}}\chi^{(ux)}$
$\displaystyle\leq\sum_{x\in S_{1}}p_{x}R_{1}$ $\displaystyle\leq R_{1}$

and $(d^{(2)})^{\top}L_{G}^{{\dagger}}(d^{(2)})\leq R_{2}$. Let
$f\in\mathbb{R}^{|E(G)|}$ be the vector with $f_{xy}=\frac{w_{xy}}{\tau}$ for
all $x\in S_{1},y\in S_{2}$ and let $f_{e}=0$ for all other $e\in E(G)$. By
definition of the $s_{u}$s, $f$ is a feasible flow for the electrical flow
optimization problem for the demand vector $d^{(12)}$. Therefore,

$\displaystyle(d^{(12)})^{\top}L_{G}^{{\dagger}}d^{(12)}$
$\displaystyle\leq\sum_{x\in S_{1},y\in S_{2}}\frac{f_{xy}^{2}}{w_{xy}}$
$\displaystyle=\sum_{x\in S_{1},y\in S_{2}}\frac{w_{xy}}{\tau^{2}}$
$\displaystyle=\frac{1}{\tau}$

so we can upper bound $\mathtt{Reff}_{G}(u,v)$ in the following way

$\displaystyle\mathtt{Reff}_{G}(u,v)$
$\displaystyle=(d^{(1)}+d^{(2)}+d^{(12)})^{\top}L_{G}^{{\dagger}}(d^{(1)}+d^{(2)}+d^{(12)})$
$\displaystyle\leq
3(d^{(1)})^{\top}L_{G}^{{\dagger}}d^{(1)}+3(d^{(2)})^{\top}L_{G}^{{\dagger}}d^{(2)}+3(d^{(12)})^{\top}L_{G}^{{\dagger}}d^{(12)}$
$\displaystyle\leq 3R_{1}+3R_{2}+3/\tau$

as desired. ∎

###  7.4 Sampling data structure

In this section, we give a data structure for efficiently sampling pairs of
points $(u,v)\in\mathbb{R}^{d}\times\mathbb{R}^{d}$ with probability
proportional to a constant-factor approximation of $|\langle u,v\rangle|$:

######  Lemma 7.13.

Given a pair of sets $S_{1},S_{2}\subseteq\mathbb{R}^{d}$, there is a data
structure that can be constructed in $\widetilde{O}(d|S_{1}|+|S_{2}|)$ time
that, in $\mathrm{poly}(d\log(|S_{1}|+|S_{2}|))$ time per sample,
independently samples pairs $u\in S_{1},v\in S_{2}$ with probability $p_{uv}$,
where

$\frac{1}{2}\frac{|\langle u,v\rangle|}{\sum_{a\in S_{1},b\in S_{2}}|\langle
a,b\rangle|}\leq p_{uv}\leq 2\frac{|\langle u,v\rangle|}{\sum_{a\in S_{1},b\in
S_{2}}|\langle a,b\rangle|}$

Furthermore, it is possible to query the probability $p_{uv}$ in
$\mathrm{poly}(d\log(|S_{1}|+|S_{2}|))$ time.

To produce this data structure, we use the following algorithm for sketching
$\ell_{1}$-norms:

######  Theorem 7.14 (Theorem 3 in [Ind06]).

An efficiently computable, $\mathrm{poly}(\log d,1/\varepsilon)$-space linear
sketch exists for the $\ell_{1}$ norm. That is, given a $d\in\mathbb{Z}_{\geq
1}$, $\delta\in(0,1)$, and $\varepsilon\in(0,1)$, there is a matrix
$C=\textsc{SketchMatrix}(d,\delta,\varepsilon)\in\mathbb{R}^{\ell\times d}$
and an algorithm $\textsc{RecoverNorm}(s,d,\delta,\varepsilon)$ with the
following properties:

  1. 1.

(Approximation) For any vector $v\in\mathbb{R}^{d}$, with probability at least
$1-\delta$ over the randomness of SketchMatrix, the value
$r=\textsc{RecoverNorm}(Cv,d,\delta,\varepsilon)$ is as follows:

$(1-\varepsilon)\|v\|_{1}\leq r\leq(1+\varepsilon)\|v\|_{1}$

  2. 2.

$\ell=(c/\varepsilon^{2})\log(1/\delta)$ for some constant $c>1$

  3. 3.

(Runtime) SketchMatrix and RecoverNorm take $\widetilde{O}(\ell d)$ and
$\mathrm{poly}(\ell)$ time respectively.

We use this sketching algorithm to obtain the desired sampling algorithm in
the following subroutine:

######  Corollary 7.15.

Given a set $S\subseteq\mathbb{R}^{d}$, an $\varepsilon\in(0,1)$, and a
$\delta\in(0,1)$, there exists a data structure which, when given a query
point $u\in\mathbb{R}^{d}$, returns a $(1\pm\varepsilon)$-multiplicative
approximation to $\sum_{v\in S}|\langle u,v\rangle|$ with probability at least
$1-\delta$. This data structure can be computed in $O(\ell d|S|)$
preprocessing time and takes $\mathrm{poly}(\ell d)$ time per query, where
$\ell=O(\varepsilon^{-2}\log(1/\delta))$.

###### Proof.

Let $n=|S|$ and $C=\textsc{SketchMatrix}(n,\delta,\varepsilon)$. We will show
that the following algorithm returns the desired estimate with probability at
least $1-\delta$:

  1. 1.

Preprocessing:

    1. (a)

Index the rows of $C$ by integers between 1 and $\ell$. Index columns of $C$
by points $v\in S$.

    2. (b)

Compute the vector $x^{(i)}=\sum_{v\in S}C_{iv}v$ for each $i\in\ell$, where
$\ell=(c/\varepsilon^{2})\log(1/\delta)$ for the constant $c$ in Theorem 7.14.

  2. 2.

Given a query point $u\in\mathbb{R}^{d}$,

    1. (a)

Let $y\in\mathbb{R}^{\ell}$ be a vector with $y_{i}=\langle u,x^{(i)}\rangle$
for each $i\in[\ell]$.

    2. (b)

Return $\textsc{RecoverNorm}(y,n,\delta,\varepsilon)$

Approximation. Let $w\in\mathbb{R}^{n}$ be the vector with $w_{v}=\langle
u,v\rangle$ for each $v\in S$. It suffices to show that the number that a
query returns is a $(1\pm\varepsilon)$-approximation to $\|w\|_{1}$. By
definition, $y_{i}=\sum_{v\in S}C_{iv}w_{v}$ for all $i\in[\ell]$ and $v\in
S$, so $y=Cw$. Therefore, by the _Approximation_ guarantee of Theorem 7.14,
$\textsc{RecoverNorm}(y,n,\delta,\varepsilon)$ returns a
$(1\pm\varepsilon)$-approximation to $\|w\|_{1}$ with probability at least
$1-\delta$, as desired.

Preprocessing time. Computing the matrix $C$ takes $\widetilde{O}(n\ell)$ time
by the _Runtime_ guarantee of Theorem 7.14. Computing the vectors $x^{(i)}$
for all $i\in[\ell]$ takes $O(d\ell n)$ time. This is all of the preprocessing
steps, so the total runtime is $\widetilde{O}(d\ell n)$, as desired.

Query time. Each query consists of $\ell$ inner products of $d$ dimensioal
vectors and one call to RecoverNorm, for a total of $O(\ell
d+\mathrm{poly}(\ell))$ work, as desired. ∎

We use this corollary to obtain a sampling algorithm as follows, where
$n=|S_{1}|+|S_{2}|$:

  1. 1.

Preprocessing:

    1. (a)

Use the Corollary 7.15 data structure to $(1\pm 1/(100\log n))$-approximate
$\sum_{v\in S_{2}}|\langle u,v\rangle|$ for each $u\in S_{1}$. Let $t_{u}$ be
this estimate for each $u\in S_{1}$. (one preprocess for $S\leftarrow S_{2}$,
$|S_{1}|$ queries).

    2. (b)

Form a balanced binary tree $\mathcal{T}$ of subsets of $S_{2}$, with $S_{2}$
at the root, the elements of $S_{2}$ at the leaves, and the property that for
every parent-child pair $(P,C)$, $|C|\leq 2|P|/3$.

    3. (c)

For every node $S$ in the binary tree, construct a $(1\pm 1/(100\log
n))$-approximate data structure for $S$.

  2. 2.

Sampling query:

    1. (a)

Sample a point $u\in S_{1}$ with probability $t_{u}/(\sum_{a\in S_{1}}t_{a})$.

    2. (b)

Initialize $S\leftarrow S_{2}$. While $|S|>1$,

      1. i.

Let $P_{1}$ and $P_{2}$ denote the two children of $S$ in $\mathcal{T}$

      2. ii.

Let $s_{1}$ and $s_{2}$ be the $(1\pm 1/(100\log n))$-approximations to
$\sum_{v\in P_{1}}|\langle u,v\rangle|$ and $\sum_{v\in P_{2}}|\langle
u,v\rangle|$ respectively obtained from the data structure for $S$ computed
during preprocessing.

      3. iii.

Reset $S$ to $P_{1}$ with probability $s_{1}/(s_{1}+s_{2})$; otherwise reset
$S$ to $P_{2}$.

    3. (c)

Return the single element in $S$.

  3. 3.

$p_{uv}$ query:

    1. (a)

Return the product of the $O(\log n)$ probabilities attached to ancestor nodes
of the node $\\{v\\}$ in $\mathcal{T}$ for $u$, obtained from the
preprocessing step (as during the sampling query)

$s_{i}/(s_{1}+s_{2})$ is a $(1\pm 1/(100\log n))^{2}$-approximation to
$\Pr[v\in P_{i}|v\in S]$ for each $i\in\\{1,2\\}$. A $v\in S_{2}$ is sampled
with probability proportional to the product of these conditional
probabilities for the ancestors, for which $p_{uv}$ is a $(1+1/(100\log
n))^{2\log n+1}\leq 2$-approximation. The total preprocessing time is
proportional to the size of all sets in the tree, which is at most
$O(|S_{2}|\log|S_{2}|)$. The total query time is also
$\text{polylog}(|S_{1}|+|S_{2}|)\mathrm{poly}(d)$ due to the logarithmic depth
of the query binary tree.

We now expand on this intuition to prove Lemma 7.13:

###### Proof of Lemma 7.13.

We show that the algorithm given just before this proof satisfies this lemma:

Probability guarantee. Consider a pair $u\in S_{1}$, $v\in S_{2}$. Let
$A_{0}=S_{2},A_{1},\ldots A_{k-1},A_{k}=\\{v\\}$ denote the sequence of
ancestor sets of the singleton set $\\{v\\}$ in $\mathcal{T}$. For each
$i\in[k]$, let $B_{i}$ be the child of $A_{i-1}$ besides $A_{i}$ (unique
because $\mathcal{T}$ is binary). For a node $X$ of $\mathcal{T}$, let $s_{X}$
be the $(1\pm 1/(100\log n))$-approximation to $\sum_{v\in X}|\langle
u,v\rangle|$ used by the algorithm. The sampling probability $p_{uv}$ is the
following product of probabilities:

$p_{uv}=\frac{t_{u}}{\sum_{a\in
S_{1}}t_{a}}\prod_{i=1}^{k}\frac{s_{A_{i}}}{s_{A_{i}}+s_{B_{i}}}$

$s_{A_{i}}+s_{B_{i}}$ is a $(1\pm 1/(100\log n))$-approximation to $\sum_{v\in
A_{i-1}}|\langle u,v\rangle|$ by the approximation guarantee of Corollary
7.15. $s_{A_{i}}$ is a $(1\pm 1/(100\log n))$-approximation to $\sum_{v\in
A_{i}}|\langle u,v\rangle|$ by the approximation guarantee of Corollary 7.15.
By these guarantees and the approximation guarantees for the $t_{a}$s for
$a\in S_{1}$, $p_{uv}$ is a $(1\pm 1/(100\log n))^{2k+2}\leq(1\pm
1/2)$-approximation to

$\frac{\sum_{b\in S_{2}}|\langle u,b\rangle|}{\sum_{a\in S_{1},b\in
S_{2}}|\langle a,b\rangle|}\prod_{i=1}^{k}\frac{\sum_{b\in A_{i}}|\langle
u,b\rangle|}{\sum_{b\in A_{i-1}}|\langle u,b\rangle|}=\frac{|\langle
u,v\rangle|}{\sum_{a\in S_{1},b\in S_{2}}|\langle a,b\rangle|}$

as desired, since $k\leq\log n$.

Preprocessing time. Let $\delta=1/n^{1000}$ and
$\ell=(c/\varepsilon^{2})\log(1/\delta)$, where $c$ is the constant from
Theorem 7.14. Approximating all $t_{u}$s takes $\widetilde{O}(\ell
d|S_{2}|)+|S_{1}|\mathrm{poly}(\ell d)=n\mathrm{poly}(\ell d)$ time by
Corollary 7.15. Preprocessing the data structures for each node
$S\in\mathcal{T}$ takes $\sum_{S\in\mathcal{T}}O(\ell d|S|)$ time in total.
Each member of $S_{2}$ is in at most $O(\log n)$ sets in $\mathcal{T}$, since
$\mathcal{T}$ is a balanced binary tree. Therefore,
$\sum_{S\in\mathcal{T}}O(\ell d|S|)\leq\widetilde{O}(n\ell d)$, so the total
preprocessing time is $\widetilde{O}(n\ell d)$, as desired.

Query time. $O(\log n)$ of the data structures attached to sets in
$\mathcal{T}$ are queried per sample query, for a total of $O(\log
n)\mathrm{poly}(\ell d)$ time by Corollary 7.15, as desired.

∎

We use this data structure via a simple reduction to implement the following
data structure, which suffices for our applications:

######  Proposition 7.16.

Given a family $\mathcal{G}$ of sets in $\mathbb{R}^{d}$, a collection of
positive real numbers $\\{\gamma_{S}\\}_{S\in\mathcal{G}}$, and a set
$S_{2}\subseteq\mathbb{R}^{d}$, there is a data structure that can be
constructed in $\widetilde{O}(d(|S_{2}|+\sum_{S\in\mathcal{G}}|S|))$ time
that, in $\mathrm{poly}(d\log(|S_{2}|+\sum_{S\in\mathcal{G}}|S|))$ time per
sample, independently samples pairs $u\in S$ for some $S\in\mathcal{G}$, $v\in
S_{2}$ with probability $p_{uv}$, where

$\frac{\gamma_{S}|\langle
u,v\rangle|}{(\sum_{A\in\mathcal{G}}\gamma_{A})\sum_{a\in A,b\in
S_{2}}|\langle a,b\rangle|}$

is a 2-approximation to $p_{uv}$. Furthermore, it is possible to query the
number $p_{uv}$ in time
$\mathrm{poly}(d\log(|S_{2}|+\sum_{S\in\mathcal{G}}|S|))$ time.

###### Proof.

Define a new set $S_{1}\subseteq\mathbb{R}^{d+\log n}$ as follows, where
$n=|S_{2}|+\sum_{S\in\mathcal{G}}|S|$:

$S_{1}=\cup_{S\in\mathcal{G}}\\{f_{S}(u)\forall u\in S\\}$

where the function $f_{S}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ is defined
as follows for any set $S\in\mathcal{G}$:

$f_{S}(u)=\frac{\gamma_{S}(u,\text{id}(u))}{\sum_{a\in S,b\in S_{2}}|\langle
a,b\rangle|}$

where $\text{id}:\cup_{S\in\mathcal{G}}S\rightarrow\\{0,1\\}^{\log n}$ is a
function that outputs a unique ID for each element of
$\cup_{S\in\mathcal{G}}S$. Define $f(u)=f_{S}(u)$ for the unique $S$
containing $u$ (Without loss of generality assume that exactly one $S$
contains u ). Let $S_{2}^{\prime}=\\{(x,0^{\log n})\forall x\in S_{2}\\}$.
Construct the data structure $\mathcal{D}$ from Lemma 7.13 on the pair of sets
$S_{1},S_{2}^{\prime}$. Now, sample a pair of $d$-dimensional vectors as
follows:

  1. 1.

Sample:

    1. (a)

Sample a pair $(x,(y,0^{\log n}))$ from $\mathcal{D}$, where $y\in S_{2}$ and
$x\in\mathbb{R}^{d+\log n}$.

    2. (b)

Since the function id outputs values that are not proportional to one other,
the function $f$ is injective.

    3. (c)

Return the pair $(f^{-1}(x),y)$.

    4. (d)

(For the proof, let $w=f^{-1}(x)$ and let $S$ be the unique set for which
$w\in S$)

This data structure has preprocessing time
$\widetilde{O}(d(|S_{2}^{\prime}|+|S_{1}|))=\widetilde{O}(d(|S_{2}|+\sum_{S\in\mathcal{G}}|S|))$
and sample query time $\mathrm{poly}(d\log n)$ by Lemma 7.13, as desired.
Therefore, we just need to show that it samples a pair $(w,y)$ with the
desired probability. By the probability guarantee for Lemma 7.13 and the
injectivity of the mapping $f$ combined over all $S\in\mathcal{G}$, $p_{wy}$
is 2-approximated by

$\displaystyle\frac{|\langle x,(y,0^{\log n})\rangle|}{\sum_{a\in S_{1},b\in
S_{2}^{\prime}}|\langle a,b\rangle|}$ $\displaystyle=\frac{\gamma_{S}|\langle
w,y\rangle|}{\sum_{A\in\mathcal{G}}\sum_{p\in A,q\in S_{2}}|\langle
p,q\rangle|}$

as desired. ∎

###  7.5 Weighted IP graph sparsification

In this section, we use the tools developed in the previous sections to
sparsify weighted inner product graphs. To modularize the exposition, we
define a partition of the edge set of a weighted inner product graph:

######  Definition 7.17.

For a $w$-weighted graph $G$ and three functions on pairs of vertex sets
$\zeta,\kappa,\delta$, a collection of vertex set family-vertex set pairs
$\mathcal{F}$ is called a $(\zeta,\kappa,\delta)$-_cover_ for $G$ iff the
following property holds:

  1. 1.

(Coverage) For any $e=\\{u,v\\}\in E(G)$, there exists a pair
$(\mathcal{G},S_{1})\in\mathcal{F}$ and an $S_{0}\in\mathcal{G}$ for which
$u\in S_{0},v\in S_{1}$ or $u\in S_{1},v\in S_{0}$, and

$\mathtt{Reff}_{G}(u,v)\leq\frac{\delta(S_{0},S_{1})}{w_{uv}}+\frac{\kappa(S_{0},S_{1})}{\max_{x\in
S_{0},y\in S_{1}}w_{xy}}+\frac{\zeta(S_{0},S_{1})}{\sum_{x\in S_{0},y\in
S_{1}}w_{xy}}$

A $(\zeta,\kappa,\delta)$-cover is said to be $s$-_sparse_ if
$\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\sum_{S_{0}\in\mathcal{G}}((\delta(S_{0},S_{1})+\kappa(S_{0},S_{1}))|S_{0}||S_{1}|+\zeta(S_{0},S_{1}))\leq
s$. A $(\zeta,\kappa)$-cover is said to be $w$-_efficient_ if
$\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\left(|S_{1}|+\sum_{S_{0}\in\mathcal{G}}|S_{0}|\right)\leq
w$. When $\delta=0$, we simplify notation to refer to $(\zeta,\kappa)$-covers
instead.

Given a $(\zeta,\kappa)$-cover for a weighted or unweighted inner product
graph, one can sparsify it using Theorem 3.6 and the sampling data structure
from Proposition 7.16:

######  Proposition 7.18.

Given a set $X\subseteq\mathbb{R}^{d}$ with $n=|X|$ and an $s$-sparse
$w$-efficient $(\zeta,\kappa,\delta)$-cover $\mathcal{F}$ for the weighted
inner product graph $G$ on $X$, and $\varepsilon,\delta\in(0,1)$, there is an

$\displaystyle\mathrm{poly}(d,\log n,\log s,\log
w,\log(1/\delta))(s+w+n)/\varepsilon^{4}$

time algorithm for constructing an $(1\pm\varepsilon)$-sparsifier for $G$ with
$O(n\log n/\varepsilon^{2})$ edges with probability at least $1-\delta$.

1:procedure OversamplingWithCover($X,\mathcal{F},\varepsilon,\delta$)

2: (for analysis only: define $r_{uv}$ for each pair $u,v\in X$ as in proof)

3: Construct the Proposition 7.16 data structure
$\mathcal{D}_{(\mathcal{G},S_{1})}$ with $\gamma_{S}=\zeta(S,S_{1})$ for each
$S\in\mathcal{G}$

4: $t\leftarrow\sum_{u,v\in X}r_{uv}$

5: $q\leftarrow C\cdot\varepsilon^{-2}\cdot t\log t\cdot\log(1/\delta)$

6: Initialize $H$ to be an empty graph

7: for $i=1\to q$ do

8: Sample one $e=\\{u,v\\}\in X\times X$ with probability $r_{e}/t$ by
sampling $\\{u,v\\}$ uniformly or from some data structure
$\mathcal{D}_{(\mathcal{G},S_{1})}$ (see proof for details)

9: Add that edge with weight $w_{e}t/(r_{e}q)$ to graph $H$ (note: $r_{e}$ can
be computed in $\mathrm{poly}(d,\log w)$ by the $p_{uv}$ query time in Prop
7.16)

10: end for

11: return Spielman-Srivastava [SS11] applied to $H$

12:end procedure

Algorithm 4

###### Proof.

Filling in algorithm details (the bolded parts). We start by filling in the
details in the algorithm

OversamplingWithCover. First, we define $r_{uv}$ for each pair of distinct
$u,v\in X$. $\\{u,v\\}$ is a weighted edge in $G$ with weight $w_{uv}$. Define

$r_{uv}=2\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\sum_{S_{0}\in\mathcal{G}:u\in
S_{0},v\in S_{1}\text{ or }v\in S_{0},u\in
S_{1}}\left(\delta(S_{0},S_{1})+\kappa(S_{0},S_{1})+\left(\sum_{A\in\mathcal{G}}\zeta(A,S_{1})\right)p_{uv}^{(\mathcal{G},S_{1})}\right)$

where $p_{uv}^{(\mathcal{G},S_{1})}$ is the probability $p_{uv}$ defined for
the data structure $\mathcal{D}^{(\mathcal{G},S_{1})}$ in Proposition 7.16.
Next, we fully describe how to sample pairs $\\{u,v\\}$ with probability
proportional to $r_{uv}$. Notice that $t$ can be computed in $O(w)$ time
because

$\displaystyle t$ $\displaystyle=2\sum_{u,v\in X}r_{uv}$
$\displaystyle=2\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\sum_{S_{0}\in\mathcal{G}}\sum_{u\in
S_{0},v\in
S_{1}}\left(\delta(S_{0},S_{1})+\kappa(S_{0},S_{1})+\left(\sum_{A\in\mathcal{G}}\zeta(A,S_{1})\right)p_{uv}^{(\mathcal{G},S_{1})}\right)$
$\displaystyle=2\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\left(\left(\sum_{A\in\mathcal{G}}\zeta(A,S_{1})\right)+\sum_{S_{0}\in\mathcal{G}}|S_{0}||S_{1}|(\delta(S_{0},S_{1})+\kappa(S_{0},S_{1}))\right)$

can be computed in $O(w)$ time. Sample a pair $\\{u,v\\}$ with probability
equal to $r_{uv}/t$ as follows:

  1. 1.

Sample a pair:

    1. (a)

Sample a Bernoulli
$b\sim\text{Bernoulli}\left(\frac{1}{t}\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\left(\sum_{A\in\mathcal{G}}\zeta(A,S_{1})\right)\right)$.

    2. (b)

If $b=1$

      1. i.

Sample a pair $(\mathcal{G},S_{1})\in\mathcal{F}$ with probability
proportional to $\sum_{A\in\mathcal{G}}\zeta(A,S_{1})$.

      2. ii.

Sample the pair $(u,v)$ using the data structure
$\mathcal{D}^{(\mathcal{G},S_{1})}$.

    3. (c)

Else

      1. i.

Sample a pair $(\mathcal{G},S_{1})\in\mathcal{F}$ with probability
proportional to
$\sum_{S_{0}\in\mathcal{G}}|S_{0}||S_{1}|(\delta(S_{0},S_{1})+\kappa(S_{0},S_{1}))$.

      2. ii.

Sample an $S_{0}\in\mathcal{G}$ with probability proportional to
$|S_{0}|(\delta(S_{0},S_{1})+\kappa(S_{0},S_{1}))$.

      3. iii.

Sample $(u,v)\in S_{0}\times S_{1}$ uniformly.

All sums in the above sampling procedure can be precomputed in
$\mathrm{poly}(d)w$ time. After doing this precomputation, each sample from
the above procedure takes $\mathrm{poly}(d,\log n,\log w)$ time by to
Proposition 7.16 for the last step in the if statement and uniform sampling
from $[0,1]$ with intervals otherwise.

Sparsifier correctness. By the _Coverage_ guarantee of $\mathcal{F}$ and the
approximation guarantee for the $p_{uv}$s in Proposition 7.16,
$w_{uv}\mathtt{Reff}_{G}(u,v)\leq r_{uv}$ for all $u,v\in X$. Therefore,
Theorem 3.6 applies and shows that the graph $H$ returned is a
$(1\pm\varepsilon)$-sparsifier for $G$ with probability at least $1-\delta$.
Spielman-Srivastava only worsens the approximation guarantee by a
$(1+\varepsilon)$ factor, as desired.

Number of edges in $H$. It suffices to bound $q$. In turn, it suffices to
bound $t$. Recall from above that

$\displaystyle t$
$\displaystyle=2\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\left(\left(\sum_{A\in\mathcal{G}}\zeta(A,S_{1})\right)+\sum_{S_{0}\in\mathcal{G}}|S_{0}||S_{1}|(\delta(S_{0},S_{1})+\kappa(S_{0},S_{1}))\right)$
$\displaystyle=2\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\left(\sum_{S_{0}\in\mathcal{G}}\left(|S_{0}||S_{1}|(\delta(S_{0},S_{1})+\kappa(S_{0},S_{1}))+\zeta(S_{0},S_{1})\right)\right)$
$\displaystyle\leq 2s$

since $\mathcal{F}$ is $s$-sparse. Therefore, $q\leq\mathrm{poly}(d,\log
s,\log 1/\delta)s/\varepsilon^{2}$.

Runtime. We start by bounding the runtime to produce $H$. Constructing the
data structure $\mathcal{D}_{(\mathcal{G},S_{1})}$ takes $\mathrm{poly}(d,\log
n,\log w)(|S_{1}|+\sum_{S_{0}\in\mathcal{G}}|S_{0}|)$ time by Proposition
7.16. Therefore, the total time to construct all data structures is at most
$\mathrm{poly}(d,\log n,\log w)w$. Computing $t$ and $q$, as discussed above,
takes $O(w)$ time. $q\leq\mathrm{poly}(d,\log s,\log
1/\delta)s/\varepsilon^{2}$ as discussed above and each iteration of the for
loop takes $\mathrm{poly}(d,\log n,\log w)$ time by the query complexity
bounds of Proposition 7.16. Therefore, the total time required to produce $H$
is at most $\mathrm{poly}(d,\log n,\log s,\log w,\log
1/\delta)(s+w)/\varepsilon^{2}$. Running Spielman-Srivastava requires an
additional $\mathrm{poly}(\log s,\log n)(s/\varepsilon^{2}+n)/\varepsilon^{2}$
time, for a total of $\mathrm{poly}(d,\log n,\log s,\log w,\log
1/\delta)(s+w)/\varepsilon^{4}$ time, as desired. ∎

Therefore, to sparsify weighted inner product graphs, it suffices to construct
an $\mathrm{poly}(d,\log n)n$-sparse, $\mathrm{poly}(d,\log n)n$-efficient
$(\zeta,\kappa)$-cover. We break up this construction into a sequence of
steps:

####  7.5.1 $(\zeta,\kappa)$-cover for unweighted IP graphs

We start by constructing covers for unweighted inner product graphs. The
algorithm repeatedly peels off sets constructed using LowDiamSet and returns
all pairs of such sets. The sparsity of the cover is bounded due to
Proposition 7.12. The efficiency of the cover is bounded thanks to a
$\mathrm{poly}(d,\log n)$ bound on the number of while loop iterations, which
in turn follows from the _Size_ guarantee of Proposition 7.9.

######  Proposition 7.19 (Cover for unweighted graphs).

Given a set $X\subseteq\mathbb{R}^{d}$ with $|X|=n$, there is an
$\mathrm{poly}(d,\log n)$-time algorithm $\textsc{UnweightedCover}(X)$ that,
with probability at least $1-1/\mathrm{poly}(n)$, produces an
$\mathrm{poly}(d,\log n)n$-sparse $\mathrm{poly}(d,\log n)n$-efficient
$(\zeta,\kappa)$-cover for the unweighted inner product graph $G$ on $X$.

Algorithm 5

1:procedure UnweightedCover($X$)

2: Input: $X\subseteq\mathbb{R}^{d}$

3: Output: An sparse, efficient $(\zeta,\kappa)$ cover for the unweighted
inner product graph $G$ on $X$

4: $\mathcal{U}\leftarrow\emptyset$

5: $Y\leftarrow X$

6: while $Y\neq\emptyset$ do $\triangleright$ Finding expanders

7: Let $Q\leftarrow\textsc{LowDiamSet}(Y)$

8: Add the set $Q$ to $\mathcal{U}$

9: Remove the vertices $Q$ from $Y$

10: end while

11: return $\\{(\mathcal{U},S):\forall S\in\mathcal{U}\\}$

12:end procedure

###### Proof.

Let $\mathcal{F}=\textsc{UnweightedCover}(X)$ and define the functions
$\zeta,\kappa$ as follows: $\zeta(S_{0},S_{1})=3$ and
$\kappa(S_{0},S_{1})=C_{2}\left(\frac{3}{|S_{0}|}+\frac{3}{|S_{1}|}\right)$
for any pair of sets $S_{0},S_{1}\subseteq X$. Recall that $C_{2}$ is defined
in the statement of Proposition 7.8.

Number of while loop iterations. We start by showing that there are at most
$\mathrm{poly}(d,\log n)$ while loop iterations with probability at least
$1-1/\mathrm{poly}(n)$. By the _Size_ guarantee of Proposition 7.8, when
LowDiamSet succeeds (which happens with probability $1-1/\mathrm{poly}(n)$),
$Y$ decreases in size by a factor of at least $1-1/p(d,\log n)$ for some fixed
constant degree polynomial $p$. Therefore, after $p(d,\log n)\log
n=\mathrm{poly}(d,\log n)$ iterations, $Y$ will be empty, as desired.
Therefore, $|\mathcal{U}|\leq\mathrm{poly}(d,\log n)$.

Runtime. The runtime follows immediately from the bound on the number of while
loop iterations and the runtime bound on LowDiamSet from Proposition 7.8.

Coverage. For each $S\in\mathcal{U}$, $\max_{u,v\in
S}\mathtt{Reff}_{G}(u,v)\leq\frac{C_{2}}{|S|}$ by the _Low effective
resistance diameter_ guarantee of Proposition 7.8. Plugging this into
Proposition 7.12 immediately shows that $\mathcal{F}$ is a
$(\zeta,\kappa)$-cover for $G$.

Sparsity bound. We bound the desired quantity directly using the fact that
$|\mathcal{U}|\leq\mathrm{poly}(d,\log n)$:

$\displaystyle\sum_{(\mathcal{U},S_{1})\in\mathcal{F}}\sum_{S_{0}\in\mathcal{U}}\left(\kappa(S_{0},S_{1})|S_{0}||S_{1}|+\zeta(S_{0},S_{1})\right)$
$\displaystyle\leq\mathrm{poly}(d,\log
n)\sum_{(\mathcal{U},S_{1})\in\mathcal{F}}\sum_{S_{0}\in\mathcal{U}}(|S_{0}|+|S_{1}|+1)$
$\displaystyle\leq\mathrm{poly}(d,\log n)n$

as desired. ∎

Efficiency bound. Follows immediately from the bound on $|\mathcal{U}|$.

####  7.5.2 $(\zeta,\kappa)$-cover for weighted IP graphs on bounded-norm
vectors

Given a covers for unweighted inner product graphs, it is easy to construct
covers for weighted inner product graphs on bounded norm vectors simply by
removing edge weights and producing the cover. Edge weights only differ by a
factor of $O(d)$ in these two graphs, so effective resistances also differ by
at most that amount. Note that the following algorithm also works for vectors
with norms between $z$ and $2z$ for any real number $z$.

######  Proposition 7.20 (Weighted bounded norm cover).

Given a set $X\subseteq\mathbb{R}^{d}$ with $1\leq\|u\|_{2}\leq 2$ for all
$u\in X$ and $|X|=n$, there is an $n\mathrm{poly}(d,\log n)$ time algorithm
$\textsc{BoundedCover}(X)$ that produces a $\mathrm{poly}(d,\log n)$-sparse,
$\mathrm{poly}(d,\log n)$-efficient $(\zeta,\kappa)$-cover for the weighted
inner product graph $G$ on $X$.

###### Proof.

Let $G_{0}$ be the unweighted inner product graph on $X$. Let $G_{1}$ be the
weighted graph $G$ with all edges that are not in $G_{0}$ deleted. Let
$\mathcal{F}$ be the $(\zeta_{0},\kappa_{0})$-cover given by Proposition 7.19
for $G_{0}$. Let this cover be the output of $\textsc{BoundedCover}(X)$. It
suffices to show that $\mathcal{F}$ is a $(\zeta,\kappa)$-cover for $G$, where
$\zeta=8d\zeta_{0}$ and $\kappa=8d\kappa_{0}$. By Rayleigh monotonicity,

$\mathtt{Reff}_{G}(u,v)\leq\mathtt{Reff}_{G_{1}}(u,v)$

for all $u,v\in X$. Let $w_{e}$ denote the weight of the edge $e$ in $G_{1}$.
For all edges $e$ in $G_{1}$, $\frac{1}{d+1}\leq w_{e}\leq 4$ by the norm
condition on $X$. Therefore, for all $u,v\in X$,

$\mathtt{Reff}_{G_{1}}(u,v)\leq(d+1)\mathtt{Reff}_{G_{0}}(u,v)$

By the _Coverage_ guarantee on $\mathcal{F}$, there exists a pair
$(\mathcal{G},S_{1})$ and an $S_{0}\in\mathcal{G}$ for which $u\in S_{0},v\in
S_{1}$ or $v\in S_{0},u\in S_{1}$ and

$\mathtt{Reff}_{G_{1}}(u,v)\leq(d+1)\left(\kappa_{0}(S_{0},S_{1})+\frac{\zeta_{0}(S_{0},S_{1})}{|S_{0}||S_{1}|}\right)$

By the upper bound on the edge weights for $G_{1}$,

$\mathtt{Reff}_{G_{1}}(u,v)\leq
4(d+1)\left(\frac{\kappa_{0}(S_{0},S_{1})}{\max_{x\in S_{0},y\in
S_{1}}w_{xy}}+\frac{\zeta_{0}(S_{0},S_{1})}{\sum_{x\in S_{0},y\in
S_{1}}w_{xy}}\right)$

Since $4(d+1)\leq 8d$, $\mathcal{F}$ is a $(\zeta,\kappa)$-cover for $G$ as
well, as desired. ∎

####  7.5.3 $(\zeta,\kappa)$-cover for weighted IP graphs on vectors with
norms in the set $[1,2]\cup[z,2z]$ for any $z>1$

By the previous subsection, it suffices to cover the pairs $(u,v)$ for which
$\|u\|_{2}\in[1,2]$ and $\|v\|_{2}\in[z,2z]$. This can be done by clustering
using LowDiamSet on the $[z,2z]$-norm vectors. For each cluster $S_{1}$, let
$\mathcal{G}=\\{\\{u\\}:\forall u\in X\text{ with }\|u\|_{2}\in[1,2]\\}$. This
cover is sparse because of the fact that the clusters have low effective
resistance diameter. It is efficient because of the small number of clusters.

######  Proposition 7.21 (Two-scale cover).

Given a set $X\subseteq\mathbb{R}^{d}$ for which $|X|=n$ and
$\|u\|_{2}\in[1,2]\cup[z,2z]$ for all $u\in X$, there is a
$\mathrm{poly}(d,\log n)n$-time algorithm $\textsc{TwoBoundedCover}(X)$ that
produces an $\mathrm{poly}(d,\log n)n$-sparse, $\mathrm{poly}(d,\log
n)$-efficient $(\zeta,\kappa)$-cover for the weighted inner product graph $G$
on $X$.

Algorithm 6

1:procedure TwoBoundedCover($X$)

2: Input: $X\subseteq\mathbb{R}^{d}$, where $\|u\|_{2}\in[1,2]\cup[z,2z]$ for
all $u\in X$

3: Output: An sparse, efficient $(\zeta,\kappa)$ cover for the weighted inner
product graph $G$ on $X$

4: $X_{\text{low}}\leftarrow\\{u\in X:\|u\|_{2}\in[1,2]\\}$

5: $X_{\text{high}}\leftarrow\\{u\in X:\|u\|_{2}\in[z,2z]\\}$

6: $\mathcal{U}\leftarrow\emptyset$

7: $Y\leftarrow X_{\text{high}}$

8: while $Y\neq\emptyset$ do

9: Let $Q\leftarrow\textsc{LowDiamSet}(Y)$

10: Add the set $Q$ to $\mathcal{U}$

11: Remove the vertices $Q$ from $Y$

12: end while

13: return $\\{(\\{\\{u\\}\forall u\in X_{\text{low}}\\},S_{1}):\forall
S_{1}\in\mathcal{U}\\}$

14:
$\cup\textsc{BoundedCover}(X_{\text{low}})\cup\textsc{BoundedCover}(X_{\text{high}})$

15:end procedure

###### Proof.

Suppose that the BoundedCovers returned for $X_{\text{low}}$ and
$X_{\text{high}}$ are $(\zeta_{\text{low}},\kappa_{\text{low}})$ and
$(\zeta_{\text{high}},\kappa_{\text{high}})$-covers respectively. Recall the
value $C_{2}\leq\mathrm{poly}(d,\log n)$ from the statement of Proposition
7.8. Let $w_{uv}=|\langle u,v\rangle|$ denote the weight of the $u$-$v$ edge
in $G$. Let $\mathcal{F}=\textsc{TwoBoundedCover}(X)$ and define the functions
$\zeta,\kappa$ as follows:

$\zeta(S_{0},S_{1})=\begin{cases}\zeta_{\text{low}}(S_{0},S_{1})&\text{if
$S_{0},S_{1}\subseteq X_{\text{low}}$}\\\
\zeta_{\text{high}}(S_{0},S_{1})&\text{if $S_{0},S_{1}\subseteq
X_{\text{high}}$}\\\ 3&\text{if $S_{0}\subseteq X_{\text{low}}$ and
$S_{1}\subseteq X_{\text{high}}$}\\\ \infty&\text{otherwise}\end{cases}$

$\kappa(S_{0},S_{1})=\begin{cases}\kappa_{\text{low}}(S_{0},S_{1})&\text{if
$S_{0},S_{1}\subseteq X_{\text{low}}$}\\\
\kappa_{\text{high}}(S_{0},S_{1})&\text{if $S_{0},S_{1}\subseteq
X_{\text{high}}$}\\\ \frac{24dC_{2}}{|S_{1}|}&\text{if $S_{0}\subseteq
X_{\text{low}}$ and $S_{1}\subseteq X_{\text{high}}$}\\\
\infty&\text{otherwise}\end{cases}$

Number of while loop iterations. A $\mathrm{poly}(d,\log n)$-round bound
follows from the _Size_ bound of Proposition 7.8. For more details, see the
same part of the proof of Proposition 7.19, which used the exact same
algorithm for producing $\mathcal{U}$.

Runtime. Follows immediately from the runtime bounds of LowDiamSet,
BoundedCover, and the number of while loop iterations.

Coverage. Consider a pair $u,v\in X$. We break the analysis up into cases:

Case 1: $u,v\in X_{\text{low}}$. In this case, the _Coverage_ property of
$\textsc{BoundedCover}(X_{\text{low}})$ implies that the pair $(u,v)$ is
covered in $\mathcal{F}$ by Rayleigh monotonicity (since $G_{\text{low}}$ is a
subgraph of $G$, where $G_{\text{low}}$ is the weighted inner product graph
for $X_{\text{low}}$).

Case 2: $u,v\in X_{\text{high}}$. In this case, the _Coverage_ property of
$\textsc{BoundedCover}(X_{\text{high}})$ implies that the pair $(u,v)$ is
covered in $\mathcal{F}$ by Rayleigh monotonicity.

Case 3: $u\in X_{\text{low}}$ and $v\in X_{\text{high}}$. Since $\mathcal{U}$
is a partition of $X_{\text{high}}$, there is a unique pair
$(\mathcal{G},S_{1})\in\mathcal{F}$ for which $\\{u\\}\in\mathcal{G}$ and
$v\in S_{1}$. Let $H$ denote the unweighted inner product graph on
$X_{\text{high}}$. By Rayleigh monotonicity, the fact that
$\frac{z^{2}}{2d}\leq\frac{z^{2}}{d+1}\leq w_{xy}$ for all $\\{x,y\\}\in
E(H)$, and the _Low effective resistance diameter_ guarantee of Proposition
7.8,

$\displaystyle\mathtt{Reff}_{G}(x,y)$
$\displaystyle\leq\mathtt{Reff}_{G_{\text{high}}}(x,y)$
$\displaystyle\leq\frac{2d\mathtt{Reff}_{H}(x,y)}{z^{2}}$
$\displaystyle\leq\frac{2dC_{2}}{z^{2}|S_{1}|}$

for any $x,y\in S_{1}$. Since $z>1$, $w_{xy}\leq 4z^{2}$ for all $x,y\in X$.
Therefore,

$\mathtt{Reff}_{G}(x,y)\leq\frac{8dC_{2}}{\max_{p\in X_{\text{low}},q\in
S_{1}}w_{pq}}$

for any $x,y\in S_{1}$. Therefore, Proposition 7.12 implies the desired
_Coverage_ bound in this case.

Sparsity bound. We use the fact that $|\mathcal{U}|\leq\mathrm{poly}(d,\log
n)$ along with sparsity bounds for BoundedCover from Proposition 7.20 to bound
the sparsity of $\mathcal{F}$ as follows:

$\displaystyle\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\sum_{S_{0}\in\mathcal{G}}(\kappa(S_{0},S_{1})|S_{0}||S_{1}|+\zeta(S_{0},S_{1}))$
$\displaystyle=\text{Sparsity}(\textsc{BoundedCover}(X_{\text{low}}))$
$\displaystyle+\text{Sparsity}(\textsc{BoundedCover}(X_{\text{high}}))$
$\displaystyle+\sum_{u\in
X_{\text{low}},S_{1}\in\mathcal{U}}(\kappa(\\{u\\},S_{1})|S_{1}|+\zeta(\\{u\\},S_{1}))$
$\displaystyle\leq\mathrm{poly}(d,\log
n)n+|X_{\text{low}}||\mathcal{U}|(24dC_{2}+3)$
$\displaystyle\leq\mathrm{poly}(d,\log n)n$

as desired.

Efficiency bound. We use the efficiency bounds of Proposition 7.20 along with
the bound on $|\mathcal{U}|$:

$\displaystyle\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\left(|S_{1}|+\sum_{S_{0}\in\mathcal{G}}|S_{0}|\right)$
$\displaystyle=\text{Efficiency}(\textsc{BoundedCover}(X_{\text{low}}))$
$\displaystyle+\text{Efficiency}(\textsc{BoundedCover}(X_{\text{high}}))$
$\displaystyle+\sum_{S_{1}\in\mathcal{U}}(|S_{1}|+|X_{\text{low}}|)$
$\displaystyle\leq\mathrm{poly}(d,\log
n)n+|X_{\text{high}}|+|\mathcal{U}||X_{\text{low}}|$
$\displaystyle\leq\mathrm{poly}(d,\log n)n$

as desired. ∎

####  7.5.4 $(\zeta,\kappa)$-cover for weighted IP graphs with polylogarithmic
dependence on norm

We now apply the subroutine from the previous subsection to produce a cover
for weighted inner product graphs on vectors with arbitrary norms. However, we
allow the sparsity and efficiency of the cover to depend on the ratio $\tau$
between the maximum and minimum norm of points in $X$. To obtain this cover,
we bucket vectors by norm and call TwoBoundedCover on all pairs of buckets.

######  Proposition 7.22 (Log-dependence cover).

Given a set of vectors $X\subseteq\mathbb{R}^{d}$ with $\tau=\frac{\max_{x\in
X}\|x\|_{2}}{\min_{x\in X}\|x\|_{2}}$ and $n=|X|$, there is a
$\mathrm{poly}(d,\log n,\log\tau)n$-time algorithm $\textsc{LogCover}(X)$ that
produces a $\mathrm{poly}(d,\log n,\log\tau)n$-sparse, $\mathrm{poly}(d,\log
n,\log\tau)n$-efficient $(\zeta,\kappa)$-cover for the weighted inner product
graph $G$ on $X$.

Algorithm 7

1:procedure LogCover($X$)

2: Input: $X\subseteq\mathbb{R}^{d}$

3: Output: An sparse, efficient $(\zeta,\kappa)$ cover for the weighted inner
product graph $G$ on $X$

4: $d_{\min}\leftarrow\min_{x\in X}\|x\|_{2}$, $d_{\max}\leftarrow\max_{x\in
X}\|x\|_{2}$

5: for $i\in\\{0,1,\ldots,\log\tau\\}$ do $X_{i}\leftarrow\\{x\in
X:\|x\|_{2}\in[2^{i}d_{\min},2^{i+1}d_{\min})\\}$

6: end for

7: $\mathcal{F}=\emptyset$

8: for each pair $i,j\in\\{0,1,\ldots,\log\tau\\}$ do

9: Add $\textsc{TwoBoundedCover}(X_{i}\cup X_{j})$ to $\mathcal{F}$

10: end for

11: return $\mathcal{F}$

12:end procedure

###### Proof.

Coverage. For any edge $\\{u,v\\}\in E(G)$, there exists a pair
$i,j\in\\{0,1,\ldots,\log\tau\\}$ for which $u,v\in X_{i}\cup X_{j}$.
Therefore, the _Coverage_ property for $\textsc{TwoBoundedCover}(X_{i}\cup
X_{j})$ (which is part of $\mathcal{F}$) implies that the pair $\\{u,v\\}$ is
covered by $\mathcal{F}$.

Runtime, efficiency, and sparsity. Efficiency and sparsity of $\mathcal{F}$
are at most the sum of the efficiencies and sparsities respectively of the
constituent TwoBoundedCovers, each of which are at most $\mathrm{poly}(d,\log
n)n$ by Proposition 7.21. There are $O(\log^{2}\tau)$ such covers in
$\mathcal{F}$, so the efficiency and sparsity of $\mathcal{F}$ is at most
$\mathrm{poly}(d,\log n)\log^{2}\tau n\leq\mathrm{poly}(d,\log n,\log\tau)n$,
as desired. Runtime is also bounded due to the fact that there are at most
$\log^{2}\tau$ for loop iterations. ∎

####  7.5.5 Desired $(\zeta,\kappa,\delta)$-cover

Now, we obtain a cover for all $X$ with sparsity, efficiency, and runtime
$\mathrm{poly}(d,\log n)$. To do this, we break up pairs to cover
$\\{u,v\\}\in X\times X$ into two types. Without loss of generality, suppose
that $\|u\|_{2}\leq\|v\|_{2}$. The first type consists of pairs for which
$\|v\|_{2}\leq(dn)^{1000}\|u\|_{2}$. These pairs are covered using several
LogCovers. The total efficiency, sparsity, and runtime required for these
covers is $\mathrm{poly}(d,\log n)n$ due to the fact that each vector is in at
most $\mathrm{poly}(d,\log n)$ of these covers.

The second type consists of all other pairs, i.e. those with
$\|v\|_{2}>(dn)^{1000}\|u\|_{2}$. For these pairs, we take care of them via a
clustering argument. We cluster all vectors in $X$ into $d+1$ clusters in a
greedy fashion. Specifically, we sort vectors in decreasing order by norm and
create a new cluster for a vector $x\in X$ if $|\langle
x,y\rangle|<\frac{1}{d+1}\|x\|_{2}\|y\|_{2}$ for the first vector $y$ in each
cluster. Otherwise, we assign $x$ to an arbitrary cluster for which $|\langle
x,y\rangle|\geq\frac{1}{d+1}\|x\|_{2}\|y\|_{2}$ for first cluster vector $y$.
We then cover the pair $\\{u,v\\}$ using the pair of sets $(\\{u\\},C)$, where
$C$ is the cluster containing $v$. To argue that this satisfies the _Coverage_
property, we exploit the norm condition on the pair $\\{u,v\\}$. To bound
efficiency, sparsity, and runtime, it suffices to bound the number of
clusters, which is at most $d+1$ by Proposition 7.5.

In order to define this algorithm, we use the notion of an _interval family_ ,
which is exactly the same as the one-dimensional interval tree from
computational geometry .

######  Definition 7.23.

For a set $X$ and a function $f:X\rightarrow\mathbb{R}$, define the _interval
family_ for $X$, denoted $\mathcal{X}=\textsc{IntervalFamily}(X)$, to be a
family of sets produced recursively by initializing $\mathcal{X}=\\{X\\}$ and
repeatedly taking an element $S\in\mathcal{X}$, splitting it evenly into two
subsets $S_{0}$ and $S_{1}$ for which $\max_{x\in S_{0}}f(x)\leq\min_{x\in
S_{1}}f(x)$, and adding $S_{0}$ and $S_{1}$ to $\mathcal{X}$ until
$\mathcal{X}$ contains all singleton subsets of $X$.

$\mathcal{X}$ has the property that for any set $S\subseteq X$ consisting of
all $x\in X$ for which $a\leq f(x)\leq b$ for two $a,b\in\mathbb{R}$, $S$ is
the disjoint union of $O(\log|X|)$ sets in $\mathcal{X}$. Furthermore, each
element in $X$ is in at most $O(\log|X|)$ sets in $\mathcal{X}$.

######  Proposition 7.24 (Desired cover).

Given a set $X\subseteq\mathbb{R}^{d}$ with $n=|X|$, there is a
$\mathrm{poly}(d,\log n)n$-time algorithm $\textsc{DesiredCover}(X)$ that
produces a $\mathrm{poly}(d,\log n)n$-sparse, $\mathrm{poly}(d,\log
n)n$-efficient $(\zeta,\kappa,\delta)$-cover for the weighted inner product
graph $G$ on $X$.

Algorithm 8

1:procedure DesiredCover($X$)

2: Input: $X\subseteq\mathbb{R}^{d}$

3: Output: An sparse, efficient $(\zeta,\kappa,\delta)$-cover for the weighted
inner product graph $G$ on $X$, where $\zeta,\kappa$, and $\delta$ are defined
in the proof of Proposition 7.24.

4: $\mathcal{F}\leftarrow\emptyset$

5: $\xi\leftarrow(dn)^{1000}$

6: $d_{\min}\leftarrow\min_{x\in X}\|x\|_{2}$, $d_{\max}\leftarrow\max_{x\in
X}\|x\|_{2}$ $\triangleright$ Cover nearby norm pairs

7: for $i\in\\{0,1,\ldots,\log(d_{\max}/d_{\min})-\lceil\log\xi\rceil$ do

8: $X_{i}\leftarrow\\{x\in X:\|x\|_{2}\in[d_{\min}2^{i},d_{\min}2^{i+1})$

9: Add $\textsc{LogCover}(X_{i}\cup X_{i+1}\cup\ldots\cup
X_{i+\lceil\log\xi\rceil})$ to $\mathcal{F}$

10: end for$\triangleright$ Create approximate basis for spread pairs
$B\leftarrow\emptyset$

11: for $x\in X$ in decreasing order by $\|x\|_{2}$ do

12: if there does not exist $y\in B$ for which $|\langle
x,y\rangle|\geq\|x\|_{2}\|y\|_{2}/(d+1)$ then

13: Add $x$ to $B$ and initialize a cluster $C_{x}=\\{x\\}$

14: else

15: Add $x$ to $C_{y}$ for an arbitrary choice of $y$ satisfying the condition

16: end if

17: end for$\triangleright$ Cover the spread pairs

18: for $w\in B$ do

19: $\mathcal{C}_{w}\leftarrow\textsc{IntervalFamily}(C_{w})$

20: for each set $C\in\mathcal{C}_{w}$ do

21: $\mathcal{G}_{C}\leftarrow$ the family of all singletons of $x\in X$ for
which the disjoint union of $O(\log n)$ sets for $\\{y\in
C_{w}:\|y\|_{2}\geq\xi\|u\|_{2}\\}$ obtained from $\mathcal{C}_{w}$ contains
$C$

22: Add $(\mathcal{G}_{C},C)$ to $\mathcal{F}$

23: end for

24: end forreturn $\mathcal{F}$

25:end procedure

###### Proof.

We start by defining the functions $\zeta,\kappa$, and $\delta$. Let
$\zeta_{i}$ and $\kappa_{i}$ denote the functions for which
$\textsc{LogCover}(Y_{i})$ is a $(\zeta_{i},\kappa_{i})$-cover for the
weighted inner product graph on $Y_{i}$, where $Y_{i}=X_{i}\cup
X_{i+1}\cup\ldots\cup X_{i+\lceil\log\xi\rceil}$ for all
$i\leq\log(d_{\max}/d_{\min})-\lceil\log\xi\rceil$. Let

$\zeta(S_{0},S_{1})=\begin{cases}\sum_{i:S_{0},S_{1}\subseteq
Y_{i},\zeta_{i}(S_{0},S_{1})\neq\infty}\zeta_{i}(S_{0},S_{1})&\text{if there
exists $i$ for which $S_{0},S_{1}\subseteq Y_{i}$}\\\ 2&\text{if
$S_{1}\in\mathcal{C}_{y}$ for some $y\in B$ and $S_{0}=\\{x\\}$ for some
$x$}\\\ &\text{with $\|x\|_{2}\leq\min_{a\in C}\|a\|_{2}/\xi$}\\\
\infty&\text{otherwise}\end{cases}$

$\kappa(S_{0},S_{1})=\begin{cases}\sum_{i:S_{0},S_{1}\subseteq
Y_{i},\kappa_{i}(S_{0},S_{1})\neq\infty}\kappa_{i}(S_{0},S_{1})&\text{if there
exists $i$ for which $S_{0},S_{1}\subseteq Y_{i}$}\\\ 0&\text{if
$S_{1}\in\mathcal{C}_{y}$ for some $y\in B$ and $S_{0}=\\{x\\}$ for some
$x$}\\\ &\text{with $\|x\|_{2}\leq\min_{a\in C}\|a\|_{2}/\xi$}\\\
\infty&\text{otherwise}\end{cases}$

$\delta(S_{0},S_{1})=\begin{cases}0&\text{if there exists $i$ for which
$S_{0},S_{1}\subseteq Y_{i}$}\\\ \frac{1}{|S_{1}|}&\text{if
$S_{1}\in\mathcal{C}_{y}$ for some $y\in B$ and $S_{0}=\\{x\\}$ for some
$x$}\\\ &\text{with $\|x\|_{2}\leq\min_{a\in C}\|a\|_{2}/\xi$}\\\
\infty&\text{otherwise}\end{cases}$

Before proving that the required guarantees are satisfied, we bound some
important quantities.

Bound on $w_{yw}$ in terms of $w_{uy}$ for $y\in C_{w}$ if
$\|y\|_{2}\geq\xi\|u\|_{2}$. By definition of $C_{w}$,
$w_{yw}\geq\frac{1}{d+1}\|y\|_{2}\|w\|_{2}$ for any $y\in C_{w}$. $w$ was the
first member added to $C_{w}$, so $\|w\|_{2}\geq\|y\|_{2}$. By the norm
assumption on $y$, $\|y\|_{2}\geq\xi\|u\|_{2}$. By Cauchy-Schwarz,
$\|y\|_{2}\|u\|_{2}\geq|\langle y,u\rangle|=w_{uy}$. Therefore,

$w_{yw}\geq\frac{\xi}{d+1}w_{uy}$

Bound on $\mathtt{Reff}_{G}(u,w)$ for $w\in B$. We start by bounding the
effective resistance between $u\in X$ and any $w\in B$ for which
$\|w\|_{2}>\xi\|u\|_{2}$. Recall that $w_{xy}=|\langle x,y\rangle|$ for any
$x,y\in X$. Consider any $C\in\mathcal{C}_{w}$ for which $\min_{a\in
C}\|a\|_{2}>\xi\|u\|_{2}$. We show that

$\mathtt{Reff}_{G}(u,w)\leq\frac{2}{\sum_{y\in C}w_{uy}}$

Consider all 2-edge paths of the form $u$-$y$-$w$ for $y\in C$. By assumption
on $C$, $\|y\|_{2}\geq\xi\|u\|_{2}$ for any $y\in C$. Therefore, the bound on
$w_{yw}$ applies:

$w_{yw}\geq\frac{\xi}{d+1}w_{uy}$

for any $y\in C$. By series-parallel reductions, the $u$-$w$ effective
resistance is at most

$\displaystyle\mathtt{Reff}_{G}(u,w)$ $\displaystyle\leq\frac{1}{\sum_{y\in
C}\frac{1}{1/w_{uy}+1/w_{yw}}}$ $\displaystyle\leq\frac{1}{\sum_{y\in
C}\frac{1}{(1+(d+1)/\xi)/w_{uy}}}$ $\displaystyle\leq\frac{2}{\sum_{y\in
C}w_{uy}}$

as desired.

Bound on $\mathtt{Reff}_{G}(u,y)$ for $y\in C$. Any $y\in C$ has the property
that $\|y\|_{2}\geq\xi\|u\|_{2}$. Therefore, for $y\in C$,
$\mathtt{Reff}_{G}(y,w)\leq\frac{d+1}{\xi w_{uy}}\leq\frac{1}{|C|w_{uy}}$. By
the triangle inequality for effective resistance,

$\mathtt{Reff}_{G}(u,y)\leq\mathtt{Reff}_{G}(u,w)+\mathtt{Reff}_{G}(w,y)\leq\frac{1}{|C|w_{uy}}+\frac{2}{\sum_{a\in
C}w_{ua}}$

Coverage. For any pair $\\{u,v\\}$ for which there exists $i$ with $u,v\in
Y_{i}$, $\\{u,v\\}$ is still covered by $\mathcal{F}$ by the _Coverage_
property of $\textsc{LogCover}(Y_{i})$. Therefore, we may assume that this is
not the case. Without loss of generality, suppose that
$\|v\|_{2}\geq\|u\|_{2}$. Then, by assumption, $\|v\|_{2}\geq\xi\|u\|_{2}$. By
definition of the $C_{w}$s, there exists a $w\in B$ for which $v\in C_{w}$. By
the first property of interval families, the set $\\{x\in
C_{w}:\|x\|_{2}\geq\xi\|u\|_{2}\\}$ is the disjoint union of $O(\log n)$ sets
in $\mathcal{C}_{w}$. Let $C$ be the unique set among these for which $v\in
C$. By our effective resistance bound,

$\displaystyle\mathtt{Reff}_{G}(u,v)$
$\displaystyle\leq\frac{1}{|C|w_{uv}}+\frac{2}{\sum_{x\in C}w_{ux}}$
$\displaystyle=\frac{\delta(\\{u\\},C)}{w_{uv}}+\frac{\kappa(\\{u\\},C)}{\max_{x\in
C}w_{ux}}+\frac{\zeta(\\{u\\},C)}{\sum_{x\in C}w_{ux}}$

so the coverage property for the pair $\\{u,v\\}$ is satisfied within
$\mathcal{F}$ by the pair $(\mathcal{G}_{C},C)$, as desired.

Efficiency. The efficiency of $\mathcal{F}$ is at most the efficiency of the
LogCovers and the remaining part for spread pairs. We start with the
LogCovers. By Proposition 7.22,

$\displaystyle\sum_{i}\text{Efficiency}(\textsc{LogCover}(Y_{i}))$
$\displaystyle\leq\sum_{i}\mathrm{poly}(d,\log|Y_{i}|,\log\xi)|Y_{i}|$
$\displaystyle\leq\sum_{i}\mathrm{poly}(d,\log n)|Y_{i}|$
$\displaystyle\leq(\log\xi+1)\mathrm{poly}(d,\log n)\sum_{i}|X_{i}|$
$\displaystyle\leq\mathrm{poly}(d,\log n)n$

Therefore, we just need to bound the efficiency of the remainder of
$\mathcal{F}$. The efficiency of $\mathcal{F}$ is at most

$\displaystyle\text{Efficiency}(\mathcal{F})$
$\displaystyle=\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}\sum_{S_{0}\in\mathcal{G}}((\delta(S_{0},S_{1})+\kappa(S_{0},S_{1}))|S_{0}||S_{1}|+\zeta(S_{0},S_{1}))$
$\displaystyle=\sum_{i}\text{Efficiency}(\textsc{LogCover}(Y_{i}))$
$\displaystyle+\sum_{w\in
B}\sum_{C\in\mathcal{C}_{w}}\sum_{\\{u\\}\in\mathcal{G}_{C}}(\delta(\\{u\\},C)|C|+\zeta(\\{u\\},C))$
$\displaystyle\leq\mathrm{poly}(d,\log n)n+\sum_{w\in
B}\sum_{C\in\mathcal{C}_{w}}3|\mathcal{G}_{C}|$

By the first property of interval families, each $x\in X$ is present as a
singleton in at most $O(\log n)$ $\mathcal{G}_{C}$s for $C$ that are a subset
of a given $C_{w}$. Therefore,

$\text{Efficiency}(\mathcal{F})\leq\mathrm{poly}(d,\log n)n+\sum_{w\in
B}O(\log n)n$

By Proposition 7.5, $|B|\leq d+1$. Therefore,
$\text{Efficiency}(\mathcal{F})\leq\mathrm{poly}(d,\log n)n$, as desired.

Sparsity. By Proposition 7.22,

$\sum_{i}\text{Sparsity}(\textsc{LogCover}(Y_{i}))\leq\sum_{i}\mathrm{poly}(d,\log
n,\log\xi)|Y_{i}|\leq\mathrm{poly}(d,\log n)n$

Therefore, we may focus on the remaining part for spread pairs. In particular,

$\displaystyle\text{Sparsity}(\mathcal{F})$
$\displaystyle=\sum_{(\mathcal{G},S_{1})\in\mathcal{F}}(|S_{1}|+\sum_{S_{0}\in\mathcal{G}}|S_{0}|)$
$\displaystyle\leq\mathrm{poly}(d,\log n)n$ $\displaystyle+\sum_{w\in
B}\sum_{C\in\mathcal{C}_{w}}(|C|+|\mathcal{G}_{C}|)$
$\displaystyle\leq\mathrm{poly}(d,\log n)n+\sum_{w\in
B}\sum_{C\in\mathcal{C}_{w}}|C|$

where the last inequality follows from the first property of interval
families. By the second property of interval families, each element of $C_{w}$
is in at most $O(\log n)$ sets in $\mathcal{C}_{w}$, so
$\sum_{C\in\mathcal{C}_{w}}|C|\leq O(\log n)|C_{w}|$. Since $|B|\leq d+1$,
$\text{Sparsity}(\mathcal{F})\leq\mathrm{poly}(d,\log n)n$, as desired.

Runtime. The first for loop takes $\sum_{i}\mathrm{poly}(d,\log
n)|Y_{i}|\leq\mathrm{poly}(d,\log n)n$ by Proposition 7.22. The second for
loop takes $O(d|B|n)\leq\mathrm{poly}(d,\log n)n$ by the bound on $|B|$. The
third for loop takes $\mathrm{poly}(d,\log n)n$ by the runtime for
IntervalFamily and the two properties of interval families. Therefore, the
total runtime is $\mathrm{poly}(d,\log n)n$, as desired.

∎

####  7.5.6 Proof of Lemma 7.1

###### Proof of Lemma 7.1.

Follows immediately from constructing the cover $\mathcal{F}$ given by
Proposition 7.24 and plugging that into Proposition 7.18. ∎

##  8 Hardness of Sparsifying and Solving Non-Multiplicatively-Lipschitz
Laplacians

We now define some terms to state our hardness results:

######  Definition 8.1.

For a decreasing function $f$ that is not $(C,L)$-multiplicatively Lipschitz,
there exists a point $x$ for which $f(Cx)\leq C^{-L}f(x)$. Let $x_{0}$ denote
one such point. A set of real numbers $S\subseteq\mathbb{R}_{\geq 0}$ is
called _$\rho$ -discrete_ for some $\rho>1$ if for any pair $a,b\in S$ with
$b>a$, $b\leq\rho a$. A set of points $X\subseteq\mathbb{R}^{d}$ is called
_$\rho$ -spaced_ for some $\rho>1$ if there is some $\rho$-discrete set
$S\subseteq\mathbb{R}_{\geq 0}$ with the property that for any pair $x,y\in
X$, $\|x-y\|_{2}\in S$. $S$ is called the _distance set_ for $X$.

Dim. | Thm. | $d$ | $g(p)$ | $\rho$ | Time
---|---|---|---|---|---
Low | 8.2 | $c^{\log^{*}n}$ | $p$ | $1+16\log(10(L^{1/(4c_{0})}))/L$ | $O(nL^{1/(8c_{0})})$
High | 8.3 | $\log n$ | $e^{p}$ | $1+2\log(10(2^{L^{0.48}}))/L$ | $O(n2^{L^{.48}})$
Table 3: Sparsification Hardness

In this section, we show the following two hardness results:

######  Theorem 8.2 (Low-dimensional sparsification hardness).

Consider a decreasing function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ that is not $(\rho,L)$-multiplicatively
lipschitz for some $L>1$, where $c$ and $c_{0}$ are the constants given in
Theorem 3.25 and $\rho=1+2\log(10L^{1/(4c_{0})})/L$. There is no algorithm
that, given a set of $n$ points $X$ in $d=c^{\log^{*}n}$ dimensions, returns a
sparsifier of the $f$-graph for $X$ in less than $O(nL^{1/(8c_{0})})$ time
assuming SETH.

######  Theorem 8.3 (High-dimensional sparsification hardness).

Consider a decreasing function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ that is not $(\rho,L)$-multiplicatively
Lipschitz for some $L>1$, where $\rho=1+2\log(10(2^{L^{0.48}}))/L$. There is
no algorithm that, given a set of $n$ points $X$ in $d=O(\log n)$ dimensions,
returns a sparsifier of the $f$-graph for $X$ in less than $O(n2^{L^{.48}})$
time assuming SETH.

Both of these results follow from the following reduction:

######  Lemma 8.4.

Consider a decreasing function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ that is not $(\rho,L)$-multiplicatively
Lipschitz for some $L>1$, where $\rho=1+2\log(10n)/L$ and $n>1$. Suppose that
there is an algorithm $\mathcal{A}$ that, when given a set of $n$ points
$X\subseteq\mathbb{R}^{d}$, returns a 2-approximate sparsifier for the
$f$-graph of $X$ with $O(n)$ edges in $\mathcal{T}(n,L,d)$ time. Then, there
is an algorithm (Algorithm 9) that, given two sets
$A,B\subseteq\mathbb{R}^{d}$ for which $A\cup B$ is $\rho$-spaced with
distance set $S$, $k\in S$, and $|A\cup B|=n$, returns whether or not
$\min_{a\in A,b\in B}\|a-b\|_{2}\leq k$ in

$\displaystyle O(\mathcal{T}(|A\cup B|,L,d)+|A\cup B|)$

time.

The reduction described starts by scaling the points in $A\cup B$ by a factor
of $x_{0}/k$ to obtain $\widetilde{A}$ and $\widetilde{B}$ respectively. Then,
it sparsifies the $f$-graph for $\widetilde{A}\cup\widetilde{B}$. Finally, it
computes the weight of the edges in the $\widetilde{A}$-$\widetilde{B}$ cut.
Because $f$ is not multiplicatively Lipschitz and the distance set for
$\widetilde{A}\cup\widetilde{B}$ is spaced, thresholding suffices for solving
the $A\times B$ nearest neighbor problem.

###### Proof of Lemma 8.4.

Consider the following algorithm, BichromaticNearestNeighbor (Algorithm 9),
given below:

Algorithm 9

1:procedure BichromaticNearestNeighbor($A,B,k$) $\triangleright$ Lemma 8.4

2: Given: $A,B\subset\mathbb{R}^{d}$ with the property that $A\cup B$ is
$\rho$-spaced, where $\rho=1+2(\log(10n))/L$, and $k\in S$

3: Returns: whether there are $a\in A,b\in B$ for which $\|a-b\|_{2}\leq k$

4: $\widetilde{A}\leftarrow\\{a\cdot\sqrt{x_{0}}/k\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall a\in A\\}$ $\triangleright$
$\widetilde{A}\subset{\mathbb{R}}^{d}$

5: $\widetilde{B}\leftarrow\\{b\cdot\sqrt{x_{0}}/k\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall b\in B\\}$ $\triangleright$
$\widetilde{B}\subset{\mathbb{R}}^{d}$

6: $H\leftarrow\mathcal{A}(\widetilde{A}\cup\widetilde{B})$ $\triangleright$
$H$ is a 2-approximate sparsifier for the $f$-graph $G$ of
$\widetilde{A}\cup\widetilde{B}$

7: if the total weight of edges between $\widetilde{A}$ and $\widetilde{B}$ in
$H$ is at least $f(x_{0})/2$ then

8: return $\mathsf{true}$

9: else

10: return $\mathsf{false}$

11: end if

12:end procedure

We start by bounding the runtime of this algorithm. Constructing
$\widetilde{A}$ and $\widetilde{B}$ and calculating the total weight of edges
between $\widetilde{A}$ and $\widetilde{B}$ takes $O(n)$ time since $H$ has
$O(n)$ edges. Since the sparsification algorithm is only called once, the
total runtime is therefore $\mathcal{T}(n,L,d)+O(n)$, as desired. For the rest
of the proof, we may therefore focus on correctness.

First, suppose that $\min_{a\in A,b\in B}\|a-b\|_{2}\leq k$. There exists a
pair of points $\widetilde{a}\in\widetilde{A}$,
$\widetilde{b}\in\widetilde{B}$ with
$\|\widetilde{a}-\widetilde{b}\|_{2}\leq\sqrt{x_{0}}$. Since $f$ is a
decreasing function, the edge between $\widetilde{a}$ and $\widetilde{b}$ in
$G$ has weight at least $f(x_{0})$, which means that the total weight of edges
in the $\widetilde{A}$-$\widetilde{B}$ cut in $G$ is at least $f(x_{0})$.
Since $H$ is a 2-approximate sparsifier for $G$, the total weight of edges in
the $\widetilde{A}$-$\widetilde{B}$ cut is at least $f(x_{0})/2$. This means
that $\mathsf{true}$ is returned, as desired.

Next, suppose that $\min_{a\in A,b\in B}\|a-b\|_{2}>k$. Since $A\cup B$ is
$\rho$-spaced with distance set $S$ and $k\in S$, $\|a-b\|_{2}\geq\rho\cdot k$
for all $a\in A$ and $b\in B$. Therefore,
$\|\widetilde{a}-\widetilde{b}\|_{2}\geq\rho\cdot\sqrt{x_{0}}$ for all
$\widetilde{a}\in\widetilde{A}$ and $\widetilde{b}\in\widetilde{B}$.

Since $f$ is decreasing and not $(\rho,L)$-multiplicatively Lipschitz, the
weight of any edge between $\widetilde{A}$ and $\widetilde{B}$ in $G$ is at
most

$\displaystyle f(\rho\cdot x_{0})\leq f(x_{0})/(100n^{2}).$

The total weight of edges between $\widetilde{A}$ and $\widetilde{B}$ is
therefore at most

$\displaystyle n^{2}\cdot(f(x_{0})/(100n^{2}))<f(x_{0})/8.$

Since $H$ is a 2-approximate sparsifier for $G$, the total weight between $C$
and $D$ is at most $f(x_{0})/4<f(x_{0})/2$, so the algorithm returns
$\mathsf{false}$, as desired. ∎

We now prove the theorems:

###### Proof of Theorem 8.2.

Consider an instance of $\ell_{2}$-bichromatic closest pair for
$n=L^{1/(4c_{0})}$ and $d=c^{\log^{*}n}$, where $c$ is the constant given in
the dimension bound of Theorem 3.25 and $c_{0}$ is such that integers have bit
length $c_{0}\log n$ in Theorem 3.25. This consists of two sets of points
$A,B\subseteq\mathbb{R}^{d}$ with $|A\cup B|=n$ for which we wish to compute
$\min_{a\in A,b\in B}\|a-b\|_{2}$. By Theorem 3.25, the coordinates of points
in $A$ are also $c_{0}\log n$ bit integers. Therefore, the set $S$ of possible
$\ell_{2}$ distances between points in $A$ and $B$ is a set of square roots of
integers with $\log d+c_{0}\log n\leq 2c_{0}\log n$ bits. Therefore, $S$ is a
$\rho$-discrete (recall $\rho=1+(2\log(10n))/L$), since
$1+1/n^{2c_{0}}>1+(2\log(10n))/L$. Furthermore, note that $f$ is not
$(\rho,L)$-multiplicatively Lipschitz.

We now describe an algorithm for solving $\ell_{2}$-closest pair on $A\times
B$. Use binary search on the values in $S$ to compute the minimum distance
between points in $A,B$. For each query point $k\in S$, by Lemma 8.4, there is
a

$\displaystyle\mathcal{T}(n,L,d)=O(\mathcal{T}(L^{1/(4c_{0})},L,c^{\log^{*}L})+L^{1/(4c_{0})})$

-time algorithm for determining whether or not the closest pair has distance at most $k$. Therefore, there is a

$\displaystyle
O(\log|S|\cdot(\mathcal{T}(L^{1/(4c_{0})},L,c^{\log^{*}L})+L^{1/4c_{0}}))=\widetilde{O}(L^{1/(4c_{0})}L^{1/(8c_{0})})<O(n^{3/2})$

time algorithm for solving $\ell_{2}$-closest pair on pairs of sets with $n$
points. But this is impossible given SETH by Theorem 3.25, a contradiction.
This completes the result. ∎

###### Proof of Theorem 8.3.

Consider an instance of bichromatic Hamming nearest neighbor search for
$n=2^{L^{0.49}}$ and $d=c_{1}\log n$ for the constant $c_{1}$ in the dimension
bound in Theorem 3.21. This consists of two sets of points
$A,B\subseteq\mathbb{R}^{d}$ with $|A\cup B|=n$ for which we wish to compute
$\min_{a\in A,b\in B}\|a-b\|_{2}$. The coordinates of points in $A$ and $B$
are 0-1. Therefore, the set $S$ of possible $\ell_{2}$ distances between
points in $A$ and $B$ is the set of square roots of integers between 0 and
$c_{1}\log n$, which differ by a factor of at least $1+1/(2c_{1}\log n)>\rho$
(recall $\rho=1+(2\log(10n))/L$). Therefore, $A\cup B$ is $\rho$-spaced. Note
that $f$ is also no $(\rho,L)$-multiplicatively Lipschitz by definition.

We now give an algorithm for solving $\ell_{2}$-closest pair on $A\times B$.
Use binary search on $S$. For each query $k\in S$, Lemma 8.4 implies that one
can check if there is a pair with distance at most $k$ in

$\displaystyle\mathcal{T}(n,L,d)=$ $\displaystyle\leavevmode\nobreak\
O(\mathcal{T}(2^{L^{.49}},L,c_{1}L^{.49})+2^{L^{.49}})$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ O(2^{L^{.49}+L^{.48}})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ n^{1+o(1)}$

time on pairs of sets with $n$ points. But this is impossible given SETH by
Theorem 3.21. This completes the result. ∎

Next, we prove hardness results for solving Laplacian systems. In these
hardness results, we insist that kernels are bounded:

######  Definition 8.5.

Call a function $f:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ _$g(p)$
-bounded_ for a function $g:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$
iff for any pair $a,b>0$ with $b>a$, $f(b)\geq f(a)\cdot g(b/a)$. Call a set
$S\subseteq\mathbb{R}_{\geq 0}$ _$\gamma$ -bounded_ iff $\max_{s\in
S}s\leq\gamma\min_{s\in S,s\neq 0}s$. A set of points
$X\subseteq\mathbb{R}^{d}$ is called _$\gamma$ -boxed_ iff the set of
distances between points in $X$ is $\gamma$-bounded.

Dim. | Thm. | $d$ | $g(p)$ | $\rho$ | Time | $\varepsilon$
---|---|---|---|---|---|---
Low | 8.6 | $c^{\log^{*}n}$ | $p$ | $1+16\log(10(L^{1/(4c_{0})}))/L$ | $n\log(g(\gamma))L^{1/(64c_{0})}$ | $1/(g(\gamma)^{3}2^{\mathrm{poly}(\log n)})$
High | 8.7 | $\log n$ | $e^{p}$ | $1+2\log(10(2^{L^{0.48}}))/L$ | $n\log(g(\gamma))2^{L^{.48}}$ | $1/(g(\gamma)^{3}2^{\mathrm{poly}(\log n)})$
Table 4: Linear System Hardness

We show the following results:

######  Theorem 8.6 (Partial low-dimensional linear system hardness).

Consider a decreasing $g(p)=p$-bounded function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ that is not $(\rho,L)$-multiplicatively
Lipschitz for some $L>1$, where $c$ and $c_{0}$ are the constants given in
Theorem 3.25 and $\rho=1+16\log(10(L^{1/(32c_{0})}))/L$. Assuming SETH, there
is no algorithm that, given a $\gamma$-boxed set of $n$ points $X$ in
$d=c^{\log^{*}n}$ dimensions with $f$-graph $G$ and a vector
$b\in\mathbb{R}^{n}$, returns a
$\varepsilon=1/(g(\gamma)^{3}2^{\mathrm{poly}(\log n)})$-approximate solution
$x\in\mathbb{R}^{n}$ to the geometric Laplacian system $L_{G}x=b$ in less than
$O(n\log(g(\gamma))L^{1/(64c_{0})})$ time.

######  Theorem 8.7 (Partial high-dimensional linear system hardness).

Consider a decreasing $g(p)=e^{p}$-bounded function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ that is not $(\rho,L)$-multiplicatively
Lipschitz for some $L>1$, where $\rho=1+16\log(10(2^{L^{0.48}}))/L$. Assuming
SETH, there is no algorithm that, given a $\gamma$-boxed set of $n$ points $X$
in $d=O(\log n)$ dimensions with $f$-graph $G$ and a vector
$b\in\mathbb{R}^{n}$, returns a
$\varepsilon=1/(g(\gamma)^{3}2^{\mathrm{poly}(\log n)})$-approximate solution
$x\in\mathbb{R}^{n}$ to the geometric Laplacian system $L_{G}x=b$ in less than
$O(n\log(g(\gamma))2^{L^{.48}})$ time assuming SETH.

To prove these theorems, we use the following reduction from bichromatic
nearest neighbors:

######  Lemma 8.8.

Consider a decreasing $g(p)$-bounded function $f:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ that is not $(\rho,L)$-multiplicatively
Lipschitz for some $L>1$, where $\rho=1+16(\log(10n))/L$ and $n>1$. Suppose
that there is an algorithm $\mathcal{A}$ that, given a $\gamma$-boxed set of
$n$ points $X$ in $d$ dimensions with $f$-graph $G$ and a vector
$b\in\mathbb{R}^{n}$, returns an
$\varepsilon=1/(g(\gamma)^{3}2^{\mathrm{poly}(\log n)})$-approximate solution
$x\in\mathbb{R}^{n}$ to the geometric Laplacian system $L_{G}x=b$ in
$\mathcal{T}(n,L,g(\gamma),d)$ time. Then, there is an algorithm that, given
two sets $A,B\subseteq\mathbb{R}^{d}$ for which $A\cup B$ is $\rho$-spaced
with $|S|^{O(1)}$-bounded distance set $S$, $k\in S$, and $|A\cup B|=n$,
returns whether or not $\min_{a\in A,b\in B}\|a-b\|_{2}\leq k$ in

$\displaystyle O((\log n)\mathcal{T}(n,L,g(|S|^{O(1)}),d)+|A\cup B|)$

time.

This reduction works in a similar way to the effective resistance data
structure of Spielman and Srivastava [SS11], but with minor differences due to
the fact that their data structure requires multiplication by incidence matrix
of the graph, which in our case is dense. Our reduction uses Johnson-
Lindenstrauss to embed the points

$\displaystyle v_{s}=L^{\dagger}b_{s}$

for vertices $s$ in the graph $G$ into $O(\log n)$ dimensions in a way that
distorts the distances

$\displaystyle b_{st}^{\top}(L^{\dagger})^{2}b_{st}$

for vertices $s,t$ in $G$ by a factor of at most 2. After computing this
embedding, we build an $O(\log n)$-approximate nearest neighbor data structure
on the resulting points. This allows us to determine whether or not a vertex
in $A$ has a high-weight edge in $G$ to $B$ in almost-constant time. After
looping through all of the edges in $A$ in total time $n^{1+o(1)}$, we
determine whether or not there are any high-weight edges between $A$ and $B$
in $G$, allowing us to answer the bichromatic nearest neighbors decision
problem.

We start by proving a result that links norms of $v_{s}$ to effective
resistances:

######  Proposition 8.9.

In an $n$-vertex graph $G$ with vertices $s$ and $t$,

$\displaystyle
0.5\cdot(\mathtt{Reff}_{G}(s,t))^{2}\leq\|v_{s}-v_{t}\|_{2}^{2}\leq
n\cdot(\mathtt{Reff}_{G}(s,t))^{2}$

###### Proof.

Lower bound. Let $x=v_{t}-v_{s}=L_{G}^{\dagger}b_{st}\in{\mathbb{R}}^{n}$. By
definition,

$\displaystyle\|v_{s}-v_{t}\|_{2}^{2}=$ $\displaystyle\leavevmode\nobreak\
\|x\|_{2}^{2}$ $\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
(x_{s})^{2}+(x_{t})^{2}$ $\displaystyle=$ $\displaystyle\leavevmode\nobreak\
(x_{s})^{2}+(x_{s}-b_{st}^{\top}L_{G}^{\dagger}b_{st})^{2}$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\
(b_{st}^{\top}L_{G}^{\dagger}b_{st})^{2}/2,$

where third step follows from
$x_{t}=x_{s}-b_{st}^{\top}L_{G}^{\dagger}b_{st}$.

Thus we complete the proof of the lower bound.

Upper bound. Next, we prove the upper bound. The maximum and minimum
coordinates of $x$ are $x_{t}$ and $x_{s}$ respectively. By definition of the
pseudoinverse, $\text{image}(L_{G}^{\dagger})=\text{image}(L_{G})$. Therefore,
$\textbf{1}^{\top}x=0$, $x_{s}\leq 0$, and $x_{t}\geq 0$. $x_{s}\leq 0$
implies that for all $i\in[n]$,

$\displaystyle x_{i}\leq x_{s}+b_{st}^{\top}L_{G}^{\dagger}b_{st}\leq
b_{st}^{\top}L_{G}^{\dagger}b_{st}.$

$x_{t}\geq 0$ implies that for all $i\in[n]$,

$\displaystyle x_{i}\geq x_{t}-b_{st}^{\top}L_{G}^{\dagger}b_{st}\geq-
b_{st}^{\top}L_{G}^{\dagger}b_{st}.$

Therefore, $|x_{i}|\leq
b_{st}^{\top}L_{G}^{\dagger}b_{st}=\mathtt{Reff}_{G}(s,t)$ for all $i\in[n]$.
Summing across $i\in[n]$ yields the desired upper bound. ∎

Furthermore, the minimum effective resistance of an edge across a cut is
related to the maximum weight edge across the cut:

######  Proposition 8.10.

In an $m$-edge graph $G$ with vertex set $S$,

$\displaystyle\min_{s\in S,t\notin
S}\mathtt{Reff}_{G}(s,t)\leq\min_{e\in\partial S}(1/w_{e})\leq m\min_{s\in
S,t\notin S}\mathtt{Reff}_{G}(s,t).$

###### Proof.

Lower bound. The lower bound on $\min_{e}1/w_{e}$ follows immediately from the
fact that for any edge $e=\\{s,t\\}$, $\mathtt{Reff}_{G}(s,t)\leq r_{e}$.

Upper bound. For the upper bound, recall that

$\displaystyle\mathtt{Reff}_{G}(s,t)$
$\displaystyle=\min_{f\in\mathbb{R}^{m}:B^{\top}f=b_{st}}\sum_{e\in
E(G)}f_{e}^{2}/w_{e}$
$\displaystyle\geq\min_{f\in\mathbb{R}^{m}:B^{\top}f=b_{st}}\sum_{e\in\partial
S}f_{e}^{2}/w_{e}$
$\displaystyle\geq\left(\min_{f\in\mathbb{R}^{m}:B^{\top}f=b_{st}}\sum_{e\in\partial
S}f_{e}^{2}\right)\left(\min_{e\in\partial S}1/w_{e}\right)$
$\displaystyle\geq\frac{1}{|\partial
S|}\left(\min_{f\in\mathbb{R}^{m}:B^{\top}f=b_{st}}\sum_{e\in\partial
S}|f_{e}|\right)^{2}\left(\min_{e\in\partial S}1/w_{e}\right)$

where the first step follows from definition of effective resistance, the
third step follows from taking $w$ out, and the last step follows from Cauchy-
Schwarz.

Since $s\in S$ and $t\notin S$, $\sum_{e\in\partial S}|f_{e}|\geq 1$.
Therefore,

$\displaystyle\mathtt{Reff}_{G}(s,t)\geq\frac{1}{m}\min_{e\in\partial
S}1/w_{e}$

completing the upper bound. ∎

######  Proposition 8.11.

Consider an $n$-vertex connected graph $G$ with edge weights
$\\{w_{e}\\}_{e\in G}$, two matrices $Z,\widetilde{Z}\in\mathbb{R}^{k\times
n}$ with rows $\\{z_{i}\\}_{i=1}^{k}$ and $\\{\widetilde{z}_{i}\\}_{i=1}^{k}$
respectively for $k\leq n$, and $\varepsilon\in(1/n,1)$. Suppose that both of
the following properties hold:

  1. 1.

$\|z_{i}-\widetilde{z}_{i}\|_{L_{G}}\leq
0.01n^{-12}w_{\min}^{2}w_{\max}^{-2}\|z_{i}\|_{L_{G}}$ for all $i\in[k]$,
where $w_{\min}$ and $w_{\max}$ are the minimum and maximum weights of edges
in $G$ respectively

  2. 2.

$(1-\varepsilon/10)\cdot\|L_{G}^{\dagger}b_{st}\|_{2}\leq\|Zb_{st}\|_{2}\leq(1+\varepsilon/10)\cdot\|L_{G}^{\dagger}b_{st}\|$
for any vertices $s,t$ in $G$

Then for any vertices $s,t$ in $G$,

$\displaystyle(1-\varepsilon)\cdot\|L_{G}^{\dagger}b_{st}\|_{2}\leq\|\widetilde{Z}b_{st}\|_{2}\leq(1+\varepsilon)\cdot\|L_{G}^{\dagger}b_{st}\|_{2}.$

###### Proof.

We start by bounding

$\displaystyle((z_{i}-\widetilde{z}_{i})^{\top}b_{st})^{2}$

for each $i\in[k]$. Since $G$ is connected, there is a path from $s$ to $t$
consisting of edges $e_{1},e_{2},\ldots,e_{\ell}$ in that order, where
$\ell\leq n$. By the Cauchy-Schwarz inequality,

$\displaystyle((z_{i}-\widetilde{z}_{i})^{\top}b_{st})^{2}\leq$
$\displaystyle\leavevmode\nobreak\
n\sum_{j=1}^{\ell}((z_{i}-\widetilde{z}_{i})^{\top}b_{e_{j}})^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
(n/w_{\min})\cdot\|z_{i}-\widetilde{z}_{i}\|_{L_{G}}^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
0.01n^{-23}w_{\min}^{3}w_{\max}^{-4}\cdot\|z_{i}\|_{L_{G}}^{2}$

where the last step from property 1 in proposition statement.

By the upper bound on $\|Zb_{s^{\prime}t^{\prime}}\|_{2}$ for any vertices
$s^{\prime},t^{\prime}$ in $G$,
$(z_{i}^{\top}b_{e})^{2}\leq(1+\varepsilon)^{2}b_{e}^{\top}(L_{G}^{\dagger})^{2}b_{e}$
for all edges $e$ in $G$, so

$\displaystyle
0.01n^{-23}w_{\min}^{3}w_{\max}^{-4}\cdot\|z_{i}\|_{L_{G}}^{2}=$
$\displaystyle\leavevmode\nobreak\
0.01n^{-23}w_{\min}^{3}w_{\max}^{-4}\cdot\sum_{e\in
E(G)}w_{e}((z_{i})^{\top}b_{e})^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
0.01n^{-23}w_{\min}^{3}w_{\max}^{-3}\cdot\sum_{e\in
E(G)}((z_{i})^{\top}b_{e})^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
0.01n^{-23}w_{\min}^{3}w_{\max}^{-3}\cdot\sum_{e\in
E(G)}(1+\varepsilon)^{2}b_{e}^{\top}(L_{G}^{\dagger})^{2}b_{e}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
0.01n^{-21}w_{\min}^{3}w_{\max}^{-3}(1+\varepsilon)^{2}\max_{e\in
E(G)}(b_{e}^{\top}(L_{G}^{\dagger})^{2}b_{e})$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
0.04n^{-21}w_{\min}^{3}w_{\max}^{-3}\max_{e\in
E(G)}(b_{e}^{\top}(L_{G}^{\dagger})^{2}b_{e}).$

where the first step follows from $\|z_{i}\|_{L_{G}}^{2}=\sum_{e\in
E}z_{i}^{\top}w_{e}b_{e}b_{e}^{\top}z_{i}$, the second step follows from
$w_{\max}=\max_{e\in G}w_{e}$, and the third step follows from
$(z_{i}^{\top}b_{e})^{2}\leq(1+\varepsilon)^{2}b_{e}^{\top}(L_{G}^{\dagger})b_{e}$,
the forth step follows from summation has at most $n^{2}$ terms, the last step
follows from $(1+\varepsilon)^{2}\leq 4$, $\forall\varepsilon\in(0,1)$.

$L_{G}^{\dagger}b_{e}$ is a vector that is maximized and minimized at the
endpoints of $e$. Furthermore, $\textbf{1}\in\text{kernel}(L_{G}^{\dagger})$
by definition of the pseudoinverse. Thus, we know $L_{G}^{\dagger}b_{e}$ has
both positive and negative coordinates and that
$\|L_{G}^{\dagger}b_{e}\|_{\infty}\leq\max_{i\neq
j}|(L_{G}^{\dagger}b_{e})_{i}-(L_{G}^{\dagger}b_{e})_{j}|\leq
b_{e}^{\top}L_{G}^{\dagger}b_{e}$ .

We have

$\displaystyle\leavevmode\nobreak\
0.04n^{-21}w_{\min}^{3}w_{\max}^{-3}\cdot\max_{e\in
E(G)}b_{e}^{\top}(L_{G}^{\dagger})^{2}b_{e}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
0.04n^{-20}w_{\min}^{3}w_{\max}^{-3}\cdot\max_{e\in
E(G)}(b_{e}^{\top}L_{G}^{\dagger}b_{e})^{2}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ 0.4n^{-20}w_{\min}w_{\max}^{-3}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
0.4n^{-16}w_{\min}w_{\max}^{-1}\cdot(b_{st}^{\top}L_{G}^{\dagger}b_{st})^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
0.8n^{-16}w_{\min}w_{\max}^{-1}\cdot\|L_{G}^{\dagger}b_{st}\|_{2}^{2}$

where the first step follows from $\max_{e\in
E(G)}b_{e}^{\top}(L_{G}^{\dagger})^{2}b_{e}=\max_{e\in
E}\|L_{G}^{\dagger}b_{e}\|_{2}^{2}\leq n\max_{e\in
E}\|L_{G}^{\dagger}b_{e}\|_{\infty}^{2}\leq n\max_{e\in
E(G)}(b_{e}^{\top}L_{G}^{\dagger}b_{e})^{2}$, the second step follows from
$\max_{e}(b_{e}^{\top}L_{G}^{\dagger}b_{e})^{2}\leq w_{\min}^{-2}$ (the lower
bound in Proposition 8.10), and the third step follows from $w_{\max}^{-2}\leq
n^{4}(b_{st}L_{G}^{\dagger}b_{st})^{2}$ (the upper bound in Proposition 8.10),
and the last step follows from $(b_{st}^{\top}L_{G}^{\dagger}b_{st})^{2}\leq
2\|L_{G}^{\dagger}b_{st}\|_{2}^{2}$ (Since $L_{G}^{\dagger}b_{st}$ is
maximized and minimized at $t$ and $s$ respectively).

Combining these inequalities shows that

$\displaystyle((z_{i}-\widetilde{z}_{i})^{\top}b_{st})^{2}\leq
0.8n^{-16}w_{\min}w_{\max}^{-1}\cdot\|L_{G}^{\dagger}b_{st}\|_{2}^{2}$

Summing over all $i$ and using the fact that $k\leq n$, $\varepsilon>1/n$, and
$w_{\min}\leq w_{\max}$ shows that

$\displaystyle\|(Z-\widetilde{Z})b_{st}\|_{2}^{2}=$
$\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{k}((z_{i}-\widetilde{z}_{i})^{\top}b_{st})^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
0.8kn^{-16}w_{\min}w_{\max}^{-1}\cdot\|L_{G}^{\dagger}b_{st}\|_{2}^{2}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
0.8\varepsilon^{2}n^{-13}w_{\min}w_{\max}^{-1}\cdot\|L_{G}^{\dagger}b_{st}\|_{2}^{2}\leavevmode\nobreak\
$ $\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
0.8\varepsilon^{2}n^{-13}\cdot\|L_{G}^{\dagger}b_{st}\|_{2}^{2}$

Combining this with the given upper and lower bounds on $\|Zb_{st}\|_{2}$
using the triangle inequality yields the desired result. ∎

###### Proof of Lemma 8.8.

Consider the following algorithm BichromaticNearestNeighbor, given below:

Algorithm 10

1:procedure BichromaticNearestNeighborProj($A,B,k$) $\triangleright$ Lemma 8.8

2: Given: $A,B\in\mathbb{R}^{d}$ with the property that $A\cup B$ is
$\rho$-spaced with $|S|^{O(1)}$-bounded distance set , where
$\rho=1+16(\log(10n))/L$, and $k\in S$

3: Returns: whether there are $a\in A,b\in B$ for which $\|a-b\|_{2}\leq k$

4: $C\leftarrow\\{a\cdot\sqrt{x_{0}}/k\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall a\in A\\}$

5: $D\leftarrow\\{b\cdot\sqrt{x_{0}}/k\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall b\in B\\}$

6: $\ell\leftarrow 200\log n$

7: Construct matrix $P\in{\mathbb{R}}^{\ell\times d}$, where each entry is
$1/\sqrt{\ell}$ with prob $1/2$ and $-1/\sqrt{\ell}$ with prob $1/2$

8: $\widetilde{Z}_{i,*}\leftarrow\mathcal{A}(C\cup D,P_{i,*})$ for each
$i\in[\ell]$ $\triangleright$ $P_{i,*},\widetilde{Z}_{i,*}$ denotes row $i$ of
$P\in{\mathbb{R}}^{\ell\times d},\widetilde{Z}\in{\mathbb{R}}^{\ell\times n}$

9: $\widehat{C}\leftarrow\\{\widetilde{Z}\cdot b_{c}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall c\in C\\}$ $\triangleright$
$b_{c}\in\mathbb{R}^{n}$ denotes the indicator vector of the vertex $c$, i.e.
$(b_{c})_{c}=1$ and $(b_{c})_{i}=0$ for all $i\neq c$

10: $\widehat{D}\leftarrow\\{\widetilde{Z}\cdot b_{c}\leavevmode\nobreak\
|\leavevmode\nobreak\ \forall c\in D\\}$

11: $t\leftarrow(\log n)$-approximation to closest $\widehat{C}$-$\widehat{D}$
$\ell_{2}$-distance using Theorem 3.17

12: if $t\leq 3\sqrt{n}(\log n)/f(x_{0})$ then

13: return $\mathsf{true}$

14: else

15: return $\mathsf{false}$

16: end if

17:end procedure

First, we bound the runtime of BichromaticNearestNeighborProj (Algorithm 10).
Computing the sets $C,D$ and the matrix $P$ trivially takes $\widetilde{O}(n)$
time. Computing the matrix $\widetilde{Z}$ takes

$\displaystyle O(\log n)\mathcal{T}(n,L,g(|S|^{O(1)}),d)$

time since the point set $C\cup D$ is $|S|^{O(1)}$-boxed. Computing
$\widehat{C}$ and $\widehat{D}$ takes $\widetilde{O}(n)$ time, as computing
$\widehat{Z}b_{i}$ takes $O(\log n)$ time for each $i\in C\cup D$ since
$b_{i}$ is supported on just one vertex. Computing $t$ takes $n^{1+o(1)}$ time