# Generalizations of Matrix Multiplication
can solve the Light Bulb Problem

Josh Alman Hengjie Zhang<EMAIL_ADDRESS>Columbia University. Supported
in part by NSF Grant CCF-2238221 and a grant from the Simons Foundation (Grant
Number 825870<EMAIL_ADDRESS>Columbia University. Supported in
part by NSF grant CCF2008733 and ONR grant N00014-22-1-2713.

###### Abstract

In the light bulb problem, one is given as input vectors
$x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}\in\\{-1,1\\}^{d}$ which are all
uniformly random. They are all chosen independently except for a planted pair
$(x_{i^{*}},y_{j^{*}})$ which is chosen to have correlation $\rho$ for some
constant $\rho>0$. The goal is to find the planted pair. The light bulb
problem was introduced over 30 years ago by L. Valiant, and is known to have
many applications in data analysis, statistics, and learning theory.

The naive algorithm runs in $\Omega(n^{2})$ time, and algorithms based on
Locality-Sensitive Hashing approach quadratic time as $\rho\to 0$. In 2012, G.
Valiant gave a breakthrough algorithm running in time
$O(n^{(5-\omega)/(4-\omega)})<O(n^{1.615})$, no matter how small $\rho>0$ is,
by making use of fast matrix multiplication. This was subsequently refined by
Karppa, Kaski, and Kohonen in 2016 to running time
$O(n^{2\omega/3})<O(n^{1.582})$, but is essentially the only known approach
for this important problem.

In this paper, we propose a new approach based on replacing fast matrix
multiplication with other _variants_ and _generalizations_ of matrix
multiplication, which can be computed faster than matrix multiplication, but
which may omit some terms one is supposed to compute, and include additional
error terms. Our new approach can make use of a wide class of tensors which
previously had no known algorithmic applications, including tensors which
arise naturally as intermediate steps in border rank methods and in the Laser
method.

We further show that our approach can be combined with locality-sensitive
hashing to design an algorithm whose running time improves as $\rho$ gets
larger. To our knowledge, this is the first algorithm which combines fast
matrix multiplication with hashing for the light bulb problem or any closest
pair problem, and it leads to faster algorithms for small $\rho>0$.

We then focus on tensors for “multiplying” $2\times 2$ matrices; using such
small tensors is typically required for practical algorithms. In this setting,
the best prior algorithm, using Strassen’s algorithm for matrix
multiplication, yields a running time of only $O(n^{1.872})$. We introduce a
new such low-rank tensor we call $T_{2112}$, which has omissions and errors
compared to matrix multiplication, and using it, we design a new algorithm for
the light bulb problem which runs in time $O(n^{1.797})$. We also explain why
we are optimistic that this approach could yield asymptotically faster
algorithms for the light bulb problem.

##  1 Introduction

We’ve known since the work of Strassen [Str73] that designing algebraic
algorithms for matrix multiplication is equivalent to bounding the ranks of
matrix multiplication tensors. Since then, an enormous amount of work has gone
into bounding the ranks of these tensors in various regimes, combining
techniques from algebra, combinatorics, algorithm design, and computer search.
One big reason that so much effort has gone into this problem is that matrix
multiplication has many algorithmic applications; algorithmic problems from
nearly every domain of computation have been reduced to matrix multiplication.

A goal of this paper is to show that tensors other than matrix multiplication
can also have algorithmic applications. In this way, the same techniques which
have been developed for matrix multiplication could be repurposed to lead to
new algorithms. Tensors whose support is a subset of the support of matrix
multiplication have been applied to Boolean matrix multiplication [CU13, KK19,
Har21] and even directly to matrix multiplication [Sch81], but we’re unaware
of applications of any tensors whose support is incomparable with matrix
multiplication (other than a small handful of special problems like polynomial
multiplication).

We focus here on the light bulb problem, a fundamental problem from learning
theory which currently has two best algorithms depending on the parameter
regime: one using fast matrix multiplication, and one using locality-sensitive
hashing. Somewhat surprisingly, there are no known parameter regimes where
combining the two approaches leads to an improved algorithm. Using tensors
other than matrix multiplication, we achieve two main results

  1. 1.

Any tensor can replace matrix multiplication to solve the light bulb problem.
The efficiency of this algorithm comes from a trade-off between the tensor’s
rank and how similar it is to matrix multiplication. We find that, restricted
to small tensors, there are better tensors than matrix multiplication that
lead to improved algorithms.

  2. 2.

Tensors other than matrix multiplication can be combined with locality-
sensitive hashing to yield improved algorithms. We find that the symmetry of
matrix multiplication prevents one from combining it with hashing, but that
sufficiently asymmetric tensors can be improved with hashing.

###  1.1 The Light Bulb Problem

In the light bulb problem for $n$ vectors of dimension $d$ and correlation
$\rho>0$, we are given as input vectors
$x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}\in\\{-1,1\\}^{d}$ which are all picked
uniformly at random, and all picked independently except for a ‘planted pair’
$(x_{i^{*}},y_{j^{*}})$ which is chosen to have correlation $\geq\rho$ (i.e.,
so that $\langle x_{i^{*}},y_{j^{*}}\rangle\geq\rho\cdot d$). The indices
$i^{*}$ and $j^{*}$ of the planted pair are unknown to us, and our goal is to
find them.111The light bulb problem is often stated as a ‘monochromatic’
problem, where we are not told which are ‘$x$’ or ‘$y$’ vectors, but this has
a simple reduction to the ‘bichromatic’ version we define here.

L. Valiant introduced the light bulb problem over 30 years ago [Val88] as a
basic primitive which captures the fundamental task of detecting correlations
among $n$ random variables. It can be seen as a special case of a multitude of
other problems in data analysis, statistics, and learning theory, and for many
of these problems, the fastest known algorithm comes from a reduction to the
light bulb problem. For instance:

  * •

If one would like to detect correlations among random variables with a range
$R$ other than just $\\{-1,1\\}$, one can typically reduce to the light bulb
problem by making use of a locality-sensitive hash function for $R$. For
example, if $R$ is the Euclidean sphere, then one can map points in $R$ to
$\\{-1,1\\}$ by determining which side of a random hyperplane they lie on,
which only slightly decreases the correlation $\rho$, by a constant factor
[Cha02].

  * •

The light bulb problem is a special case of many learning problems, including
learning sparse parities with noise, and learning $k$-Juntas with and without
noise, and the fastest known algorithms for these problems come from reducing
the general case to the light bulb problem [Val12].

Suppose $d=\Theta(\log n)$. The straightforward algorithm for this problem
simply compares each pair of vectors and runs in time $\tilde{O}(n^{2})$.222We
write $\tilde{O}(t)$ to suppress polylog$(t)$ factors. Techniques for nearest
neighbor search like locality-sensitive hashing have been applied to the
problem, culminating in Dubiner’s algorithm [Dub10] which runs in time
$n^{2/(\rho+1)+o(1)}$. This is the fastest known algorithm for larger $\rho$,
but its running time becomes quadratic as $\rho\to 0$. In 2012, G. Valiant
[Val12] gave a breakthrough algorithm running in time $O(n^{1.615})$ no matter
how small the constant $\rho>0$ is. Thereafter, Karppa, Kaski, and Kohonen
[KKK18] improved the running time to $O(n^{1.582})$. This is faster than
Dubiner’s algorithm for all $0<\rho<0.264$. To emphasize, these algorithms
work for any constant $\rho>0$, but give essentially the same running time no
matter how large $\rho$ is.

The key ideas behind these latter two algorithms focus on the dimension $d$,
which is sometimes called the ‘sample complexity’. One would typically like to
keep $d$ low while still solving the problem quickly. It is information-
theoretically necessary to pick $d=\Omega(\log n)$ (since if $d=o(\log n)$,
then by the pigeonhole principle, two of the uncorrelated vectors will be
_equal to_ each other and indistinguishable from the correlated pair).

Interestingly, G. Valiant [Val12] introduced a ‘XOR/Tensor Embedding’
technique, and Karppa, Kaski, and Kohonen [KKK18] gave a more efficient
‘compressed matrices’ implementation, which (roughly) allows one to
efficiently ‘expand’ lower-dimensional vectors, and convert $d=\Theta(\log n)$
to a much larger $d=n^{\Theta(1)}$ with only a negligible decrease in $\rho$.
This allows one to focus on the task of designing faster algorithms for
detecting correlations without worrying about $d$. More precisely, these prior
algorithms consist of two phases solving two different problems: a ‘vector
aggregation’ problem of converting groups of shorter vectors into single
longer vectors, and a ‘light bulb computation’ problem of actually detecting
the correlations among these vectors. The final running time of [Val12] trades
off between the running times of these two problems, and the later work
[KKK18] showed how to make the running time of vector aggregation negligible
compared to the running time of light bulb computation. Both prior algorithms
ultimately solve the light bulb computation problem using fast matrix
multiplication, and we focus in this paper on faster algorithms for this
problem. (See footnote 10 in Section 3 below for more details.)

Despite the importance of the light bulb problem, no approach beyond locality-
sensitive hashing or ‘expand then use fast matrix multiplication’ has been
proposed since the breakthrough almost 10 years ago [Val12], and these known
approaches seem to have hit their limits [KKK18, Alm18]. Furthermore, although
hashing approaches and matrix multiplication approaches have been known for
both the light bulb problem as well as many other closest pair problems for
some time (see, for instance, the survey [AIR18]), there are no known
algorithms for any of these problems which truly combine the two.

In this paper, we propose a new approach to designing faster algorithms for
the light bulb problem by replacing fast matrix multiplication with other
tensors which are _generalizations_ of matrix multiplication, and which can be
computed faster. We also show how hashing methods can be combined with our
approach to design even faster algorithms: while previous matrix
multiplication-based algorithms for the light bulb problem have the same
running time regardless of how large $\rho>0$ is, our new approach yields
algorithms which are faster as $\rho$ gets larger. Before getting into more
detail, we introduce some necessary background.

##### Known Algorithms and Exponents.

The exponent of matrix multiplication, $\omega$, is the smallest real number
such that for any $\varepsilon>0$, one can multiply $n\times n$ matrices over
a field using $O(n^{\omega+\varepsilon})$ field operations333The ‘running
time’ and ‘number of field operations’ are typically related by low-order
terms unless one is working with very large numbers. In principle, $\omega$
might depend on the characteristic of the field, although all known bounds
work equally well over any field, so we will abuse notation and simply refer
to the same $\omega$ for all fields.. Since $n\times n$ matrices have $n^{2}$
entries one must read and write, it is known that $\omega\geq 2$, and the best
known algorithms show $\omega<2.37286$ [CW82, DS13, Wil12, LG14, AW21].

We similarly define the exponent of the light bulb problem, $\omega_{\ell}$,
to be the smallest real number such that for any $\varepsilon>0$, one can
solve the light bulb problem with $n$ vectors, for any constant $\rho>0$, in
time $O(n^{\omega_{\ell}+\varepsilon})$. G. Valiant [Val12] showed that
$\omega_{\ell}\leq(5-\omega)/(4-\omega)<1.615$, and Karppa, Kaski, and Kohonen
[KKK18] later improved this to the best known bound $\omega_{\ell}\leq
2\omega/3<1.582$. Since the input size is only $\tilde{O}(n)$, the
corresponding lower bound is $\omega_{\ell}\geq 1$. However, even showing
$\omega=2$ would only imply that $\omega_{\ell}\leq 4/3$ using the known
algorithms [Val12, KKK18, Alm18].

We will also discuss the _Boolean_ matrix multiplication problem, where we’re
given as input matrices $A,B\in\\{0,1\\}^{n\times n}$, and we need to compute
the matrix product $C=A\times B$ over the Boolean semiring, i.e., the matrix
$C\in\\{0,1\\}^{n\times n}$ given by $C[i,j]=\bigvee_{k=1}^{n}(A[i,k]\wedge
B[k,j])$. Let $\omega_{B}$ denote the smallest real number such that for any
$\varepsilon>0$, one can solve this problem in time
$O(n^{\omega_{B}+\varepsilon})$. It is known that $2\leq\omega_{B}\leq\omega$,
and there are no known algorithms for Boolean matrix multiplication that are
asymptotically faster than the best known matrix multiplication algorithms
(see, e.g., [KK19, Section 1]).

###  1.2 Bilinear Problems

A key technique in this paper will be designing and making use of algorithms
for bilinear problems, wherein one would like to evaluate a prescribed set of
bilinear polynomials when its variables are set to input numbers. Matrix
multiplication is a prominent example, and we will focus particularly on
bilinear problems like this where the inputs and outputs are naturally
formatted as matrices. Bilinear problems which take as input a $q_{i}\times
q_{k}$ matrix $\mathsf{X}$ and a $q_{j}\times q_{k}$ matrix $\mathsf{Y}$, and
output a $q_{i}\times q_{j}$ matrix $\mathsf{Z}$, can be written as a (three-
dimensional) tensor

$T=\sum_{i,i^{\prime}\in[q_{i}],j,j^{\prime}\in[q_{j}],k,k^{\prime}\in[q_{k}]}T(\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}})\cdot\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}},$

where
$T(\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}})\in\mathbb{R}$
is the coefficient of $\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}$ in the
bilinear polynomial we output in entry $\mathsf{Z}_{i^{\prime},j^{\prime}}$.
One can imagine plugging in values for each of the $\mathsf{X}$ and
$\mathsf{Y}$ variables, and then the goal is to compute the coefficient of
each $\mathsf{Z}$ variable. For example, for the $q\times q$ matrix
multiplication problem $T_{q}=\langle q,q,q\rangle$,

$T_{q}(\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}})=\begin{cases}1&\mbox{if
}i=i^{\prime},j=j^{\prime},\text{ and }k=k^{\prime},\\\
0&\mbox{otherwise.}\end{cases}$

###  1.3 Main result when $\rho$ is close to $0$

Our main result, which we will state below, gives a way to use an algorithm
for almost any bilinear problem $T$ to solve the light bulb problem, even if
$T$ only computes some of the terms of matrix multiplication, and if $T$ also
computes other ‘noise’ terms. To state our result, we need to define two
relevant properties of $T$. The first property, the rank of $T$, is a standard
measure of how complicated $T$ is, while the another property, efficacy, is
the property we introduce for measuring how useful $T$ is for solving the
light bulb problem.

##### Rank.

A tensor $T$ has rank $1$ if it can be written in the form

$T=\left(\sum_{i\in[q_{i}],k\in[q_{k}]}\alpha_{i,k}\mathsf{X}_{i,k}\right)\left(\sum_{j\in[q_{j}],k\in[q_{k}]}\beta_{j,k}\mathsf{Y}_{j,k}\right)\left(\sum_{i\in[q_{i}],j\in[q_{j}]}\gamma_{i,j}\mathsf{Z}_{i,j}\right)$

for coefficients $\alpha_{i,k},\beta_{j,k},\gamma_{i,j}\in\mathbb{R}$. More
generally, the rank of $T$, denoted $\mathop{\operatorname{rank}}(T)$, is the
minimum nonnegative integer $k$ such that there are rank $1$ tensors
$T_{1},\ldots,T_{k}$ with $T=T_{1}+\cdots+T_{k}$. Rank is the most prominent
measure of the complexity of a tensor, and rank upper bounds for tensors yield
algorithms for applying that tensor to matrices. For instance, Strassen
[Str69] famously showed that the rank of the tensor $\langle 2,2,2\rangle$ for
multiplying two $2\times 2$ matrices is at most $7$, and hence that one can
multiply $n\times n$ matrices in time $O(n^{\log_{2}7})$.

##### Efficacy.

The second property of $T$, which is a new property we introduce, is its
_efficacy_ 444We were inspired to pick this name by the ‘luminous efficacy’ of
a light bulb, which measures the ratio of how much light is produced and how
much power is consumed. It bears similarity to other known statistical ratios
like the ‘standardized second moment’ and the ‘Fano factor’.. For
$i\in[q_{i}]$ and $j\in[q_{j}]$, the efficacy of $T$ at $(i,j)$ is given by:

$\mathop{\operatorname{eff}}_{i,j}(T):=\frac{\sum_{k\in[q_{k}]}T(\mathsf{X}_{i,k}\mathsf{Y}_{j,k}\mathsf{Z}_{i,j})}{\sqrt{\sum_{i^{\prime}\in[q_{i}],j^{\prime}\in[q_{j}],k,k^{\prime}\in[q_{k}]}T(\mathsf{X}_{i^{\prime},k}\mathsf{Y}_{j^{\prime},k^{\prime}}\mathsf{Z}_{i,j})^{2}}}.$

The numerator of $\mathop{\operatorname{eff}}_{i,j}(T)$ is the sum of the
coefficients of all the entries which are supposed to be included in $Z_{i,j}$
in regular matrix multiplication. The denominator is the $\ell_{2}$ norm of
the vector of coefficients of _all_ the terms which are included in $Z_{i,j}$
in $T$. Hence, one can think of $\mathop{\operatorname{eff}}_{i,j}(T)$ as a
ratio of the ‘signal’ and the ‘noise’ of $T$ for computing the $(i,j)$ output
entry of matrix multiplication.

Then, the efficacy of the whole tensor $T$ is the $\ell_{2}$ norm of the
efficacies of all its output entries:

$\mathop{\operatorname{eff}}(T):=\sqrt{\sum_{i\in[q_{i}],j\in[q_{j}]}\left(\mathop{\operatorname{eff}}_{i,j}(T)\right)^{2}}.$

We will see that $\mathop{\operatorname{eff}}(T)$ measures how useful $T$ is
for solving the light bulb problem from our main result, which shows how one
could improve on the current best exponent $2\omega/3$:

######  Theorem 1.1.

For any tensor $T$, if

$\frac{\log(\mathop{\operatorname{rank}}(T))}{\log(\mathop{\operatorname{eff}}(T))}<\frac{2\omega}{3},$

then

$\omega_{\ell}<\frac{2\omega}{3}.$

Moreover, if $T$ has negligible aggregation time (see Section 1.4 below), then

$\omega_{\ell}<\frac{\log(\mathop{\operatorname{rank}}(T))}{\log(\mathop{\operatorname{eff}}(T))}.$

Hence, as long as $T$ is easy to compute ($\mathop{\operatorname{rank}}(T)$ is
small) and it has a high ratio of signal to noise for computing matrix
multiplication ($\mathop{\operatorname{eff}}(T)$ is large), one can use it to
design a fast algorithm for the light bulb computation problem. (Again, this
algorithm works with this exponent for any constant $\rho>0$, no matter how
small.) We will see shortly that the algorithm consists of applying $T$ to
pairs of carefully-chosen (but simple to construct) matrices, and then doing a
simple analysis of the result. In other words, the algorithm itself is fairly
simple, but the proof of correctness is quite involved.

###  1.4 Aggregation time

The aggregation time assumption in Theorem 1.1 relates to the initial
aggregation step that appears in all prior matrix multiplication-based light
bulb algorithms including ours [Val12, KKK18, Alm18]. In [Val12], aggregation
took a significant amount of time which needed to be “traded off” against
later steps of the algorithm. [KKK18] substantially improved aggregation to
take a negligible amount of time compared to the rest of the algorithm.

The same technique of [KKK18] applies in our setting as well, which makes
aggregation negligible for all the tensors we study. We believe this technique
makes the aggregation time negligible for all possible tensors $T$, although
we’re unable to prove this555Tensors with nonnegligible aggregation time would
have very low efficacy, so that very long vectors are needed in our algorithm,
but extremely low rank so that the algorithm may still be fast; see Appendix A
below for more details..

Nonetheless, we prove in Theorem 1.1 that in order to improve the current best
exponent $2\omega/3$, it suffices to find any tensor $T$ with
$\frac{\log(\mathop{\operatorname{rank}}(T))}{\log(\mathop{\operatorname{eff}}(T))}<\frac{2\omega}{3}$,
ignoring the aggregation time condition. To prove this, we show in Appendix A
below that for any tensor $T$ with nonnegligible aggregation time, if the
quantity
$\frac{\log(\mathop{\operatorname{rank}}(T))}{\log(\mathop{\operatorname{eff}}(T))}$
is less than the current best exponent $2\omega/3$, then one can slightly
modify $T$ to get a new tensor $T^{\prime}$ with negligible aggregation time
which still has
$\frac{\log(\mathop{\operatorname{rank}}(T^{\prime}))}{\log(\mathop{\operatorname{eff}}(T^{\prime}))}<2\omega/3$.

###  1.5 Applying to Matrix Multiplication Generalizations

To demonstrate the promise of Theorem 1.1, we focus on tensors for $2\times 2$
input matrices. (Using the notation above, we focus on $q_{i}=q_{j}=q_{k}=2$.)
This is the size of the tensor for Strassen’s algorithm. As we discuss
shortly, we introduce a new tensor with rank only $5$ which is able to to
achieve a better exponent than Strassen’s algorithm.

We focus on this case for three reasons. First, using such a small tensor is
typically necessary to design a practical algorithm (see, e.g., the
introductions of [HSHVDG16, KK19, Pan18, FBH+22] where practicality concerns
are discussed). Second, using such small tensors lets us more concretely see
how more general tensors can be used, especially in conjunction with locality-
sensitive hashing later. Third, small tensors are typically a good test bed
for further improvements based on larger tensors. (We discuss this in more
detail shortly, in Section 1.7 below.)

##### Three Matrix Multiplication Generalizations.

We apply Theorem 1.1 to three tensors of interest. We will see that applying
it when $T$ is a matrix multiplication tensor recovers the best known bound
$\omega_{\ell}\leq\frac{2}{3}\omega$ of [KKK18], but that other tensors can
yield even faster algorithms, including a new tensor we introduce. See Figure
1 for descriptions of the three tensors; their precise definitions and rank
expressions are given in Section 5 below.

Tensor Name | Rank | Tensor |  Table of $\mathop{\operatorname{eff}}_{i,j}$666The indices $i$ and $j$ are in bold on the left and top of the table, respectively. The efficacy of the whole tensor is given below the table. value of $\mathop{\operatorname{eff}}$, and resulting $\omega_{\ell}$ bound
---|---|---|---
$\langle 2,2,2\rangle$ (Strassen’s algorithm [Str69]) | $7$ |  $(\mathsf{X}_{1,1}\mathsf{Y}_{1,1}+\mathsf{X}_{1,2}\mathsf{Y}_{2,1})\mathsf{Z}_{1,1}\\\ +(\mathsf{X}_{1,1}\mathsf{Y}_{1,2}+\mathsf{X}_{1,2}\mathsf{Y}_{2,2})\mathsf{Z}_{2,1}\\\ +(\mathsf{X}_{2,1}\mathsf{Y}_{1,1}+\mathsf{X}_{2,2}\mathsf{Y}_{2,1})\mathsf{Z}_{1,2}\\\ +(\mathsf{X}_{2,1}\mathsf{Y}_{1,2}+\mathsf{X}_{2,2}\mathsf{Y}_{2,2})\mathsf{Z}_{2,2}$ |  $i$\$j$ 1 2 1 $\sqrt{2}$ $\sqrt{2}$ 2 $\sqrt{2}$ $\sqrt{2}$ $\mathop{\operatorname{eff}}(\langle 2,2,2\rangle)=\sqrt{8}$ $\omega_{\ell}\leq\frac{\log(7)}{\log(\sqrt{8})}<1.872$
$SW$ (Strassen-Winograd identity [Win71]) | $6$ |  $(\mathsf{X}_{1,2}\mathsf{Y}_{2,1})\mathsf{Z}_{1,1}\\\ +(\mathsf{X}_{1,1}\mathsf{Y}_{1,2}+\mathsf{X}_{1,2}\mathsf{Y}_{2,2})\mathsf{Z}_{2,1}\\\ +(\mathsf{X}_{2,1}\mathsf{Y}_{1,1}+\mathsf{X}_{2,2}\mathsf{Y}_{2,1})\mathsf{Z}_{1,2}\\\ +(\mathsf{X}_{2,1}\mathsf{Y}_{1,2}+\mathsf{X}_{2,2}\mathsf{Y}_{2,2})\mathsf{Z}_{2,2}$ |  $i$\$j$ 1 2 1 1 $\sqrt{2}$ 2 $\sqrt{2}$ $\sqrt{2}$ $\mathop{\operatorname{eff}}(SW)=\sqrt{7}$ $\omega_{\ell}\leq\frac{\log(6)}{\log(\sqrt{7})}<1.842$
$T_{2112}$ (new tensor) | $5$ |  $(\mathsf{X}_{1,1}\mathsf{Y}_{1,1}+\mathsf{X}_{1,2}\mathsf{Y}_{2,1}+O(\varepsilon))\mathsf{Z}_{1,1}\\\ +(\mathsf{X}_{1,2}\mathsf{Y}_{2,2}+O(\varepsilon))\mathsf{Z}_{2,1}\\\ +(\mathsf{X}_{2,1}\mathsf{Y}_{1,1}+O(\varepsilon))\mathsf{Z}_{1,2}+\\\ (\mathsf{X}_{2,1}\mathsf{Y}_{1,2}+\mathsf{X}_{2,2}\mathsf{Y}_{2,2}+O(\varepsilon))\mathsf{Z}_{2,2}$ ($O(\varepsilon)$ hides arbitrarily small positive coefficients in terms of a parameter $\varepsilon>0$) |  $i$\$j$ 1 2 1 $\sqrt{2}-O(\varepsilon^{2})$ $1-O(\varepsilon^{2})$ 2 $1-O(\varepsilon^{2})$ $\sqrt{2}-O(\varepsilon^{2})$ $\mathop{\operatorname{eff}}(T_{2112})=\sqrt{6}-O(\varepsilon^{2})$
$\omega_{\ell}\leq\frac{\log(5)}{\log(\sqrt{6}-O(\varepsilon^{2}))}\rightarrow
1.797$
Figure 1: Three tensors with $q=2$ which we use in our algorithm, along with
the resulting bounds on $\omega_{\ell}$ from using them in Theorem 1.1. See
Section 5 below where we define these tensors exactly (without hiding terms in
‘$O(\varepsilon)$’) and give their rank expressions. The tensors $\langle
2,2,2\rangle$ and $SW$ come from classical work on optimizing Strassen’s
algorithm, while $T_{2112}$ and its rank upper bound are both new.

First is the tensor for $2\times 2$ matrix multiplication (denoted $\langle
2,2,2\rangle$). We can calculate that $\mathop{\operatorname{eff}}(\langle
2,2,2\rangle)=\sqrt{8}$, and hence, using Strassen’s bound
$\mathop{\operatorname{rank}}(\langle 2,2,2\rangle)\leq 7$, that
$\omega_{\ell}\leq 1.872$. Prior to this work, this was the smallest known
exponent for the light bulb problem based on a $q=2$ tensor. Note that more
generally, $\mathop{\operatorname{eff}}(\langle n,n,n\rangle)=n^{3/2}$, so
applying Theorem 1.1 to the $n\times n$ matrix multiplication tensor (denoted
$\langle n,n,n\rangle$) for large $n$ yields $\omega_{\ell}\leq\log(R(\langle
n,n,n\rangle))/\log(n^{1.5})\leq\log(n^{\omega+o(1)})/\log(n^{1.5})\rightarrow\frac{2}{3}\omega$,
which recovers the best known exponent for the light bulb problem [KKK18].

Second is the tensor $SW$, which consists of $7$ of the $8$ terms of $2\times
2$ matrix multiplication, and which has rank $6$ via an identity by Winograd
[Win71]. Recent work by Karppa and Kaski [KK19] showed how to apply any tensor
which consists of a subset of the terms of matrix multiplication to design a
Boolean matrix multiplication algorithm. Follow-up work by Harris [Har21]
improved their analysis specifically for the tensor $SW$ to design a practical
(since it is based on a small tensor) algorithm for Boolean matrix
multiplication with exponent $\omega_{B}<2.763$. It was previously unclear how
to use $SW$, or any such ‘subset of matrix multiplication’ tensor, to design
an algorithm for the light bulb problem, or any problem which does not have a
known reduction to Boolean matrix multiplication. Applying our Theorem 1.1 to
$SW$ yields an algorithm with exponent $\omega_{\ell}<1.842$, improving on
Strassen’s algorithm. More generally, for ‘subset of matrix multiplication’
tensors, our bound on $\omega_{\ell}$ is strictly better than $\frac{2}{3}$
times the bound on $\omega_{B}$ which Karppa and Kaski [KK19] achieves, and
equal to $\frac{2}{3}$ times the bound on $\omega_{B}$ which Harris [Har21]
achieves (although [Har21] only applies to some such tensors777It seems
difficult to extend the approach of [Har21] to ‘subset of matrix
multiplication’ tensors with very skewed patterns of terms, whereas [KK19]
applies to all such tensors. In this paper we use a technique to ‘regularize’
the pattern of errors of a tensor (see Section 3.3 below) which seems at a
first glance like it could apply to that setting as well, but unfortunately,
the ‘space of errors’ in that settings is 3-dimensional, whereas we critically
use the fact that it is 2-dimensional here.).

Third is a new rank-$5$ tensor $T_{2112}$ that we design and give a rank bound
for in this paper. In terms of a parameter $\varepsilon>0$, $T_{2112}$ is a
sum of $6$ of the $8$ terms terms of $2\times 2$ matrix multiplication, plus
$7$ additional terms with coefficients $O(\varepsilon)$, which can be made
arbitrarily small by suitably picking $\varepsilon$. (Note that one cannot
eliminate these terms by setting $\varepsilon=0$, since we divide by
$\varepsilon$ when showing that $T_{2112}$ has rank $5$; see Section 5 for
more details.)

Prior work would have concluded by taking the limit $\varepsilon\to 0$ in
$T_{2112}$ that the ‘border rank’ of 6 of the 8 terms of $2\times 2$ matrix
multiplication is $5$. Border rank bounds could be used instead of rank in
conjunction with our approach by using the technique of Bini [Bin80a]. One
advantage of Theorem 1.1 is that it allows one to plug constants
$\varepsilon>0$ into border rank expressions and avoid the complications of
border rank. (Border rank identities are typically harder to find using
numerical methods, and lead to less practical algorithms.) Setting just
$\varepsilon=0.025$ suffices to get the best possible exponent using $q=2$:

######  Theorem 1.2.

There is a tensor $T_{2112}$ with $q=2$ which achieves the exponent
$\omega_{\ell}<1.797.$

Before moving on, we note that a prior identity of Bini [Bin80b] already gave
a different tensor $B$ with (a different) 6 of the 8 terms of $2\times 2$
matrix multiplication, and border rank $5$. However, our tensor $T_{2112}$ has
one advantage over $B$. That is, the pattern of
$\mathop{\operatorname{eff}}_{i,j}(T_{2112})$, with larger entries along the
diagonal, will allow us to use it in conjunction with hashing methods in our
second result.

###  1.6 Main result when $\rho$ is bounded away from $0$, using locality-
sensitive hashing

At a high level, our algorithm for Theorem 1.1 works by first mapping each of
the $n$ different $x$ inputs into one of $q_{i}$ independently random buckets,
and each of the $n$ different $y$ inputs into one of $q_{j}$ independently
random buckets. (Recall that $q_{i},q_{j}$ are two of the parameters defining
the size of the tensor $T$; think of them as $n^{c}$ for a constant $0<c<1$,
for instance by first taking an appropriate ‘Kronecker power’ of $T$.) If the
correlated pair were mapped into buckets $i\in[q_{i}]$ and $j\in[q_{j}]$, then
our algorithm will succeed as long as $\mathop{\operatorname{eff}}_{i,j}(T)$
is large enough. The proof of Theorem 1.1 requires carefully balancing the
parameters so that, when $i$ and $j$ are picked uniformly randomly, then this
becomes fairly likely.

Our second main result shows how to improve Theorem 1.1 by combining it with
one of the most prevalent techniques in nearest neighbor search: locality-
sensitive hashing. The main idea to improve on this is to place the inputs
into buckets using (a variation on) bit sampling locality-sensitive hashing,
instead of uniformly random hashing. In this way, thinking of the buckets as
$\\{-1,1\\}$ bit strings, we know that if the planted pair has correlation
$\rho>0$, then they are likely put into buckets
$i\in\\{-1,1\\}^{\log_{2}(q_{i})}$ and $j\in\\{-1,1\\}^{\log_{2}(q_{j})}$
which also have correlation close to $\rho$. If such buckets have larger
$\mathop{\operatorname{eff}}_{i,j}(T)$ than uniformly random buckets, then we
can speed up our algorithm.

By construction, our new tensor $T_{2112}$ has exactly this property! By
renaming variables888Whenever $i$ or $j$ was $2$, we now call it $-1$. and
taking the limit $\varepsilon\to 0$ for notational simplicity, we see that it
has
$\mathop{\operatorname{eff}}_{1,1}(T_{2112})=\mathop{\operatorname{eff}}_{-1,-1}(T_{2112})=\sqrt{2}$
and
$\mathop{\operatorname{eff}}_{1,-1}(T_{2112})=\mathop{\operatorname{eff}}_{-1,1}(T_{2112})=1$.
More generally, once we’ve taken a Kronecker power so that $q_{i}=q_{j}=q$ is
larger than $2$, the resulting tensor will have the property that, for buckets
$i,j\in\\{-1,1\\}^{\log_{2}(q)}$ with correlation $\rho$, we have
$\mathop{\operatorname{eff}}_{i,j}(T_{2112}^{\otimes\log_{2}(q)})=2^{(1+\rho)(\log_{2}(q)/2)}$,
whereas the median pair $i,j$ of buckets has only
$\mathop{\operatorname{eff}}_{i,j}(T_{2112}^{\otimes\log_{2}(q)})=2^{\log_{2}(q)/2}$.
Thus, in a sense, the efficacy of our tensor $T_{2112}$ is increasing with
$\rho$, resulting in a faster algorithm. (We briefly note that although our
analysis makes use of Kronecker powers of tensors, our algorithm itself does
not, and only applies the tensor itself to input matrices.)

However, the formal statement of our result is more complicated than this
because of a key detail behind Theorem 1.1 that we have thus far swept under
the rug. Rather than map each input point into a single bucket, it actually
makes many copies of each input point and independently maps them into
buckets. This way, in order to solve the light bulb problem, it suffices for
any one pair of copies of the correlated pair to map into buckets with large
efficacy. Typically a locality-sensitive hashing scheme would map all the
different copies of the same vector to the same bucket, and lose these
savings. Nonetheless, we find a way to hash inputs into multiple buckets, so
that the correlated pair is still hashed to correlated buckets, but the
different pairs of buckets are ‘sufficiently independent’ of each other so
that whether or not each succeeds isn’t too correlated. Applying this to
$T_{2112}$, we achieve:

######  Theorem 1.3.

For the tensor $T_{2112}$, the bound of Theorem 1.1 can be improved to

$\displaystyle\omega_{\ell}\leq\begin{cases}\frac{2\log
5}{\log\left(6(1-\rho)^{-\rho/2}(1+\rho)^{\rho/2}(1-\rho^{2})^{1/2}\right)}&\textrm{
when~{}}\rho<1/3,\\\ \frac{4\log 5}{(5+\rho)\log 2}&\textrm{
when~{}}1/3\leq\rho\leq 1.\end{cases}$

The resulting plot of $w_{\ell}$ with respect to $\rho$ from can be found in
Figure 2 (in blue). Our Theorem 1.1, as well as prior matrix multiplication-
based algorithms for the light bulb problem, give the same running time
exponent no matter how large $\rho>0$ is, whereas Theorem 1.3 uses hashing to
improve with $\rho$. We also show Dubiner’s algorithm, which is purely based
on hashing, and is worse for small $\rho>0$, but better for larger $\rho$.

(a) The running time exponent of three different methods in terms of
$\rho\in[0,1]$.

(b) The same plot as in the figure to the left, but focused on the range
$\rho\in[0,0.2]$.

Figure 2: The running time exponents ($y$-axis) of three algorithms in terms
of $\rho$ ($x$-axis): Theorem 1.3 (blue line), Theorem 1.1 using $T_{2112}$
(green line), and Dubiner’s algorithm [Dub10] (orange line).

##### Custom-tailored hash functions for other tensors.

In order to prove Theorem 1.3, we observed that bit sampling locality-
sensitive hashing is likely to put the correlated pair of vectors into buckets
$i,j$ where $i$ and $j$ are correlated, and hence have a higher-than-average
value of $\mathop{\operatorname{eff}}_{i,j}(T_{2112}^{\otimes\log_{2}(q)})$.
What if we are working with a different tensor $T$ for which the value of
$\mathop{\operatorname{eff}}_{i,j}(T)$ does not increase as $i$ and $j$ are
more correlated? Bit sampling locality-sensitive hashing won’t give an
improvement, but this is only one possible hash function.

In fact, we can generalize Theorem 1.3 to almost any tensor. We show that for
any $T$ whose efficacy matrix
$[(\mathop{\operatorname{eff}}_{i,j}(T))^{2}]_{i,j}$ is not ‘degenerate’ in
some sense, one can custom-tailor hash functions for $T$ which result in an
improved running time as $\rho$ grows. The formal statement of this result is
somewhat complicated; we defer the details to Section 4 below. However, for
one simple and important example, we show:

######  Theorem 1.4.

Suppose $T$ is a $\langle q,q,q_{k}\rangle$-sized tensor which consists of a
subset of the terms of a matrix multiplication tensor, and the matrix
$[(\mathop{\operatorname{eff}}_{i,j}(T))^{2}]_{i\in[q],j\in[q]}$ has full
rank. Let $\omega_{\ell}^{\prime}$ be the exponent one would get from $T$ from
applying Theorem 1.1. Then, for every $\rho>0$, there is an $f(T,\rho)>0$ such
that the light bulb computation problem with correlation $\rho$ can be solved
with the improved exponent $\omega_{\ell}^{\prime}-f(T,\rho).$

Theorem 1.4 shows that hashing can improve the algorithm based on almost any
‘subset of matrix multiplication’ tensor. These are the same tensors used by
Karppa and Kaski [KK19] to solve Boolean matrix multiplication (they showed
that bounds on their ranks give bounds on the ‘probabilistic rank’ of matrix
multiplication) and include the tensors other than $\langle 2,2,2\rangle$ that
we discussed above in Section 1.5.

Intuitively, we require the matrix
$[(\mathop{\operatorname{eff}}_{i,j}(T))^{2}]_{i,j}$ to have full rank in
Theorem 1.4 so that there are regions of buckets with higher efficacy that we
could hope to hash the correlated pair to. For instance, if $T$ is a matrix
multiplication tensor, then hashing cannot move the correlated pair to a
better bucket since all buckets have the same efficacy, and indeed, the
efficacy matrix has rank 1 since all its entries are equal.

###  1.7 Comparison with Prior Work on Tensor and Nearest Neighbor Search
Algorithms

##### Other Variants on Matrix Multiplication.

As mentioned at the beginning of Section 1, prior work has solved Boolean
matrix multiplication using tensors whose support is (a subset of) the support
of matrix multiplication [CU13, KK19, Har21]. To our knowledge, we are the
first to use tensors whose support may not be a subset of the support of
matrix multiplication, and the first to use variants of matrix multiplication
on a problem that is not (reducible to) Boolean matrix multiplication. This
access to a larger class of tensors is what allows us to design a faster
practical algorithm for the light bulb problem than the analogous fastest
practical algorithm for Boolean matrix multiplication; our tensor $T_{2112}$
cannot be applied in the other settings (for fixed $\varepsilon>0$). We hope
our techniques could be used to apply these tensors to other problems in the
future, particularly problems which are currently solved with exact matrix
multiplication but which may only need approximate matrix multiplication.

##### Improving the asymptotic exponent

We are optimistic that Theorem 1.1 can be used to improve the best known
exponent for the light bulb problem by using larger tensors. Finding
improvements based on larger tensors has historically been very difficult
compared to finding improvements based on small tensors; for instance, it took
almost 10 years after Strassen’s algorithm based on a $2\times 2$ identity
before Pan [Pan78] gave an improved exponent based on a larger tensor.
Moreover, decades of work have gone into designing matrix multiplication
algorithms for larger $q$ which we need to catch up to for the light bulb
problem. Many of these techniques can be directly repurposed to the light bulb
problem (for instance, it is not hard to prove a version of the asymptotic sum
inequality [Sch81] in this setting), but the centerpiece of fast matrix
multiplication algorithms, the Coppersmith-Winograd tensor, seems particularly
designed for exact matrix multiplication, and it is not clear how to improve
it for our light bulb setting. (More generally, it is a major open challenge
to understand the effectiveness of the Coppersmith-Winograd tensor or find any
useful variants on it [HJMS22, BL16, CGLV19, CHL22].) Nonetheless, our
computations suggest that this trend continues: our approach gives better
bounds on $\frac{3}{2}\omega_{\ell}$ than prior approaches do for $\omega_{B}$
when restricted to certain small classes of tensors, such as tensors on the
variable set of $\langle 3,3,3\rangle$, or tensors on the variable set of
$\langle 2,2,2\rangle$ of rank at most $4$ (but none of these beats the bound
of $T_{2112}$). We are optimistic improvements are possible for larger $q$ as
well.

##### Exponent Comparison.

Combining our result with [KK19, Har21] shows that, when restricted to rank
bounds on small tensors over the same variable set as $\langle 2,2,2\rangle$,
the best known upper bounds have $\frac{3}{2}\omega_{\ell}<\omega_{B}<\omega.$
By comparison, the asymptotically best known upper bounds have
$\frac{3}{2}\omega_{\ell}=\omega_{B}=\omega.$ It would be exciting to
determine the relationship between these exponents in the asymptotic setting,
perhaps using fine-grained reduction techniques. Indeed, although we know
$\omega_{B}\leq\omega$, it’s not clear in general what the relationship
between $\omega_{\ell}$ and $\omega_{B}$ should be. Neither problem is known
to be reducible to the other. Moreover, even our ‘efficacy’ approach for the
light bulb problem is incomparable to the ‘support rank’ [CU13] and
‘probabilistic rank’ [KK19] approaches: our approach applies to a wider class
of tensors, but the bound in Theorem 1.1 becomes worse when $T$ has large or
negative coefficients, whereas ‘support rank’ and ‘probabilistic rank’ aren’t
impacted by what the coefficients are. Nonetheless, from the small tensor
regime, it appears plausible that $\omega_{\ell}<\omega_{B}$; it may be worth
investigating whether other problems which are known to be reducible to matrix
multiplication can actually be reduced to the light bulb problem instead!

Another advantage of our new algorithm is that it is not necessarily
restricted to give exponents which are $\geq 4/3$. Recall that using the known
bound $\omega_{\ell}\leq\frac{2}{3}\omega$, even if $\omega=2$, one could only
prove $\omega_{\ell}\leq 4/3$. Achieving an exponent less than $4/3$ requires
another approach, and our Theorem 1.1 appears promising since it doesn’t seem
to have any such restrictions.

##### Tensors with Undesirable Terms.

One motivation for this work is to use tensors with ‘undesirable’ terms which,
in other contexts, make them unusable. Typically one would expend rank to
remove those terms, but one could design faster algorithms by allowing them to
contribute to the efficacy of the tensor instead. We’ve already discussed the
case of tensors from border rank upper bounds via our example $T_{2112}$.
Tensors with undesirable terms also arise in the Laser method [Str87], the
tool used to design the best known upper bounds on $\omega$. A key step at the
end of the Laser method, which was improved but not entirely removed in recent
work of Alman and Vassilevska Williams [AW21], removes such undesirable terms.
Leaving them in to contribute to the efficacy could lead to asymptotically
faster algorithms.

##### Further Generalizations of the Light Bulb Problem.

In Section 4 below, we show that our algorithm can also solve a generalization
of the light bulb problem where each group of coordinates of the ‘correlated
pair’ are sampled from _any_ non-uniform joint distribution. Other
generalizations have also been previously considered [Val12, KKK18], including
a variant with many correlated pairs to find, and an ‘outlier correlation
detection’ variant where we are promised that the correlated pair has
correlation $\rho$, and all other pairs have correlation at most $\tau$, for
parameters $0<\tau<\rho<1$. Our approach can also solve these generalizations,
by using the same techniques from prior work (which essentially amplify the
differences in correlations by taking large Kronecker powers of the input
vectors), since we focus on finding the correlated vectors after this
amplification step. The details, which are essentially the same as in the past
work, are omitted here. As discussed earlier, the best known algorithms for
generalizations to other learning problems such as learning sparse parities or
Juntas with noise also come from reductions to the light bulb problem [Val12].

##### Other Closest Pair Problems.

The light bulb problem is an average case version of the bichromatic
$(1+\varepsilon)$-approximate closest pair problem, where one is given as
input two sets $X,Y$ of $n$ points from a metric space, and one wants to find
$x^{*}\in X$ and $y^{*}\in Y$ satisfying
$\mathrm{dist}(x^{*},y^{*})\leq(1+\varepsilon)\cdot\min_{x\in X,y\in
Y}\mathrm{dist}(x,y)$. Similar to the previous state of the art for the light
bulb problem, for many popular metric spaces, there are two known approaches
for solving this problem: one based on matrix multiplication which is faster
when $\varepsilon>0$ is small [AW15, ACW16, ACW20], and one based on locality-
sensitive hashing which is faster when $\varepsilon$ is larger [AR15, ALRW17];
see also [AIR18]. To our knowledge, our hashing-based algorithm is the first
to successfully combine matrix multiplication and hashing methods for any such
problem. It is not hard to see that more straightforward ways to combine the
two, such as hashing into smaller buckets and then using matrix multiplication
within each bucket, cannot be faster than just using one of the two techniques
on its own; we get around this by carefully choosing a hash function which
correlates well with our chosen tensor. It would be exciting to apply a
similar technique to other nearest neighbor search problems.

###  1.8 Algorithm Overview

Although Theorem 1.1 has a simple form (perhaps reminiscent of the bound
$\omega\leq\log(\mathop{\operatorname{rank}}(\langle q,q,q\rangle))/\log(q)$
which follows from the simple recursive argument), the algorithm itself
involves a number of subtle steps in the case when $T$ is not ‘symmetric
enough’, and the proof of correctness is ultimately quite involved. At a high
level, the elaborate probabilistic analyses which arise in prior works on the
light bulb problem [Val12, KKK18], wherein one needs to prove tail bounds on
sums of correlated events, return in full force when combined with errors
which arise from using the tensor $T$ instead of matrix multiplication. We end
up applying a simple variant on the Laser method to the tensor $T$ to
‘regularize’ it without changing $\mathop{\operatorname{eff}}(T)$ too much, to
help with the analysis.999Alman [Alm18] recently simplified some steps in
prior algorithms for the light bulb problem using the polynomial method, but
using our tensors in Alman’s approach doesn’t seem to work since Alman creates
matrices with large entries to multiply.

We focus here on describing the algorithm for Theorem 1.1 in the case when the
tensor $T$ is sufficiently ‘symmetric’ (as is the case for the three tensors
described in Figure 1). Afterwards we will briefly discuss how we deal with
asymmetric tensors, and how we extend our result using hashing to Theorems 1.3
and 1.4.

Algorithm 1 Light bulb algorithm for Theorem 1.1

1:procedure LightBulb($x_{1}\cdots x_{n},y_{1}\cdots
y_{n}\in\\{-1,1\\}^{d},T$)

2: $\triangleright$ $x_{1},\cdots,x_{n},y_{1},\cdots,y_{n}$ are input vectors;
$T$ is a tensor with $q_{i}=q_{j}=q_{k}=q$

3: Let $N$ be such that
$n^{\omega_{\ell}}=\mathop{\operatorname{rank}}(T)^{N}$. $\triangleright$
$\omega_{\ell}=\frac{\log(\mathop{\operatorname{rank}}(T))}{\log(\mathop{\operatorname{eff}}(T))}$

4: Calculate $\mathop{\operatorname{eff}}_{i,j}(T^{\otimes N})$ for all
$i,j\in[q]^{N}$. $\triangleright$ Can be done in negligible
$\tilde{O}(q^{2N})$ time

5: Let $g$ be such that
$g^{2}\cdot|\\{i,j\in[q]^{N}:\mathop{\operatorname{eff}}_{i,j}(T^{\otimes
N})\geq g^{2}\\}|$ is maximized, and set $t\leftarrow q^{N}g/n$.

6: $X_{1},\cdots,X_{q^{N}},Y_{1},\cdots,Y_{q^{N}}\leftarrow\emptyset$.

7: for $i\in[n]$ do

8: Uniformly independently at random pick $i_{1},\cdots,i_{t}$ and
$j_{1},\cdots,j_{t}$ from $[q^{N}]$.

9: Add $i$ to all the sets
$X_{i_{1}},\cdots,X_{i_{t}},Y_{j_{1}},\cdots,Y_{j_{t}}$.

10: end for

11: For all $i\in[q]^{N}$, let $a_{i}:=\sum_{j\in X_{i}}x_{j}$ and
$b_{i}:=\sum_{j\in Y_{i}}y_{j}$.

12: Let $A=[a_{1}^{\top},\cdots,a_{q^{N}}^{\top}]$ be $q^{N}\times d$ matrix
of all $a_{i}^{\top}$ vectors.

13: Let $B=[b_{1}^{\top},\cdots,b_{q^{N}}^{\top}]$ be the $q^{N}\times d$
matrix of all $b_{i}^{\top}$ vectors. $\triangleright$ Assume $d=q_{k}^{N}$.

14: Random multiply each row of $A$ and $B$ by $-1$ or $1$.

15: Recursively apply $T$ to ‘multiply’ $A$ and $B^{\top}$ and get their
‘product’ $C$. $\triangleright$ Take time
$\tilde{O}(\mathop{\operatorname{rank}}(T)^{N})$.

16: Do the multiplication $100\log n$ times to get $C_{1},\cdots,C_{100\log
n}$. $\triangleright$ Each time redo from beginning using fresh inputs.

17: Find $(i,j)$ such that, there are at least $20\log n$ different
$k\in[100\log n]$ that, $C_{k}[i,j]\geq
10\mathop{\operatorname{eff}}^{2}_{i,j}(T^{\otimes N})\geq 10g^{2}$.

18:end procedure

The main algorithm is given in Algorithm 1. There are two key results we need
to prove its correctness. First, because of how
$\mathop{\operatorname{eff}}_{i,j}$ is defined, if
$|X_{i}|\cdot|Y_{j}|\leq\mathop{\operatorname{eff}}_{i,j}^{2}(T^{\otimes N})$
but $C[i,j]\geq\mathop{\operatorname{eff}}^{2}_{i,j}(T^{\otimes N})$, this
means the correlated pair is likely to be in $X_{i}$ and $Y_{j}$. Roughly, we
prove the fact that $\mathop{\operatorname{eff}}_{i,j}(T^{\otimes N})$ is so
large _means that_ random noise cannot explain $C_{k}[i,j]$ being so large for
too many $k$. Second, there is a decent probability that the bucketing used by
the algorithm will result in copies of the correlated pair being put into
$X_{i}$ and $Y_{j}$ for which $\mathop{\operatorname{eff}}_{i,j}(T^{\otimes
N})$ is large enough.

This second result requires some work since whether or not the planted pair
has been put into the pair of groups $(X_{i},Y_{j})$ is _not_ independent of
whether it has been put into other pairs of groups. Moreover, it becomes more
complicated in the case when the set
$\\{(i,j)\in[q]^{N}:\mathop{\operatorname{eff}}_{i,j}\geq g^{2}\\}$ is
‘skewed’ and mostly consists of pairs in a small number of rows or columns. In
this case, we modify our algorithm by alternatingly applying either $T$ or its
(appropriately defined) transpose. After this transformation, the large
efficacies are ‘balanced enough’ that a second moment method can be used to
imply our second property.

Finally, as discussed in Section 1.6 above, the idea behind Theorems 1.3 and
1.4 is to modify Line 8 of the algorithm to sample the indices
$i_{1},\ldots,i_{t}$ according to a locality-sensitive hash function. This
further complicates the analysis: not only are the pairs $(X_{i},Y_{j})$ which
the planted pair has been put into not independent of each other, but even the
buckets $X_{i_{1}},\ldots,X_{i_{t}}$ which a single one of the planted vectors
has been put into are not independent. We address this by independently
perturbing $t$ copies of each input vector before applying a locality-
sensitive hash function to them so that the different buckets are
‘sufficiently independent’. The key behind applying our approach to tensors
$T$ other than $T_{2112}$ in Theorem 1.4 is to do this perturbation in a
biased way which correlates with the efficacy matrix of $T$. Fortunately,
although the analysis requires these probabilistic analyses and explicitly
analyzing the Kronecker power $T^{\otimes N}$, the algorithm itself is simple
and only applies $T$ in the usual recursive way to pairs of matrices.

###  1.9 Outline

The remainder of our paper is organized as follows. After the preliminaries in
Section 2, we prove Theorem 1.1 in Section 3, then we prove Theorem 1.3 in
Section 4. In Section 5 we define and give the rank expressions for the
tensors in Figure 1, including introducing our new tensor $T_{2112}$. In
Section 6 we prove Theorem 1.4 that hashing can be used to improve the
algorithm from most tensors. Finally, in Appendix A we discuss techniques from
prior work for vector aggregation.

##  2 Preliminaries

##### Notation

For positive integer $q$, write $[q]:=\\{1,2,3,\ldots,q\\}$.

For an event $F$, write $[F]_{\mathbf{1}}$ to be $1$ if $F$ happens, and $0$
if $F$ does not happen.

For vectors $v\in\mathbb{R}^{d}$, and $\ell\in[d]$, we write $v[\ell]$ to
denote entry $\ell$ of $v$. Similarly, for matrices
$M\in\mathbb{R}^{d_{1}\times d_{2}}$, and
$\ell_{1}\in[d_{1}],\ell_{2}\in[d_{2}]$, we write $M[\ell_{1},\ell_{2}]$ to
denote the corresponding entry of $M$.

##### Multinomial Coefficients

If $a_{1},a_{2},\ldots,a_{k}\in[0,1]$ and $N\in\mathbb{N}$ are such that
$\sum_{i=1}^{k}a_{i}=1$, and $a_{i}\cdot N$ is an integer for all $i$, then we
write the multinomial coefficient:

$\binom{N}{\\{a_{i}\cdot
N\\}_{i\in[k]}}:=\prod_{i=1}^{k}\binom{N\cdot(1-\sum_{j=1}^{i-1}a_{j})}{a_{i}\cdot
N}.$

Standard bounds show that as $N\to\infty$, we have

$\binom{N}{\\{a_{i}\cdot
N\\}_{i\in[k]}}=\left(\prod_{i=1}^{k}a_{i}^{-a_{i}}\right)^{N-o(N)}.$

##### Chebyshev’s inequality

Chebyshev’s inequality says that if $U\in\mathbb{R}$ is a random variable with
finite mean and finite non-zero variance, then for any real $k>0$ we have

$\Pr\left[|U-\mathbb{E}[U]|\geq
k\cdot\sqrt{\mathop{\operatorname{var}}[U]}\right]\leq\frac{1}{k^{2}}.$

##### Second Moment Method

The second moment method says that if $U\in\mathbb{R}$ is a random variable
such that $U$ is always nonnegative, and $\mathop{\operatorname{var}}[U]$ is
finite, then

$Pr[U>0]\geq\frac{(\mathbb{E}[U])^{2}}{\mathbb{E}[U^{2}]}.$

##### Tensors

For positive integer $q,q_{k}$, let
$\mathsf{X}=\\{\mathsf{X}_{i,k}\\}_{i\in[q],k\in[q_{k}]}$ ,
$\mathsf{Y}=\\{\mathsf{Y}_{j,k}\\}_{j\in[q],k\in[q_{k}]}$, and
$\mathsf{Z}=\\{\mathsf{Z}_{i,j}\\}_{i,j\in[q]}$. Most of the tensors in this
paper will be over these sets, and we call a tensor over these sets a $\langle
q,q,q_{k}\rangle$-sized tensor.

A tensor $T$ over $\mathsf{X},\mathsf{Y},\mathsf{Z}$ is a trilinear form in
$\mathbb{R}^{|\mathsf{X}|\times|\mathsf{Y}|\times|\mathsf{Z}|}$. For
$i,i^{\prime},j,j^{\prime}\in[q]$ and $k,k^{\prime}\in[q_{k}]$ we write
$T(\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}})$
for the coefficient of the term
$\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}}$
in $T$. In other words, we can write:

$T=\sum_{i,i^{\prime},j,j^{\prime}\in[q],k,k^{\prime}\in[q_{k}]}T(\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}})\cdot\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}}.$

We say $\mathsf{X}$ are the $x$-variables of $T$, $\mathsf{Y}$ are the
$y$-variables of $T$, and $\mathsf{Z}$ are the $z$-variables of $T$.

The matrix multiplication tensor $\langle q,q,q_{k}\rangle$ is a tensor over
$\mathsf{X},\mathsf{Y},\mathsf{Z}$ given by

$\langle
q,q,q_{k}\rangle:=\sum_{i,j\in[q],k\in[q_{k}]}\mathsf{X}_{i,k}\mathsf{Y}_{j,k}\mathsf{Z}_{i,j}.$

##### Tensor Rank

A tensor $T$ over $\mathsf{X},\mathsf{Y},\mathsf{Z}$ has rank $1$ if it can be
written in the form

$T=\left(\sum_{i\in[q],k\in[q_{k}]}a_{i,k}\mathsf{X}_{i,k}\right)\left(\sum_{j\in[q],k\in[q_{k}]}b_{j,k}\mathsf{Y}_{j,k}\right)\left(\sum_{i,j\in[q]}c_{i,j}\mathsf{Z}_{i,j}\right)$

for coefficients $a_{i,k},b_{j,k},c_{i,j}\in\mathbb{R}$. More generally,
$\mathop{\operatorname{rank}}(T)$ is the minimum number of rank $1$ tensors
whose sum is $T$.

##### Kronecker Product

If
$\mathsf{X},\mathsf{Y},\mathsf{Z},\mathsf{X}^{\prime},\mathsf{Y}^{\prime},\mathsf{Z}^{\prime}$
are sets of variables, $T$ is a tensor over
$\mathsf{X},\mathsf{Y},\mathsf{Z}$, and $T^{\prime}$ is a tensor over
$\mathsf{X}^{\prime},\mathsf{Y}^{\prime},\mathsf{Z}^{\prime}$, then the
Kronecker product $T\otimes T^{\prime}$ is a tensor over
$\mathsf{X}\times\mathsf{X}^{\prime},\mathsf{Y}\times\mathsf{Y}^{\prime},\mathsf{Z}\times\mathsf{Z}^{\prime}$
given by, for
$x\in\mathsf{X},x^{\prime}\in\mathsf{X}^{\prime},y\in\mathsf{Y},y^{\prime}\in\mathsf{Y}^{\prime},z\in\mathsf{Z},z^{\prime}\in\mathsf{Z}^{\prime}$,

$T\otimes T^{\prime}((x,x^{\prime})(y,y^{\prime})(z,z^{\prime}))=T(xyz)\cdot
T^{\prime}(x^{\prime}y^{\prime}z^{\prime}).$

Notice in particular that for positive integers
$q,q^{\prime},q_{k},q_{k}^{\prime}$ we have $\langle
q,q,q_{k}\rangle\otimes\langle
q^{\prime},q^{\prime},q_{k}^{\prime}\rangle=\langle
qq^{\prime},qq^{\prime},q_{k}q_{k}^{\prime}\rangle$. (Here, we say two tensors
are equal if they are the same up to renaming variables.) We can view $\langle
qq^{\prime},qq^{\prime},q_{k}q_{k}^{\prime}\rangle$ as a tensor whose
$\mathsf{X}$-variables are either $\\{\mathsf{X}_{i,k}\\}_{i\in[q\cdot
q^{\prime}],k\in[q_{k}\cdot q_{k}^{\prime}]}$ or
$\\{\mathsf{X}_{(i,i^{\prime}),(k,k^{\prime})}\\}_{i\in[q],i^{\prime}\in[q^{\prime}],k\in[q_{k}],k^{\prime}\in[q_{k}^{\prime}]}$.
These are the same up to a natural bijection, and we will use both notations
interchangeably.

For a tensor $T$ over $\mathsf{X},\mathsf{Y},\mathsf{Z}$ and positive integer
$k$, we define the Kronecker power $T^{\otimes k}$ to be the Kronecker product
of $k$ copies of $T$. It is a tensor over
$\mathsf{X}^{k},\mathsf{Y}^{k},\mathsf{Z}^{k}$, and its coefficients are all
the products of $k$ coefficients of $T$.

##### Applying a Tensor to Matrices

If $T$ is a tensor over $\mathsf{X},\mathsf{Y},\mathsf{Z}$, and
$A,B\in\mathbb{R}^{q\times q_{k}}$ are matrices, then the result of applying
$T$ to $A$ and $B$ is a matrix $C\in\mathbb{R}^{q\times q}$ given by

$C[i,j]=\sum_{i^{\prime},j^{\prime}\in[q],k,k^{\prime}\in[q_{k}]}T(\mathsf{X}_{i^{\prime},k}\mathsf{Y}_{j^{\prime},k^{\prime}}\mathsf{Z}_{i,j})\cdot
A[i^{\prime},k]\cdot B[j^{\prime},k^{\prime}].$

The usual recursive algorithm (similar to Strassen’s algorithm) shows that,
for positive integers $N$, the tensor $T^{\otimes N}$ can be applied using
only $\tilde{O}(\mathop{\operatorname{rank}}(T)^{N})$ field operations, or the
improved bound $O(\mathop{\operatorname{rank}}(T)^{N})$ when
$\mathop{\operatorname{rank}}(T)>q^{2}$.

##### Tensor Reflection

For a tensor $T$ over $\mathsf{X},\mathsf{Y},\mathsf{Z}$, its reflection
$T^{\top}$ is another tensor over $\mathsf{X},\mathsf{Y},\mathsf{Z}$ given by,
for $i,i^{\prime},j,j^{\prime}\in[q]$ and $k,k^{\prime}\in[q_{k}]$,

$T^{\top}(\mathsf{X}_{i,k}\mathsf{Y}_{j,k^{\prime}}\mathsf{Z}_{i^{\prime},j^{\prime}})=T(\mathsf{X}_{j,k^{\prime}}\mathsf{Y}_{i,k}\mathsf{Z}_{i^{\prime},j^{\prime}}).$

This swaps the roles of the $\mathsf{X}$ and $\mathsf{Y}$ variables.

##### Kronecker Products of Matrices and Vectors

If $A\in\mathbb{R}^{n_{a}\times m_{a}}$ and $B\in\mathbb{R}^{n_{b}\times
m_{b}}$ are matrices, one can analogously define their Kronecker product
$A\otimes B\in\mathbb{R}^{n_{a}n_{b}\times m_{a}m_{b}}$ by, for
$i\in[n_{a}],i^{\prime}\in[n_{b}],j\in[m_{a}],j^{\prime}\in[m_{b}]$, $A\otimes
B[(i,i^{\prime}),(j,j^{\prime})]=A[i,j]\cdot B[i^{\prime},j^{\prime}]$.
Similarly, for vectors $u\in\mathbb{R}^{n_{a}},v\in\mathbb{R}^{n_{b}}$, one
can define $u\otimes v\in\mathbb{R}^{n_{a}n_{b}}$ by $u\otimes
v[(i,i^{\prime})]=u[i]\cdot v[i^{\prime}]$.

Suppose $P$ is a property of vectors which is preserved under Kronecker
product, i.e., if $u,v$ have the property, then so does $u\otimes v$. One
example is the property of whether $\|v\|_{2}\geq 1$. For a tensor $T$ over
$\mathsf{X},\mathsf{Y},\mathsf{Z}$, let $S_{P}(T)\in\mathbb{R}^{q\times q}$
denote the matrix such that $S_{P}(T)[i,j]=1$ if the vector
$(T(\mathsf{X}_{i^{\prime},k}\mathsf{Y}_{j^{\prime},k^{\prime}}\mathsf{Z}_{i,j}))_{i^{\prime},j^{\prime}\in[q],k,k^{\prime}\in[q_{k}]}$
has property $P$, and $S_{P}(T)[i,j]=0$ otherwise. Then, we can see that
$S_{P}(T^{\otimes N})=S_{P}(T)^{\otimes N}$. This will be particularly helpful
to us in the case when $P$ is the property that
$\mathop{\operatorname{eff}}_{i,j}(T)\geq f$ for some threshold $f$. (See
Definition 3.1 below for the the definition of $\mathop{\operatorname{eff}}$.)

##  3 Algorithm for the light bulb problem

######  Definition 3.1 (Efficacy).

Given any $\langle q,q,q_{k}\rangle$-sized tensor $T$, for $i,j\in[q]$, we
define the _$(i,j)$ -efficacy of $T$_ as:

$\mathop{\operatorname{eff}}_{i,j}(T):=\frac{\sum_{k\in[q_{k}]}T(\mathsf{X}_{i,k}\mathsf{Y}_{j,k}\mathsf{Z}_{i,j})}{\sqrt{\sum_{i^{\prime},j^{\prime}\in[q],k,k^{\prime}\in[q_{k}]}T(\mathsf{X}_{i^{\prime},k}\mathsf{Y}_{j^{\prime},k^{\prime}}\mathsf{Z}_{i,j})^{2}}}.$

We further define the _efficacy of $T$_ as:

$\mathop{\operatorname{eff}}(T):=\sqrt{\sum_{i\in[q]}\sum_{j\in[q]}\left(\mathop{\operatorname{eff}}_{i,j}(T)\right)^{2}}.$

Note that if $T,T^{\prime}$ are two tensors, for
$(i,i^{\prime}),(j,j^{\prime})\in[q]^{2}$, we have
$\mathop{\operatorname{eff}}_{(i,i^{\prime}),(j,j^{\prime})}(T\otimes
T^{\prime})=\mathop{\operatorname{eff}}_{i,j}(T)\cdot\mathop{\operatorname{eff}}_{i^{\prime},j^{\prime}}(T^{\prime}).$

We now begin giving our algorithm for the light bulb problem. Our goal is to
analyze Algorithm 1 in order to prove Theorem 1.1. In particular, we assume
throughout this section that $T$ is such that the aggregation step (lines 11,
12, , 13) take negligible time compared to the rest of the algorithm; in
Appendix A below, we show how to modify $T$, if necessary, so that this is the
case.

######  Theorem 3.2.

Suppose $T$ is a $\langle q,q,q_{k}\rangle$-sized tensor. For any $f\geq 1$,
and any set $S_{f}\subseteq[q]^{2}$ such that
$\mathop{\operatorname{eff}}_{i,j}(T)\geq f$ for all $(i,j)\in S_{f}$, we have
$\omega_{\ell}\leq\log(\mathop{\operatorname{rank}}(T)\cdot
q^{2}/|S_{f}|)/\log(f\cdot q)$.

###### Proof.

Suppose we are given as input $x_{1},\ldots,x_{n},$
$y_{1},\ldots,y_{n}\in\\{-1,1\\}^{d}$ which are all generated independently
and uniformly at random except for an unknown $(i^{*},j^{*})\in[n]^{2}$ with
$\langle x_{i^{*}},y_{j^{*}}\rangle\geq\rho\cdot d$. Permute the inputs at
random so that $(i^{*},j^{*})$ is a uniformly random pair in $[n]^{2}$.

We can solve the light bulb problem using $O(\log n)$ calls of its decision
version – we randomly take half $x$ and half $y$, and for the decision
problem, we need to distinguish between two cases 1). all inputs are uniformly
at random in $\\{-1,1\\}^{d}$, and 2). there exists one correlated
$(i^{*},j^{*})$ pair. From now on, we will only consider the decision version.

Let $m=(\frac{20n}{\rho})^{\frac{1}{1+\log_{q}(f)}}$ and let $g=n/m$.
Partition $x_{1},\ldots,x_{n}$ into $m$ groups $X_{1},\ldots,X_{m}$ of size
$g$ each, and partition $y_{1},\ldots,y_{n}$ into $m$ groups
$Y_{1},\ldots,Y_{m}$ of size $g$ each. For each $i\in[m]$, create vectors
$a_{i},b_{i}\in\mathbb{R}^{d}$ given by $a_{i}=\sum_{u\in X_{i}}u$ and
$b_{i}=\sum_{v\in Y_{i}}v$. (These vectors aggregate all the data points which
were put into the same group; we will see soon that if groups $i$ and $j$
contain the correlated pair, then $a_{i}$ and $b_{j}$ are still somewhat
correlated.) Let $s_{a},s_{b}\in\\{-1,1\\}^{m}$ be two vectors whose entries
are independently uniformly sampled from $\\{-1,1\\}$. Finally, we form the
matrices $A,B\in\mathbb{R}^{m\times d}$ whose rows are $s_{a}[1]\cdot
a_{1},\ldots,s_{a}[m]\cdot a_{m}$ and $s_{b}[1]\cdot
b_{1},\ldots,s_{b}[m]\cdot b_{m}$, respectively.

For simplicity, let us assume that $d=m^{\log(q_{k})/\log(q)}$ so that
$T^{\otimes c}$ is a $\langle m,m,d\rangle$-sized tensor that can be used on
$A$ and $B$, where $c=\log(m)/\log(q)$. As discussed in the introduction, if
one would like to remove this requirement, then using the ‘compressed
matrices’ method introduced in [KKK18, Section 4.2], one can ‘expand’ lower-
dimensional vectors, and hence relax this assumption to only require
$d\geq\Omega(\log n)$ while only decreasing $\rho$ by a negligible
factor101010In fact, the result of the compressed matrices method gives that
if $x_{i},y_{j}$ are not the correlated pair, the the entries of the entry-
wise product $x_{i}\circ y_{j}$ are only pairwise-independent of each other,
and not fully independent. (This is because they are products of different
entries of the original vectors.) As we will see below, this pairwise-
independence suffices for our algorithm. The compressed matrices technique
particularly speeds up the time to compute the aggregated vectors
$a_{i},b_{j}$ so that it is negligible compared to the remaining running time
of the algorithm, and one can confirm that it remains negligible here. We
refer the reader to [KKK18, Section 4.4] for more details.; see Appendix A
below for more details.

We now apply the usual recursive algorithm using the tensor $T$ to the
matrices $A$ and $B^{T}$, resulting in the matrix $C\in\mathbb{R}^{m\times
m}$. The running time is
$\tilde{O}(m^{\log(\mathop{\operatorname{rank}}(T))/\log(q)})=\tilde{O}(n^{\log(\mathop{\operatorname{rank}}(T))/\log(qf)})$.
The output $C$ is the result of applying the tensor $T^{\otimes c}$ to the
matrices $X=A$ and $Y=B^{T}$, so that each entry $C[i,j]$ is the sum:

$\displaystyle
C[i,j]=\sum_{i_{a},j_{b}\in[q^{c}],k_{a},k_{b}\in[q_{k}^{c}]}T^{\otimes
c}(X_{i_{a},k_{a}}Y_{j_{b},k_{b}}Z_{i,j})\cdot A[i_{a},k_{a}]\cdot
B[j_{b},k_{b}].$ (1)

Consider the product of two terms $A[i,k_{a}]\cdot B[j,k_{b}]$. These are
distributed as follows:

  * •

If there’s a planted pair $(x_{i^{*}},y_{j^{*}})$ and $k_{a}=k_{b}$,
$x_{i^{*}}\in X_{i}$, and $y_{j^{*}}\in Y_{j}$, then this is the sum of
$g^{2}$ random $\\{-1,1\\}$ variables which are pairwise-independent from each
other. They all have mean $0$ except one of them has mean $\rho$, so the
entire variable $A[i,k_{a}]\cdot B[j,k_{b}]$ has mean $\rho$ and variance
$g^{2}$.

  * •

Otherwise, it is the sum of $g^{2}$ uniformly random pairwise-independent
$\\{-1,1\\}$ variables, which has mean $0$ and variance $g^{2}$.

Let’s compute the variance of $C[i,j]$. We showed earlier that each term
$A[i_{a},k_{a}]\cdot B[j_{b},k_{b}]$ has variance $g^{2}$, so $T^{\otimes
c}(X_{i_{a},k_{a}}Y_{j_{b},k_{b}}Z_{i,j})\cdot A[i_{a},k_{a}]\cdot
B[j_{b},k_{b}]$ has variance $T^{\otimes
c}(X_{i_{a},k_{a}}Y_{j_{b},k_{b}}Z_{i,j})^{2}\cdot g^{2}$. Since we use
$s_{a},s_{b}$ entry-wise independently sampled from $\\{-1,1\\}$, the terms in
the sum (1) are pairwise-independent of each other. It follows that regardless
of whether there’s a planted pair, every $C[i,j]$ has variance:

$\mathop{\operatorname{var}}[C[i,j]]=g^{2}\cdot\sum_{i_{a},j_{b}\in[q^{c}],k_{a},k_{b}\in[q_{k}^{c}]}T^{\otimes
c}(X_{i_{a},k_{a}}Y_{j_{b},k_{b}}Z_{i,j})^{2}.$

Next let’s compute the mean of $C[i,j]$. If there’s no planted pair, every
$C[i,j]$ has mean $0$. If the planted pair $(x_{i^{*}},y_{j^{*}})$ exists,
let’s assume $x_{i^{*}}\in X_{i}$ and $y_{j^{*}}\in Y_{j}$ and only consider
the mean of $C[i,j]$. Recall that $A[i_{a},k_{a}]\cdot B[j_{b},k_{b}]$ has
mean nonzero only if $k_{a}=k_{b}$, $i_{a}=i$ and $j_{b}=j$. It follows by
linearity of expectation that

$\displaystyle\mathbb{E}[C[i,j]]=$
$\displaystyle~{}\sum_{k\in[q_{k}^{c}]}T^{\otimes
c}(X_{i,k}Y_{j,k}Z_{i,j})\cdot\mathbb{E}[A[i,k]\cdot B[j,k]]$ $\displaystyle=$
$\displaystyle~{}\rho\cdot s_{a}[i]\cdot
s_{b}[j]\cdot\sum_{k\in[q_{k}^{c}]}T^{\otimes c}(X_{i,k}Y_{j,k}Z_{i,j}).$

To summarize: when there’s no planted pair, every $C[i,j]$ has mean $0$ and
variance

$g^{2}\cdot\sum_{i_{a},j_{b}\in[q^{c}],k_{a},k_{b}\in[q_{k}^{c}]}T^{\otimes
c}(X_{i_{a},k_{a}}Y_{j_{b},k_{b}}Z_{i,j})^{2}.$

When the planted pair exists, and $x_{i^{*}}$ is in $X_{i}$, $y_{j^{*}}$ is in
$Y_{j}$, and the entry $(i,j)$ is ‘good’ (We say $(i,j)$ is ‘good’ if
$\mathop{\operatorname{eff}}_{i,j}(T^{\otimes c})\geq f^{c}$), the ratio of
its mean and standard deviation is at least:

$\displaystyle~{}\left|\frac{\rho\cdot s_{a}[i]\cdot
s_{b}[j]\cdot\sum_{k\in[q_{k}^{c}]}T^{\otimes
c}(X_{i,k}Y_{j,k}Z_{i,j})}{g^{2}\cdot\sum_{i_{a},j_{b}\in[q^{c}],k_{a},k_{b}\in[q_{k}^{c}]}T^{\otimes
c}(X_{i_{a},k_{a}}Y_{j_{b},k_{b}}Z_{i,j})^{2}}\right|$ $\displaystyle=$
$\displaystyle~{}\frac{\rho}{g}\cdot\mathop{\operatorname{eff}}_{i,j}(T^{\otimes
c})$ $\displaystyle\geq$ $\displaystyle~{}\frac{\rho}{g}\cdot f^{c}$
$\displaystyle=$ $\displaystyle~{}\frac{\rho\cdot m}{n}\cdot f^{c}$
$\displaystyle\geq$ $\displaystyle~{}\frac{\rho\cdot m}{n}\cdot
f^{\log(m)/\log(k)}$ $\displaystyle=$ $\displaystyle~{}\frac{\rho}{n}\cdot
m^{1+\log(f)/\log(k)}$ $\displaystyle=$
$\displaystyle~{}\frac{\rho}{n}\cdot\frac{20\cdot n}{\rho}$ $\displaystyle=$
$\displaystyle~{}20.$

Therefore, follows by Chebyshev’s inequality, when there’s no planted pair,
$C[i,j]\leq 10\mathop{\operatorname{var}}[C[i,j]]$ with probability $\geq
0.99$ for all $(i,j)\in[m]^{2}$, and when there exists a planted pair in a
‘good’ entry $(i^{*},j^{*})$, then $C[i^{*},j^{*}]\geq
10\mathop{\operatorname{var}}[C[i^{*},j^{*}]]$ with probability $\geq 0.99$.
Thus, we can independently repeating $O(\log n)$ times to distinguish the two
cases with polynomially-low error.

Let $|S_{f}|=q^{\alpha}$. Since
$\mathop{\operatorname{eff}}_{(i,i^{\prime}),(j,j^{\prime})}(T\otimes
T^{\prime})=\mathop{\operatorname{eff}}_{i,j}(T)\cdot\mathop{\operatorname{eff}}_{i^{\prime},j^{\prime}}(T^{\prime})$,
there are at least $|S_{f}|^{c}$ pairs of $(i,j)\in[m]^{2}$ that
$\mathop{\operatorname{eff}}_{i,j}(T^{\otimes c})\geq f^{c}$. So the planted
pair has $|S_{f}|^{c}/q^{2c}=q^{-(2-\alpha)c}$ probability going to a ‘good’
entry. We repeat $q^{(2-\alpha)c}\log n$ times to make sure the planted pair
goes to a ‘good’ entry at least once with high probability, therefore we can
distinguish the planted-pair case and the non planted-pair case.

Running time: Each run cost
$\tilde{O}(n^{\log(\mathop{\operatorname{rank}}(T))/\log(qf)})$ time. We
repeat the whole procedure $O(n^{(2-\alpha)\log(q)/\log(qf)}\cdot\log^{2}n)$
times to succeed with high probability.

The total running time is
$\tilde{O}(n^{\log(\mathop{\operatorname{rank}}(T))/\log(qf)}\cdot
n^{(2-\alpha)\log(q)/\log(qf)})=\tilde{O}(n^{\log(\mathop{\operatorname{rank}}(T)q^{2-\alpha})/\log(qf)})=\tilde{O}(n^{\log(\mathop{\operatorname{rank}}(T)q^{2}/|S_{f}|)/\log(qf)})$,
as desired. ∎

###  3.1 Improvement when $S_{f}$ is not ‘skewed’

We next show that in the special case when $S_{f}$ is not too ‘skewed’, we can
improve the bound of Theorem 3.2.

Recall that for $f\geq 1$, we chose a subset $S_{f}\subseteq[q]^{2}$
consisting of pairs $(i,j)\in[q]^{2}$ for which
$\mathop{\operatorname{eff}}_{i,j}(T)\geq f$. Let’s define the following
measurement of how a set $S_{f}$ is closed to ’skewed’.

######  Definition 3.3 ($V_{x}(S)$ and $V_{y}(S)$).

For any set $S\subseteq[q]^{2}$, let’s define
$V_{x}(S):=\sum_{i\in[q]}|\\{j\in[q]\mid(i,j)\in S\\}|^{2}$, and similarly
define $V_{y}(S):=\sum_{j\in[q]}|\\{i\in[q]\mid(i,j)\in S\\}|^{2}$.

######  Theorem 3.4.

Suppose $T$ is a $\langle q,q,q_{k}\rangle$-sized tensor. For any $f\geq 1$,
and any set $S_{f}\subseteq[q]^{2}$ such that
$\mathop{\operatorname{eff}}_{i,j}(T)\geq f$ for all $(i,j)\in S_{f}$, if
$V_{x}(S_{f}),V_{y}(S_{f})\leq|S_{f}|^{1.5}$, then,
$\omega_{\ell}\leq\log(\mathop{\operatorname{rank}}(T))/\log(f\cdot\sqrt{|S_{f}|})$.

###### Proof.

Let $E_{1}=\log(\mathop{\operatorname{rank}}(T))/\log(qf)$ and
$E_{2}=\log(q^{2}/|S_{f}|)/\log(qf)$.

Recall that in Theorem 3.2, we randomly partitioned the inputs
$x_{1},\ldots,x_{n}$ into sets $X_{1},\ldots,X_{m}$, and the inputs
$y_{1},\ldots,y_{n}$ into sets $Y_{1},\ldots,Y_{m}$, then we ran an algorithm
which takes time $\tilde{O}(n^{E_{1}})$, and which will (with high
probability) distinguish the all-random case and the planted-pair case, if
$x_{i^{*}}$ was put into set $X_{i}$ and $y_{j^{*}}$ was put into set $Y_{j}$
such that $(i,j)\in S_{f}^{\otimes c}$. Call such $(i,j)$ ‘good’. The
probability $(i,j)$ is good is $(|S_{f}|^{c}/q^{2c})=n^{-E_{2}}$.

In Theorem 3.2, we then repeated $\tilde{O}(n^{E_{2}})$ times, resulting in a
final running time of $\tilde{O}(n^{E_{1}+E_{2}})$, but we will now instead do
something more clever.

Let $t=n^{E_{2}/(2-E_{2})}$. We will make $t$ copies of each $x_{i}$ and
$y_{j}$ vector, and then run the above algorithm on this new instance with
$n\cdot t$ vectors, with the caveat that we never put two copies of the same
$x$ vector in the same group $X_{i}$, or two copies of the same $y$ vector in
the same group $Y_{j}$. The running time of this is
$\tilde{O}((nt)^{E_{1}})=\tilde{O}(n^{2\cdot E_{1}/(2-E_{2})})$, and the
probability that a particular correlated pair will be put in a good pair of
groups is now $(nt)^{-E_{2}}$. Since we made $t$ copies of $x_{i^{*}}$ and $t$
copies of $y_{j^{*}}$, there are now $t^{2}$ correlated pairs, so the expected
number of correlated pairs in a good pair of groups is

$t^{2}\cdot(nt)^{-E_{2}}=t^{2-E_{2}}\cdot
n^{-E_{2}}=n^{\frac{E_{2}}{2-E_{2}}\cdot(2-E_{2})-E_{2}}=n^{E_{2}-E_{2}}=1.$

With more work, and using our bounds on $V_{x}(S_{f})$ and $V_{y}(S_{f})$, we
can show that there is a positive constant probability that a correlated pair
was put in a good pair of groups. See Lemma 3.7 below for the details. Hence,
if we repeat $O(\log n)$ times, a correlated pair will be put in a good pair
of groups with polynomially low error.

The proof that our algorithm can distinguish the planted-pair case with the
non planted-pair case is almost identical to the proof in Theorem 3.2, except
the following. In the old proof, when the planted pair is in $X_{i}$ and
$Y_{j}$ and $\mathop{\operatorname{eff}}_{i,j}(T^{\otimes c})\geq f^{c}$,
there’s $\geq 0.99$ probability that $C[i,j]\geq
10\mathop{\operatorname{var}}[C[i,j]]$. Now, we can only prove the probability
is $\geq 0.24$ because duplicated vectors created correlation. Nonetheless, we
can distinguish from the non-planted-pair case, in which every $C[i,j]\geq
10\mathop{\operatorname{var}}[C[i,j]]$ with probability $\leq 0.01$. We show
probability $\geq 0.24$ as follows.

Let

$P[i_{a},j_{b}]:=\sum_{k_{a},k_{b}\in[d]}T^{\otimes
c}(X_{i_{a},k_{a}}Y_{j_{b},k_{b}}Z_{i,j})\cdot a_{i_{a},k_{a}}\cdot
b_{j_{b},k_{b}},$

so that $C[i,j]$ can be written as

$\displaystyle C[i,j]=\sum_{i_{a},j_{b}\in[m]}P[i_{a},j_{b}]\cdot
s_{a}[i_{a}]\cdot s_{b}[j_{b}],$ (2)

where $s_{a},s_{b}\in\\{-1,1\\}^{m}$ has i.i.d. $\\{-1,1\\}$ entries.

Use Lemma 3.5 on $C[i,j]$, we conclude that with $\geq 1/4$ probability over
random choice of $s_{a}$, $s_{b}$, $|C[i,j]|\geq|P[i,j]|$.

$\mathbb{E}[P[i,j]]=\rho\cdot\sum_{k\in[q_{k}^{c}]}T^{\otimes
c}(X_{i,k}Y_{j,k}Z_{i,j})$ and
$\mathop{\operatorname{var}}[P[i,j]]\leq\mathop{\operatorname{var}}[C[i,j]]$.
By the same analysis in Theorem 3.2, with $\geq 1/4-0.01$ probability,
$|C[i,j]|\geq|\mathbb{E}[P[i,j]]|-10\mathop{\operatorname{var}}[P[i,j]]\geq
10\mathop{\operatorname{var}}[C[i,j]]$.

The resulting exponent is hence:

$2\cdot E_{1}/(2-E_{2})=2\cdot
E_{1}/(\log(f^{2}\cdot|S_{f}|)/\log(qf))=\log(\mathop{\operatorname{rank}}(T))/\log(f\cdot\sqrt{|S_{f}|}).$

∎

######  Lemma 3.5.

Let $P\in\mathbb{R}^{n\times n}$ be a matrix. Let $a,b\in\\{-1,1\\}^{n}$ be
entry-wise i.i.d. uniformly sampled from $\\{-1,1\\}$. Then with probability
$\geq 1/4$,

$\displaystyle\left|\sum_{i,j\in[n]}a[i]\cdot b[j]\cdot
P[i,j]\right|\geq\left|P[1,1]\right|.$ (3)

###### Proof.

Define $\overline{T}=\sum_{j\geq 2}P[1,j]\cdot b[j]$, and
$T=\overline{T}+P[1,1]\cdot b[1]$. Regardless of how large $\overline{T}$ is,
with $\geq 1/2$ probability over $b[1]$, $|T|\geq|P[1,1]|$.

Let $S$ be the left side of Eq. (3). Notice that

$S=\left|\sum_{i\geq 2}a[i](\sum_{j\in[n]}P[i,j]\cdot b[j])+T\cdot
a[1]\right|,$

use the same argument, we have $|S|\geq|T|\geq|P[1,1]|$ with $\geq 1/4$
probability. ∎

###  3.2 Probabilistic lemma for when $S_{f}$ is not ‘skewed’

######  Lemma 3.6.

Suppose $q$ is a positive integer and $S\subseteq[q]^{2}$ is a nonempty
subset. Let $V_{x}(S):=\sum_{i\in[q]}|\\{j\in[q]\mid(i,j)\in S\\}|^{2}$ and
$V_{y}(S):=\sum_{j\in[q]}|\\{i\in[q]\mid(i,j)\in S\\}|^{2}$, and suppose that
$V_{x}(S)\leq|S|^{1.5}$ and $V_{y}(S)\leq|S|^{1.5}$.

Suppose we pick $S_{x},S_{y}\subseteq[q]$ of size $|S_{x}|,|S_{y}|\geq
q/\sqrt{|S|}$ independently and uniformly at random. Then, the probability
that $|(S_{x}\times S_{y})\cap S|>0$ is at least $1/4$.

###### Proof.

Let $U$ denote the random variable $|(S_{x}\times S_{y})\cap S|$. We will use
the second moment method, which says that

$\Pr[U>0]\geq\frac{(\mathbb{E}[U])^{2}}{\mathbb{E}[U^{2}]}.$

First, by linearity of expectation, we compute that
$\mathbb{E}[U]=|S_{x}|\cdot|S_{y}|\cdot(|S|/q^{2})=1$.

Next, again by linearity of expectation, we compute:

$\displaystyle\mathbb{E}[U^{2}]=$ $\displaystyle\sum_{(i,j)\in
S}\sum_{(i^{\prime},j^{\prime})\in S}\Pr[i,i^{\prime}\in S_{x}\text{ and
}j,j^{\prime}\in S_{y}]$ $\displaystyle=$ $\displaystyle\sum_{(i,j)\in
S}\Bigg{(}\left(\frac{1}{\sqrt{|S|}}\right)^{2}+\left(\frac{1}{\sqrt{|S|}}\right)^{3}\cdot|\\{(i^{\prime},j^{\prime})\in
S\mid i=i^{\prime}\text{ xor }j=j^{\prime}\\}|$
$\displaystyle+\left(\frac{1}{\sqrt{|S|}}\right)^{4}\cdot|\\{(i^{\prime},j^{\prime})\in
S\mid i\neq i^{\prime}\text{ and }j\neq j^{\prime}\\}|\Bigg{)}$
$\displaystyle=$
$\displaystyle\left(\frac{1}{\sqrt{|S|}}\right)^{2}\cdot|S|+\left(\frac{1}{\sqrt{|S|}}\right)^{3}\cdot(V_{x}(S)+V_{y}(S)-2|S|)$
$\displaystyle+\left(\frac{1}{\sqrt{|S|}}\right)^{4}\cdot(|S|^{2}-V_{x}(S)-V_{y}(S)+|S|)$
$\displaystyle=$ $\displaystyle
2+\frac{1}{|S|}-\frac{2}{|S|^{0.5}}+(V_{x}(S)+V_{y}(S))\cdot\left(\frac{1}{|S|^{1.5}}-\frac{1}{|S|^{2}}\right)$
$\displaystyle\leq$ $\displaystyle 4+\frac{1}{|S|}-\frac{4}{|S|^{0.5}}$
$\displaystyle<$ $\displaystyle 4,$

where the last step follows since $\frac{1}{s}-\frac{4}{\sqrt{s}}<0$ for all
$s\geq 1$.

In total, we get as desired that

$\Pr[U>0]\geq\frac{(\mathbb{E}[U])^{2}}{\mathbb{E}[U^{2}]}=\frac{1}{\mathbb{E}[U^{2}]}>\frac{1}{4}.$

∎

######  Lemma 3.7.

Suppose $q$ is a positive integer and $S\subseteq[q]^{2}$ is a nonempty
subset. Let $V_{x}(S):=\sum_{i\in[q]}|\\{j\in[q]\mid(i,j)\in S\\}|^{2}$ and
$V_{y}(S):=\sum_{j\in[q]}|\\{i\in[q]\mid(i,j)\in S\\}|^{2}$, and suppose that
$V_{x}(S)+V_{y}(S)\leq|S|^{1.5}$. Let $c$ be a positive integer.

Suppose we pick $S_{x},S_{y}\subseteq[q^{c}]$ of size $|S_{x}|,|S_{y}|\geq
q^{c}/\sqrt{|S|^{c}}$ independently and uniformly at random. Then, the
probability that $|(S_{x}\times S_{y})\cap S^{\otimes c}|>0$ is at least
$1/4$.

###### Proof.

Apply Lemma 3.6 to $S^{\otimes c}\subseteq[q^{c}]^{2}$. Note that
$V_{x}(S^{\otimes c})=(V_{x}(S))^{c}$ and $V_{y}(S^{\otimes
c})=(V_{y}(S))^{c}$, so the conditions are still satisfied after taking the
$c^{th}$ Kronecker power. ∎

###  3.3 Symmetrizing a tensor to avoid skew

######  Definition 3.8.

For a positive integer $q$, we say a set $S\subseteq[q]^{2}$ is _regular_ if
there are positive integers $a$ and $b$ such that, for all $i\in[q]$,
$|\\{j\in[q]\mid(i,j)\in S\\}|$ is either equal to $a$ or equal to $0$, and
similarly for all $j\in[q]$, $|\\{i\in[q]\mid(i,j)\in S\\}|$ is either equal
to $b$ or equal to $0$.

######  Lemma 3.9.

Suppose $q$ is a positive integer and $S\subseteq[q]^{2}$ is regular. Let
$V_{x}(S):=\sum_{i\in[q]}|\\{j\in[q]\mid(i,j)\in S\\}|^{2}$ and
$V_{y}(S):=\sum_{j\in[q]}|\\{i\in[q]\mid(i,j)\in S\\}|^{2}$. Then,
$V_{x}(S)\cdot V_{y}(S)\leq|S|^{3}$.

###### Proof.

If $S$ is empty, then the result holds since $V_{x}(S)=V_{y}(S)=|S|=0$.
Otherwise, assume without loss of generality that $(1,1)\in S$.

Let $a=|\\{j\in[q]\mid(1,j)\in S\\}|$, and $b=|\\{i\in[q]\mid(i,1)\in S\\}|$.
Since $S$ is regular, there are $|S|/a$ choices of $i\in[q]$ for which
$|\\{j\in[q]\mid(i,j)\in S\\}|=a$, and so $V_{x}(S)=\frac{|S|}{a}\cdot
a^{2}=a\cdot|S|$. Similarly, $V_{y}(S)=b\cdot|S|$, which means $V_{x}(S)\cdot
V_{y}(S)=a\cdot b\cdot|S|^{2}$.

Let $W:=\\{j\in[q]\mid(1,j)\in S\\}$, so $|W|=a$. Next, for each $j\in W$, let
$W_{j}:=\\{(i,j)\mid i\in[q]\text{ and }(i,j)\in S\\}\subseteq S$. Let
$W^{\prime}:=\bigcup_{j\in W}W_{j}\subseteq S$, and note that the $W_{j}$ sets
are disjoint, so $|W^{\prime}|=\sum_{j\in W}|W_{j}|$. By definition of $W$, we
know that $W_{j}$ is nonempty for each $j\in W$, and so $|W_{j}|=b$. It
follows that $|S|\geq|W^{\prime}|=|W|\cdot b=a\cdot b$.

We thus get as desired that $V_{x}(S)\cdot V_{y}(S)=a\cdot
b\cdot|S|^{2}\leq|S|^{3}$. ∎

######  Theorem 3.10.

Suppose $T$ is a $\langle q,q,q_{k}\rangle$-sized tensor. For any $f\geq 1$,
and any regular set $S_{f}\subseteq[q]^{2}$ such that
$\mathop{\operatorname{eff}}_{i,j}(T)\geq f$ for all $(i,j)\in S_{f}$, we have
$\omega_{\ell}\leq\log(\mathop{\operatorname{rank}}(T))/\log(f\cdot\sqrt{|S_{f}|})$.

###### Proof.

Define $T^{\prime}=T\otimes T^{\top}$ and $S^{\prime}_{f}=S_{f}\otimes
S_{f}^{\top}$. We can see that
$V_{x}(S^{\prime}_{f})=V_{y}(S^{\prime}_{f})=V_{x}(S_{f})\cdot V_{y}(S_{f})$.
By Lemma 3.9, this is at most $|S_{f}|^{3}=|S^{\prime}_{f}|^{1.5}$.
Furthermore, for any $i,i^{\prime},j,j^{\prime}\in[q]$ such that
$((i,j^{\prime}),(j,i^{\prime}))\in S^{\prime}_{f}$, we have that
$\mathop{\operatorname{eff}}_{(i,j^{\prime}),(j,i^{\prime})}(T^{\prime})=(\mathop{\operatorname{eff}}_{i,j}(T))\cdot(\mathop{\operatorname{eff}}_{j^{\prime},i^{\prime}}(T^{\top}))\geq
f^{2}$. We may thus apply Theorem 3.4 to $T^{\prime}$ and $S^{\prime}_{f}$ to
yield the desired result. ∎

######  Theorem 3.11 (Restatement of Theorem 1.1).

Suppose $T$ is a $\langle q,q,q_{k}\rangle$-sized tensor, then

$\omega_{\ell}\leq\frac{\log(\mathop{\operatorname{rank}}(T))}{\log(\mathop{\operatorname{eff}}(T))}.$

###### Proof.

Let $N$ be a sufficiently large positive integer. We will partition the set
$[q]^{N}\times[q]^{N}$ into many regular sets in the following way. For any
$(I,J)=((i_{1},\cdots,i_{N}),(j_{1},\cdots,j_{N}))\in([q]^{N})^{2}$, let
$p\in[q]^{2}\rightarrow\mathbb{N}$ be the counter, such that $p(u,v)$ counts
the number of pairs $(i_{\ell},j_{\ell})$ that equal to $(u,v)$, and let
$S_{p}\subseteq[q]^{2N}$ be the set including all such pairs $(I,J)$ whose
counter is $p$. We have that $\\{S_{p}\\}_{\\{p\\}}$ form a partition of
$[q]^{N}\times[q]^{N}$. We can also see that for every $p$, $S_{p}$ is a
regular set (since its definition does not depend on the order of the $N$
indices). Let
$f_{p}=\Pi_{i,j\in[q]}{\mathop{\operatorname{eff}}}_{i,j}(T)^{p(i,j)}$, every
pair $(I,J)\in S_{p}$ has ${\mathop{\operatorname{eff}}}_{I,J}(T^{\otimes
N})=f_{p}$. By Theorem 3.10, we have

$\displaystyle w_{\ell}\leq\frac{\log(\mathop{\operatorname{rank}}(T^{\otimes
N}))}{\log(\sqrt{f_{p}^{2}\cdot|S_{p}|})}.$

The next step is to choose the best $p$ that maximize $f_{p}^{2}\cdot|S_{p}|$.
Note that the number of different $p$ is upper bounded by $N^{q^{2}}$. And
thus

$\displaystyle\max_{p}f_{p}^{2}\cdot|S_{p}|\geq\frac{1}{N^{q^{2}}}\sum_{p}f_{p}^{2}|S_{p}|=\frac{1}{N^{q^{2}}}\sum_{p}\sum_{(I,J)\in
S_{p}}{\mathop{\operatorname{eff}}}_{I,J}(T^{\otimes
N})^{2}=\frac{1}{N^{q^{2}}}{\mathop{\operatorname{eff}}}(T^{\otimes N})^{2},$

where the last step is because $\\{S_{p}\\}_{\\{p\\}}$ is the partition of
$[q]^{N}\times[q]^{N}$ and the definition of
${\mathop{\operatorname{eff}}}(T)$.

Therefore, we have

$\displaystyle w_{\ell}\leq\frac{\log(\mathop{\operatorname{rank}}(T^{\otimes
N}))}{\log(\sqrt{f_{p}^{2}\cdot|S_{p}|})}\leq\frac{\log(\mathop{\operatorname{rank}}(T^{\otimes
N}))}{\log\left(\sqrt{\frac{1}{N^{q^{2}}}{\mathop{\operatorname{eff}}}(T^{\otimes
N})^{2}}\right)}=\frac{N\log(\mathop{\operatorname{rank}}(T))}{\log(\sqrt{\frac{1}{N^{q^{2}}}})+N\log({\mathop{\operatorname{eff}}}(T))}\leq\frac{\log(\mathop{\operatorname{rank}}(T))}{\log({\mathop{\operatorname{eff}}}(T))}+o(1),$

and the result follows from taking $N\rightarrow\infty$. ∎

##  4 Solving the $P$-light bulb problem with locality-sensitive hashing

##### General Faster Algorithm.

The general statement of Theorem 1.3 which applies to any tensor needs a few
definitions. Let $q\geq 2$ be an integer, and $P\in\mathbb{R}^{q\times q}$ be
a matrix of nonnegative real numbers whose entries sum to $1$, but whose
entries are _not_ all equal to $1/q^{2}$. We say that two vectors
$x,y\in[q]^{d}$ are _jointly sampled according to $P$_ if, for each
$\ell\in[d]$, the coordinates $x[\ell],y[\ell]$ are sampled independently of
all other coordinates, and $(x[\ell],y[\ell])=(i,j)$ with probability $P[i,j]$
for all $(i,j)\in[q]^{2}$.

We focus on a generalization of the light bulb problem which our algorithm is
naturally able to solve. In the _$P$ -light bulb problem_, one is given as
input vectors $x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}\in[q]^{d}$ which are all
independent and uniformly random except for a planted pair which has been
jointly sampled according to $P$, and the goal is to find the planted pair.
The light bulb problem with correlation $\rho$ is a special case of this
problem with $q=2$, $P[0,0]=P[1,1]=(1+\rho)/4$, $P[0,1]=P[1,0]=(1-\rho)/4$. It
could alternatively be viewed as a special case of this problem for any $q$
which is a power of $2$, along with the appropriately defined $P$.

###  4.1 Overview of the proof

Let $x^{*},y^{*}$ be the correlated pair. Since each bit of
$(x^{*}_{i},y^{*}_{i})$ is sampled according to the joint distribution $P$,
the number of coordinates $l$ such that $(x^{*}_{l},y^{*}_{l})=(i,j)$ will be
proportional to $P[i,j]$ in expectation. In fact, we will assume that the
number is equal to its expectation for all $(i,j)$; this happens with decent
probability, and will simplify our analysis. The assumption below that
$(x^{*},y^{*})$ falls into the set $V_{N}$ (defined in Eq. (4) below) captures
this property.

Given a tensor $T$ of size $\langle q,q,q\rangle$ along with its
$\mathop{\operatorname{eff}}$ matrix, our hope is that $(x^{*},y^{*})$ falls
into a bucket $(i,j)\in[q]^{2}$ with high $\mathop{\operatorname{eff}}_{i,j}$.
However, depending on how the $\mathop{\operatorname{eff}}$ matrix correlates
with the $P$ distribution matrix, this may not be the case. To address this,
we will choose a pair of stochastic matrices $Q_{x},Q_{y}$ (Def. 4.1 below)
which we use to process vectors after they have been sampled, so that $P$
after this transformation will be correlated with
$\mathop{\operatorname{eff}}$.

More precisely, we use $Q_{x}$ and $Q_{y}$ to decide which bucket every vector
goes into as follows. Take a vector $x$ as example. For every coordinate $l$,
if $x_{l}=i$, we switch $x_{l}$ to $j$ with probability $Q_{x}[i,j]$. The
final $x$ after this transformation is the bucket we put this vector into.
Vectors $y$ are transformed in a similar way, but with the matrix $Q_{y}$.
Note that different buckets may have different numbers of points since the
matrices $Q_{x},Q_{y}$ are not necessarily doubly-stochastic. This needs to be
taken into account since $(x^{*}_{i},y^{*}_{i})$ wil only be detected it they
are put into a bucket where $\mathop{\operatorname{eff}}_{i,j}^{2}$ is larger
than the number of pairs of points. Below we will rescale
$\mathop{\operatorname{eff}}$ by $\partial_{x}$ and $\partial_{y}$ (Def. 4.1
below) to “normalize” this effect.

Ultimately we need to optimize over choices of $Q_{x},Q_{y}$ to achieve the
best running time. The number $\gamma_{Q_{x},Q_{y}}$ (Def. 4.1 below)
indicates the performance of particular matrices $Q_{x},Q_{y}$. The higher
this number is, the better the choice of $Q_{x},Q_{y}$.

Ultimately we will find using properties of the Kronecker power that many
buckets shares the same property: they have the same chance that of containing
the correlated pair $(x^{*},y^{*})$, and they have the same
$\mathop{\operatorname{eff}}$ value. We cluster these buckets into many
groups, each specified by a mapping $\tau$ (Def. 4.6 below). We find the best
cluster $S_{\tau}$ in Lemma 4.8 below, and our algorithm will only consider
the buckets inside this cluster to find $(x^{*},y^{*})$. (We will calculate
that other clusters give a negligible additional probability of finding
$(x^{*},y^{*})$.) Similar to Theorem 3.4 above, we copy $x^{*}$ and $y^{*}$
multiple times to guarantee that there is a constant probability that at least
one copy falls into a bucket in that cluster.

Similar to before, we will aim to use Lemma 3.6, and toward this goal, we need
to ensure our cluster $S_{\tau}$ is not too “skewed”. Similar to Section 3.3
above, we consider the Kronecker power of $S_{\tau}$ with its transpose
$S_{\tau}^{\top}$ to “symmetrize” the cluster and avoid this issue. Section
4.4.2 below is devoted to dealing with this issue.

See Algorithm 2 below for the full algorithm description.

###  4.2 Preliminaries

Given any tensor $T$, we now define its
$P\text{-}\mathop{\operatorname{eff}}(T)$, a generalization of
$\mathop{\operatorname{eff}}(T)$. We start by defining some useful functions.

######  Definition 4.1 ($\mathop{\operatorname{effQ}}$ and $\gamma$).

Suppose $T$ is a $\langle q,q,q_{k}\rangle$-sized tensor. Given two stochastic
matrices $Q_{x},Q_{y}\in\mathbb{R}^{q\times q}$, define
$\partial_{x}(i):=\sum_{j\in[q]}Q_{x}[i,j]$ for $i\in[q]$, and same for
$\partial_{y}$. we define the Q version of $\mathop{\operatorname{eff}}(T)$ as
follows. For $i,j\in[q]$,

$\mathop{\operatorname{effQ}}_{i,j}(Q_{x},Q_{y},T):=\frac{\sum_{k\in[q_{k}]}T(\mathsf{X}_{i,k}\mathsf{Y}_{j,k}\mathsf{Z}_{i,j})}{\sqrt{\sum_{i^{\prime},j^{\prime}\in[q],k,k^{\prime}\in[q_{k}]}T(\mathsf{X}_{i^{\prime},k}\mathsf{Y}_{j^{\prime},k^{\prime}}\mathsf{Z}_{i,j})^{2}\partial_{x}(i^{\prime})\partial_{y}(j^{\prime})}}.$

Given a joint probability matrix $P\in\mathbb{R}^{p\times p}$, we further
define the performance of $Q_{x},Q_{y}$ as

$\displaystyle\gamma_{Q_{x},Q_{y}}:=\prod_{i,j\in[q]}\left(\sum_{u,v\in[q]}Q_{x}[i,u]Q_{y}[j,v](\mathop{\operatorname{effQ}}_{u,v}(Q_{x},Q_{y},T))^{2}\right)^{P[i,j]}.$

Let $\gamma$ be the best $\gamma_{Q_{x},Q_{y}}$ over all stochastic matrices
$Q_{x},Q_{y}$.

$\displaystyle\gamma:=\max_{Q_{x},Q_{y}}\gamma_{Q_{x},Q_{y}},$

Note that $\mathop{\operatorname{effQ}}$ is multiplicative: suppose
$T,T^{\prime}$ both have size $\langle q,q,q_{k}\rangle$, and $Q_{x}$,
$Q_{x}^{\prime}$, $Q_{y}$, $Q_{y}^{\prime}$ are all stochastic matrices, then
for $(i,i^{\prime}),(j,j^{\prime})\in[q]^{2}$, we have
$\mathop{\operatorname{effQ}}_{(i,i^{\prime}),(j,j^{\prime})}(Q_{x}\otimes
Q_{x}^{\prime},Q_{y}\otimes Q_{y}^{\prime},T\otimes
T^{\prime})=\mathop{\operatorname{effQ}}_{i,j}(Q_{x},Q_{y},T)\cdot\mathop{\operatorname{effQ}}_{i^{\prime},j^{\prime}}(Q_{x}^{\prime},Q_{y}^{\prime},T^{\prime}).$

######  Remark 4.2.

By choosing matrix $Q_{x},Q_{y}$ to be the matrix where each entry is $1/q$,
$\mathop{\operatorname{effQ}}(T)$ is the same as
$\mathop{\operatorname{eff}}(T)$ and thus
$\gamma\geq\mathop{\operatorname{eff}}(T)^{2}/q^{2}$.

We finally define:

$\displaystyle P\text{-}\mathop{\operatorname{eff}}(T):=\sqrt{\gamma\cdot
q^{2}}.$

Here’s our main theorem of this section.

######  Theorem 4.3.

Suppose $T$ is a $\langle q,q,q_{k}\rangle$-sized tensor. Suppose there are
$n$ vectors uniformly independently sampled from $[q]^{d}$, with a planted
pair $(x^{*},y^{*})$ where each bit of them is sampled from a symmetric joint
probability matrix $P\in\mathbb{R}^{q\times q}$.

Let $\gamma$ be as defined in Definition 4.1, then $(x^{*},y^{*})$ can be
found in $O(n^{\omega_{P}+o(1)})$ time, where

$\displaystyle\omega_{P}\leq\frac{\log\mathop{\operatorname{rank}}(T)}{\log(q\gamma^{1/2})}.$

Theorem 1.3 follows from Theorem 4.3 by finding the optimal $Q$ for the tensor
$T_{2112}$ (see Section 5 for the definition of $T_{2112}$) and the matrix $P$
arising from $\rho$ in the light bulb problem; see the Example 4.4 below for
more details.

######  Example 4.4.

Consider our standard light-bulb problem where the correlated pair has
$\rho$-correlation, i.e.,

$\displaystyle P_{\rho}=\begin{pmatrix}\frac{1+\rho}{4}&\frac{1-\rho}{4}\\\
\frac{1-\rho}{4}&\frac{1+\rho}{4}\end{pmatrix}.$

Let $a\in[0,1]$ be some parameter, let both $Q_{x}$ and $Q_{y}$ be

$\displaystyle Q_{x}=Q_{y}=\begin{pmatrix}1-a&a\\\ a&1-a\end{pmatrix}.$

Given our $T_{2112}$ tensor, by definition of $\gamma_{Q_{x},Q_{y}}$
(Definition 4.1), we can calculate

$\displaystyle\gamma_{Q_{x},Q_{y}}=\left(2\cdot\big{(}(1-a)^{2}+a^{2}\big{)}+1\cdot\big{(}2a(1-a)\big{)}\right)^{\frac{1+\rho}{2}}\left(2\cdot\big{(}2a(1-a)\big{)}+1\cdot\big{(}(1-a)^{2}+a^{2}\big{)}\right)^{\frac{1-\rho}{2}}.$

The optimal $a$ is given as $a=\max\\{0,(1-\sqrt{3\rho})/2\\}$. Write
$\omega_{\rho}$ to be the exponent $\omega_{P}$ in Theorem 4.3 given our
$P=P_{\rho}$. Then we get

$\displaystyle w_{\rho}=\begin{cases}\frac{2\log
5}{\log\left(6(1-\rho)^{-\rho/2}(1+\rho)^{\rho/2}(1-\rho^{2})^{1/2}\right)}&\textrm{,when~{}}\rho<1/3\\\
\frac{4\log 5}{(5+\rho)\log 2}&\textrm{,when~{}}1/3\leq\rho\leq 1.\end{cases}$

In the remainder of this section, we prove Theorem 4.3.

###  4.3 Preparation before symmetrization

We will show that for every stochastic $Q_{x},Q_{y}$, our algorithm gives an
exponent $\omega_{P}\leq
2\frac{\log\mathop{\operatorname{rank}}(T)}{\log(\gamma_{Q_{x},Q_{y}})}$ and
therefore, the theorem follows by choosing the best $Q_{x}$ and $Q_{y}$. In
the following, we assume $Q_{x},Q_{y}$ are fixed stochastic matrices.

Fix a joint probability matrix $P$. Let $N$ be a sufficiently large positive
integer so that $P[i,j]N$ are all integers.111111We only need this property
when constructing the set $V_{N}$. There is a negligible change in our
algorithm if we round $P[i,j]\cdot N$ to be the integer closest to
$P[i,j]\cdot N$ in the construction of $V_{N}$ for large $N$. Define the set
$V_{N}$ as all pairs of $(x,y)$ where there are exactly $P[i,j]\cdot N$ number
of coordinates $l$ such that $(x[l],y[l])=(i,j)$,

$\displaystyle V_{N}:=\\{(x,y)\in[q]^{N}:\forall
i,j\in[q],~{}|\\{l\mid(x[l],y[l])=(i,j)\\}|=P[i,j]\cdot N\\}.$ (4)

If the planted pair $(x^{*},y^{*})$ is drawn from the joint distribution $P$,
then there’s a descent chance that $(x^{*},y^{*})\in V_{N}$.

######  Definition 4.5 (Distribution $\mathcal{D}^{x}$ and $\mathcal{D}^{y}$).

Let $i\in[q]$ and $Q_{x}\in\mathbb{R}^{q\times q}$ be a stochastic matrix, we
define the distribution $\mathcal{D}_{Q_{x}}^{i}\in\mathbb{R}^{q}$ as

$\mathcal{D}_{Q_{x}}^{i}(j):=Q_{x}[i,j],~{}\forall j\in[q].$

In another words, the distribution $\mathcal{D}_{Q_{x}}^{i}$ is generated by
transforming $i$ to $j$ with probability $Q_{x}[i,j]$.

Let $x\in[q]^{N}$ be any vector, we define the distribution
$\mathcal{D}_{Q_{x}^{\otimes N}}^{x}\in\mathbb{R}^{q^{N}}$ as

$\mathcal{D}_{Q_{x}^{\otimes
N}}^{x}:=\otimes_{l=1}^{N}\mathcal{D}_{Q_{x}}^{x[l]}.$

In another words, the distribution $\mathcal{D}_{Q_{x}^{\otimes N}}^{x}$ is
generated by transforming independently each entry $x[\ell]$ to
$x^{\prime}[\ell]$ with probability $Q_{x}[x[\ell],x^{\prime}[\ell]]$.

Similarly, we define

$\displaystyle\mathcal{D}^{y}_{Q_{y}^{\otimes
N}}:=\otimes_{l=1}^{N}\mathcal{D}^{y[l]}_{Q_{y}}\in\mathbb{R}^{q^{N}}.$

For simplicity, if $Q_{x}$ and $Q_{y}$ are clear from the context, we write
$\mathcal{D}^{x}_{Q_{x}^{\otimes N}}$ as $\mathcal{D}^{x}$ and
$\mathcal{D}^{y}_{Q_{y}^{\otimes N}}$ as $\mathcal{D}^{y}$.

We define $\mathcal{D}^{x,y}:=\mathcal{D}^{x}\otimes\mathcal{D}^{y}$ to be
their joint distribution. In particular, for
$x^{\prime},y^{\prime}\in[q]^{n}$, we will write
$\mathcal{D}^{x,y}(x^{\prime},y^{\prime})=\mathcal{D}^{x}(x^{\prime})\cdot\mathcal{D}^{y}(y^{\prime})$
to denote the probability that $\mathcal{D}^{x,y}$ outputs
$(x^{\prime},y^{\prime})$.

Next, similar to the proof of Theorem 3.11, we will partition the entire space
$[q]^{N}\times[q]^{N}$ into several regular sets.

######  Definition 4.6 ($\tau$-partition).

Call a mapping $\tau:[q]^{4}\rightarrow\\{0,1,\cdots,N\\}$ _valid_ if for all
$i,j\in[q]$, we have $\sum_{u,v\in[q]}\tau(i,j,u,v)=N\cdot P[i,j]$. Fix a pair
$(x^{*},y^{*})\in V_{N}$. Every pair $(x,y)\in[q]^{N}\times[q]^{N}$
_corresponds to_ one valid mapping $\tau$ defined by
$\tau(i,j,u,v)=|\\{l:(x^{*}[l],y^{*}[l])=(i,j)~{}\textrm{and}~{}(x[l],y[l])=(u,v)\\}|$.
For a valid mapping $\tau$, let $S_{\tau}^{x^{*},y^{*}}\subseteq[q]^{2N}$ be
the set of all pairs $(x,y)$ that correspond to $\tau$. When $x^{*},y^{*}$ is
clear from the context, we simply write $S_{\tau}$ instead of
$S_{\tau}^{x^{*},y^{*}}$.

We next make some key observations about valid mappings $\tau$.

######  Fact 4.7.

Fix $(x^{*},y^{*})\in V_{N}$, then

  1. 1.

$\\{S_{\tau}\\}_{\\{\text{valid }\tau\\}}$ is a partition of
$[q]^{N}\times[q]^{N}$;

  2. 2.

$S_{\tau}$ is regular for all valid $\tau$;

  3. 3.

Every $(x,y)\in S_{\tau}$ has the same $\mathcal{D}^{x^{*},y^{*}}(x,y)$, since
$\mathcal{D}^{x^{*},y^{*}}(x,y)=\prod_{i,j,u,v}(Q_{x}[i,u]Q_{y}[j,v])^{\tau(i,j,u,v)}$
only depends on $\tau$. For simplicity, we denote them as
$\mathcal{D}_{\tau}$;

  4. 4.

Every $(x,y)\in S_{\tau}$ has the same
$\mathop{\operatorname{effQ}}_{x,y}(T^{\otimes N})$, since

$\mathop{\operatorname{effQ}}_{x,y}(Q_{x}^{\otimes N},Q_{y}^{\otimes
N},T^{\otimes
N})=\prod_{i,j,u,v}\mathop{\operatorname{effQ}}_{u,v}(Q_{x},Q_{y},T)^{\tau(i,j,u,v)}$

only depends on $\tau$. For simplicity, we denote them as
$\mathop{\operatorname{effQ}}_{\tau}$.

###### Proof.

1\. This is because each pair $(x,y)$ corresponds to exactly one valid $\tau$.

2\. For $i,j\in[q]$, let $Z_{i,j}:=\\{l\mid
x^{*}[l]=i~{}\textrm{and}~{}y^{*}[l]=j\\}\subseteq[N]$, and let
$(S_{\tau})_{i,j}\subseteq[q]^{Z_{i,j}}$ be the set of pairs
$(x,y)\in[q]^{Z_{i,j}}$ for which, for all $(u,v)\in[q]^{2}$, we have
$|\\{\ell\in Z_{i,j}\mid(x[\ell],y[\ell])=(u,v)\\}|=\tau(i,j,u,v)$. We can see
that $(S_{\tau})_{i,j}$ is regular since it is defined independently of the
order of the indices. Thus, $S_{\tau}=\otimes_{i,j}(S_{\tau})_{i,j}$, which is
a Kronecker product of regular sets $(S_{\tau})_{i,j}$, is also regular.

3 and 4. Proved in the statement. ∎

######  Lemma 4.8.

Let $N$ be a sufficient large integer. Let $(x^{*},y^{*})\in V_{N}$ be any
pair. Then there exists a valid mapping $\tau$ such that

$\mathcal{D}_{\tau}\cdot|S_{\tau}|\cdot{\mathop{\operatorname{effQ}}}_{\tau}^{2}\geq\frac{1}{(N+1)^{q^{4}}}\gamma_{Q_{x},Q_{y}}^{N},$

where $\gamma_{Q_{x},Q_{y}}$ is defined in Definition 4.1.

###### Proof.

$\displaystyle~{}\max_{\tau}\mathcal{D}_{\tau}\cdot|S_{\tau}|\cdot{\mathop{\operatorname{effQ}}}_{\tau}^{2}$
$\displaystyle\geq$
$\displaystyle~{}\frac{1}{(N+1)^{q^{4}}}\sum_{\tau}\mathcal{D}_{\tau}\cdot|S_{\tau}|\cdot{\mathop{\operatorname{effQ}}}_{\tau}^{2}$
$\displaystyle=$
$\displaystyle~{}\frac{1}{(N+1)^{q^{4}}}\sum_{\tau}\mathbb{E}_{(x,y)\sim\mathcal{D}^{x^{*},y^{*}}}[{\mathop{\operatorname{effQ}}}_{x,y}^{2}(T^{\otimes
N})\cdot\big{[}(x,y)\in S_{\tau}\big{]}_{\mathbf{1}}]$ $\displaystyle=$
$\displaystyle~{}\frac{1}{(N+1)^{q^{4}}}\mathbb{E}_{(x,y)\sim\mathcal{D}^{x^{*},y^{*}}}[{\mathop{\operatorname{effQ}}}^{2}_{x,y}(T^{\otimes
N})],$

where the first step follows because there are at most $(N+1)^{q^{4}}$
different valid $\tau$, the second step follows from part 3 and part 4 of Fact
4.7, the third step follows from part 1 of Fact 4.7. We conclude by computing
that

$\displaystyle~{}\mathbb{E}_{(x,y)\sim\mathcal{D}_{x^{*},y^{*}}}[{\mathop{\operatorname{effQ}}}^{2}_{x,y}(T^{\otimes
N})]$ $\displaystyle=$
$\displaystyle~{}\mathbb{E}_{\begin{subarray}{c}(x_{1},y_{1})\sim\mathcal{D}^{x_{1}^{*},y_{1}^{*}}\\\
~{}\vdots~{}\\\
(x_{N},y_{N})\sim\mathcal{D}^{x_{N}^{*},y_{N}^{*}}\end{subarray}}[\Pi_{i=1}^{N}{\mathop{\operatorname{effQ}}}^{2}_{x_{i},y_{i}}(T)]$
$\displaystyle=$
$\displaystyle~{}\prod_{i=1}^{N}\mathbb{E}_{(x_{i},y_{i})\sim\mathcal{D}^{x_{i}^{*},y_{i}^{*}}}[{\mathop{\operatorname{effQ}}}^{2}_{x_{i},y_{i}}(T)]$
$\displaystyle=$
$\displaystyle~{}\prod_{i,j\in[q]}\left(\sum_{u,v\in[q]}Q_{x}[i,u]Q_{y}[j,v]{\mathop{\operatorname{effQ}}}_{u,v}^{2}(T)\right)^{P_{i,j}N}$
$\displaystyle=$ $\displaystyle\gamma_{Q_{x},Q_{y}}.\qed$

We also give this lemma for later use.

######  Lemma 4.9.

Suppose $q$ is even, and $P\in\mathbb{R}^{q\times q}$ is a joint probability
matrix. There exist two mappings $h,g:[q]\rightarrow\\{-1,1\\}$ and a constant
$\rho>0$ such that:

  * •

If $b_{0},b_{1}$ are sampled independently from $[q]$, and at least one of
them is sampled uniformly, then $\mathbb{E}[g(b_{0})\cdot h(b_{1})]=0$, but

  * •

If $b_{0},b_{1}$ are sampled from $[q]$ according to $P$ (so
$(b_{0},b_{1})=(i,j)$ with probability $P[i,j]$), then
$\mathbb{E}[g(b_{0})\cdot h(b_{1})]=\rho$.

###### Proof.

We construct $g,h$ in a greedy fashion. Pick any row of $P$ that is not
uniform. Such a row exists since we assume $P$ is not the uniform matrix. Fix
$g$ to map the column indices of the $q/2$ largest entries in that row to $1$,
and the others to $-1$. Let $v:=P\cdot g\in\mathbb{R}^{q}$. Fix $h$ to map the
indices of the $q/2$ largest entries of $v$ to $1$ and the others to $-1$.

If $b_{0}$ or $b_{1}$ is sampled uniformly from $[q]$, then $g(b_{0})$ or
$h(b_{1})$, respectively, is uniformly chosen from $\\{-1,1\\}$ since $h$ and
$g$ each map half of $[q]$ to $1$ and the other half to $-1$. Hence, in this
case, if $b_{0}$ and $b_{1}$ are sampled independently, then
$\mathbb{E}[g(b_{0})\cdot h(b_{1})]=0$.

Meanwhile, by our construction of $h$,

$\mathbb{E}_{(b_{0},b_{1})\sim P}[g(b_{0})\cdot h(b_{1})]=\langle
v,h\rangle>0,$

which is strictly larger than $0$ because $v$ is non-zero. We may thus pick
$\rho=\langle v,h\rangle$. ∎

Algorithm 2

1:Input

2:Let $T$ be a $\langle q,q,q_{k}\rangle$-sized tensor.

3:Let $x_{1},\cdots,x_{n},y_{1},\cdots,y_{n}\in[q]^{d}$ be $2n$ vectors with
one planted pair $(x^{*},y^{*})$.

4:Let $P\in\mathbb{R}^{q\times q}$ be joint-probability symmetric matrix for
planted pair, that every bit $(x^{*}[l],y^{*}[l])$ is sampled according to
$P$.

5:Algorithm

6:Let $\gamma$ and its corresponding stochastic matrices
$Q_{x},Q_{y}\in\mathbb{R}^{q\times q}$ be from Definition 4.1.

7:Let $N$ be such that $q^{2N}\gamma^{N}=20n\cdot(N+1)^{q^{4}}$

8:$T^{\prime}\leftarrow(T\otimes T^{\top})^{\otimes N}$

9:for $g$ a power of $2$ from
$1,2,4\cdots,\max_{i,j}\mathop{\operatorname{eff}}_{i,j}(T^{\prime})$ do

10: Prepare $q^{2N}$ sets indexed by vector in $[q]^{2N}$ for both $x$ and
$y$, $X_{1},\cdots,X_{q^{2N}}$, $Y_{1},\cdots,Y_{q^{2N}}$.

11: $c\leftarrow q^{2N}\cdot g/n$

12: for each $x_{i}$, independently generate $c$ indices $i_{1},\cdots,i_{c}$
from $\mathcal{D}^{x_{i}}_{Q_{x}^{\otimes N}\otimes Q_{y}^{\otimes N}}$ and
add $\\{i\\}$ to every $X_{i_{j}}$.

13: for each $y_{i}$, independently generate $c$ indices $i_{1},\cdots,i_{c}$
from $\mathcal{D}^{y_{i}}_{Q_{y}^{\otimes N}\otimes Q_{x}^{\otimes N}}$ and
add $\\{i\\}$ to every $Y_{i_{j}}$.

14: Find correlated pair under such groupings. $\triangleright$ See details in
Section 4.4.4

15:end for

###  4.4 Proof of Theorem 4.3

In Lemma 4.8 from the previous section, we found the best mapping $\tau$, and
we aimed to use $S_{\tau}$ to detect the correlated pair. However, although
$S_{\tau}$ is a regular set, it still can be “skewed” (in the sense of Section
3.2). In this section, at a high level, we are going to symmetrize $S_{\tau}$
using a Kronecker product with its transpose $S_{\tau}^{\top}$ to avoid skew.
We will prove Theorem 4.3 in four steps.

####  4.4.1 Step 1. General start

We may assume $\gamma>1/q$, since otherwise, the bound on $\omega_{P}$ we
claim in Theorem 4.3 is worse than the trivial exponent of $2$. We first fix
$N$ such that

$\displaystyle q^{2N}=20n\left(\frac{1}{\gamma}\right)^{N}(N+1)^{q^{4}}.$ (5)

Note that $N=\Theta_{q}(\log n)$.

For simplicity, let us assume that the input vectors are long enough; as
discussed in the introduction and early proofs, that one can use the
‘compressed matrices’ method introduced in [KKK18, Section 4.2] to ‘expand’
lower-dimensional vectors without losing too much correlations on correlated
pair.

Let the planted pair be $(x^{*},y^{*})$. We abuse notation here and also write
$x^{*},y^{*}\in[q]^{2N}$ to denote the first $2N$ coordinates of the planted
pair. We write $x^{*}=x_{1}^{*}\circ x_{2}^{*}$, where
$x^{*}_{1},x^{*}_{2}\in[q]^{N}$, and write $y^{*}=y_{1}^{*}\circ y_{2}^{*}$ in
the same way. (Here $\circ$ denotes vector concatenation.)

We will use Algorithm 2 to solve the problem. As suggested by line 9 to line
15 of the algorithm, our goal here is to copy every vector $c$ times and
partition them into $q^{2N}$ groups, with each group containing roughly $g$
vectors (so $nc/g\approx q^{2N}$). Our algorithm enumerates over $g$ from $1$
to $(\max_{i,j}\mathop{\operatorname{eff}}_{i,j})^{2N}$ by doubling each time.
We are going to prove that we will successfully find the correlated pair for
one of these choices of $g$.

We set aside the first $2N$ entries of each input vector which we will use to
decide the grouping. We will later use fresh entries from the input vectors in
later parts of the algorithm (when we perform matrix multiplication) so that
there is no correlation between the independent random vectors which are
placed in the same group.

With probability $1/(q^{N})^{o(1)}$, we have both pairs
$(x^{*}_{1},y^{*}_{1}),(x^{*}_{2},y^{*}_{2})\in V_{N}$. We will assume this
happens in the later analysis, since it only cost a $1/(q^{N})^{o(1)}$
overhead on the running time by repeating the algorithm using fresh bits.

####  4.4.2 Step 2. Symmetrizing $S_{\tau}$

Recall that $Q_{x},Q_{y}\in\mathbb{R}^{q\times q}$ are the given stochastic
matrices. We apply $Q_{x}$ to $x_{1}^{*}$ and $Q_{y}$ to $y_{1}^{*}$, and let
$\tau_{1}$ be the best $\tau$ chosen from Lemma 4.8 with respect to
$x_{1}^{*},y_{1}^{*},Q_{x},Q_{y}$. For ease of presentation, we will still use
notation $S_{\tau}$, $\mathcal{D}_{\tau}$,
$\mathop{\operatorname{effQ}}_{\tau}$ in the Lemma 4.8 and note that they are
with respect to $\tau_{1}$ and $x_{1}^{*}$, $y_{1}^{*}$, $Q_{x}$, $Q_{y}$,
i.e., we have

$\displaystyle S_{\tau}=$
$\displaystyle~{}S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}},~{}~{}~{}\textrm{and}$
$\displaystyle\forall(x,y)\in S_{\tau},~{}\mathcal{D}_{\tau}=$
$\displaystyle~{}\mathcal{D}_{Q_{x}^{\otimes N},Q_{y}^{\otimes
N}}^{x_{1}^{*},y_{1}^{*}}(x,y),$ (6) $\displaystyle\forall(x,y)\in
S_{\tau},~{}\mathop{\operatorname{effQ}}_{\tau}=$
$\displaystyle~{}\mathop{\operatorname{effQ}}_{x,y}(Q_{x}^{\otimes
N},Q_{y}^{\otimes N},T^{\otimes N}).$

Now, consider symmetrizing $S_{\tau}$ as follows. Let $\tau_{2}$ be the
(“transposed”) mapping such that, for all $i,j,u,v\in[q]$, we have
$\tau_{2}(i,j,u,v):=\tau_{1}(j,i,v,u)$. Since $P$ is a symmetric matrix, we
know that $\tau_{2}$ is also _valid_. Define
$S:=S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}}\otimes
S_{\tau_{2}}^{x_{2}^{*},y_{2}^{*}}\subseteq[q]^{2N}$, and we will show in
Claim 4.10, $S=S_{\tau}\otimes S_{\tau}^{\top}$. For the purpose of
symmetricity, we will further apply $Q_{y}$ to $x_{2}$ and $Q_{x}$ to $y_{2}$.
We are able to do so because $P$ is symmetric and thus,
$(y_{2}^{*},x_{2}^{*})$ is also in $V_{N}$.

We will prove that, with a careful choice of $c$ (the number of copies we make
of each vector), there will be a decent probability that a copy of the planted
pair falls into some bucket in $S$. To do this, we first need to prove $S$ is
not skewed. The following are some useful fact about $S$.

######  Claim 4.10.

$(S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}})^{\top}=S_{\tau_{2}}^{y_{1}^{*},x_{1}^{*}}$.

###### Proof.

$\displaystyle~{}(S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}})^{\top}$ $\displaystyle=$
$\displaystyle~{}\\{(x,y)\in[q]^{2N}:\forall
i,j,u,v\in[q]~{}\left|\\{\ell\in[N]:x_{1}^{*}[\ell]=i~{}\textrm{and}~{}y_{1}^{*}[\ell]=j~{}\textrm{and}~{}x[\ell]=v~{}\textrm{and}~{}y[\ell]=u\\}\right|=\tau_{1}(i,j,u,v)\\}$
$\displaystyle=$ $\displaystyle~{}\\{(x,y)\in[q]^{2N}:\forall
i,j,u,v\in[q]~{}\left|\\{\ell\in[N]:x_{1}^{*}[\ell]=i~{}\textrm{and}~{}y_{1}^{*}[\ell]=j~{}\textrm{and}~{}x[\ell]=v~{}\textrm{and}~{}y[\ell]=u\\}\right|=\tau_{2}(j,i,v,u)\\}$
$\displaystyle=$ $\displaystyle~{}\\{(x,y)\in[q]^{2N}:\forall
i,j,u,v\in[q]~{}\left|\\{\ell\in[N]:x_{1}^{*}[\ell]=j~{}\textrm{and}~{}y_{1}^{*}[\ell]=i~{}\textrm{and}~{}x[\ell]=u~{}\textrm{and}~{}y[\ell]=v\\}\right|=\tau_{2}(i,j,u,v)\\}$
$\displaystyle=$ $\displaystyle~{}S_{\tau_{2}}^{y_{1}^{*},x_{1}^{*}},$

where the first step is by definition, the second step replaces $\tau_{1}$
with $\tau_{2}$, and the third step is by switching variables. ∎

######  Definition 4.11.

For a ground set $U$, we say two sets $S_{1},S_{2}\subseteq U^{2}$ are
_isomorphic_ if they are equal up to permuting first and second coordinates,
i.e., there are permutations $\pi_{1},\pi_{2}:U\to U$ such that, for all
$(a,b)\in U^{2}$, $(a,b)\in S_{1}$ if and only if $(\pi_{1}(a),\pi_{2}(b))\in
S_{2}$.

######  Claim 4.12.

1\. $V_{x}(S),V_{y}(S)\leq|S|^{1.5}$; ($V_{x}(S)$, $V_{y}(S)$ is defined in
Definition 3.3)

2\. $|S|=|S_{\tau}|^{2}$;

3\. $\forall(x,y)\in S$, $\mathcal{D}^{x^{*}}_{Q_{x}^{\otimes N}\otimes
Q_{y}^{\otimes N}}(x)=\mathcal{D}^{y^{*}}_{Q_{y}^{\otimes N}\otimes
Q_{x}^{\otimes N}}(y)=\mathcal{D}_{\tau}$;

4\. Let $\widetilde{T}:=T^{\otimes N}$. For all $(x,y)\in S$, we have
${\mathop{\operatorname{effQ}}}_{x,y}(Q_{x}^{\otimes N}\otimes Q_{y}^{\otimes
N},Q_{y}^{\otimes N}\otimes Q_{x}^{\otimes
N},\widetilde{T}\otimes\widetilde{T}^{\top})=\mathop{\operatorname{effQ}}_{\tau}^{2}$.

###### Proof.

Part 1 and 2.

For any valid $\tau$ and $(x_{1},y_{1}),(x_{2},y_{2})\in V_{N}$, the sets
$S^{x_{1},y_{1}}_{\tau}$ and $S^{x_{2},y_{2}}_{\tau}$ are isomorphic, since
the definition of $S_{\tau}$ does not depend on the order of the $N$ indices.
Therefore, because both $(y_{1}^{*},x_{1}^{*})$ and $(x_{2}^{*},y_{2}^{*})$
are in $V_{N}$, we know that $S^{y_{1}^{*},x_{1}^{*}}_{\tau_{2}}$ is
isomorphic to $S^{x_{2}^{*},y_{2}^{*}}_{\tau_{2}}$. By Claim 4.10,
$(S_{\tau_{2}}^{y_{1}^{*},x_{1}^{*}})^{\top}=S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}}$,
so

$\displaystyle|S|=|S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}}|\cdot|S_{\tau_{2}}^{x_{2}^{*},y_{2}^{*}}|=|S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}}|\cdot|S_{\tau_{2}}^{y_{1}^{*},x_{1}^{*}}|=|S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}}|^{2},$

and

$\displaystyle V_{x}(S)=V_{x}(S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}})\cdot
V_{x}(S_{\tau_{2}}^{x_{2}^{*},y_{2}^{*}})=V_{x}(S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}})\cdot
V_{y}(S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}})\leq|S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}}|^{3}=|S|^{1.5},$

where the third step follows because $S_{\tau_{1}}^{x_{1}^{*},y_{1}^{*}}$ is
regular (by part 2 of Fact 4.7) and by Lemma 3.9.

$V_{y}(S)\leq|S|^{1.5}$ follows for the same reason.

Part 3. For all $(x,y)\in S$,

$\displaystyle\mathcal{D}^{x^{*}}_{Q_{x}^{\otimes N}\otimes Q_{y}^{\otimes
N}}(x)=\prod_{i,j,u,v}(Q_{x})_{i,u}^{\tau_{1}(i,j,u,v)}\prod_{i,j,u,v}(Q_{y})_{i,u}^{\tau_{2}(i,j,u,v)}=\prod_{i,j,u,v}(Q_{x})_{i,u}^{\tau_{1}(i,j,u,v)}\prod_{i,j,u,v}(Q_{y})_{j,v}^{\tau_{1}(i,j,u,v)}=\mathcal{D}_{\tau},$

where the second step is by the symmetry of $\tau_{1}$ and $\tau_{2}$, and the
last step is by the definition of $\mathcal{D}_{\tau}$ (part 3 of Fact 4.7).
Similarly,

$\displaystyle\mathcal{D}^{y^{*}}_{Q_{y}^{\otimes N}\otimes Q_{x}^{\otimes
N}}(y)=\prod_{i,j,u,v}(Q_{y})_{j,v}^{\tau_{1}(i,j,u,v)}\prod_{i,j,u,v}(Q_{x})_{j,v}^{\tau_{2}(i,j,u,v)}=\prod_{i,j,u,v}(Q_{y})_{j,v}^{\tau_{1}(i,j,u,v)}\prod_{i,j,u,v}(Q_{x})_{i,u}^{\tau_{1}(i,j,u,v)}=\mathcal{D}_{\tau}.$

Part 4. For all $x,y\in S$, we write $x=x_{1}\circ x_{2}$ and $y=y_{1}\circ
y_{2}$ to partition them into two halves. Then,

${\mathop{\operatorname{effQ}}}_{x,y}(Q_{x}^{\otimes N}\otimes Q_{y}^{\otimes
N},Q_{y}^{\otimes N}\otimes Q_{x}^{\otimes
N},\widetilde{T}\otimes\widetilde{T}^{\top})={\mathop{\operatorname{effQ}}}_{x_{1},y_{1}}(Q_{x}^{\otimes
N},Q_{y}^{\otimes
N},\widetilde{T})\cdot{\mathop{\operatorname{effQ}}}_{x_{2},y_{2}}(Q_{y}^{\otimes
N},Q_{x}^{\otimes N},\widetilde{T}^{\top}).$

We can calculate that

$\displaystyle{\mathop{\operatorname{effQ}}}_{x_{2},y_{2}}(Q_{y}^{\otimes
N},Q_{x}^{\otimes N},\widetilde{T}^{\top})=$
$\displaystyle~{}\prod_{i,j,u,v}{\mathop{\operatorname{effQ}}}_{u,v}(Q_{y},Q_{x},T^{\top})^{\tau_{2}(i,j,u,v)}=\prod_{i,j,u,v}{\mathop{\operatorname{effQ}}}_{v,u}(Q_{x},Q_{y},T)^{\tau_{2}(i,j,u,v)}$
$\displaystyle=$
$\displaystyle~{}\prod_{i,j,u,v}{\mathop{\operatorname{effQ}}}_{u,v}(Q_{x},Q_{y},T)^{\tau_{1}(j,i,u,v)}=\prod_{u,v}{\mathop{\operatorname{effQ}}}_{u,v}(Q_{x},Q_{y},T)^{\sum_{i,j}\tau_{1}(j,i,u,v)}$
$\displaystyle=$
$\displaystyle~{}{\mathop{\operatorname{effQ}}}_{x_{1},y_{1}}(Q_{x},Q_{y},T)={\mathop{\operatorname{effQ}}}_{\tau},$

where the second step is because
$\mathop{\operatorname{effQ}}_{u,v}(Q_{y},Q_{x},T^{\top})=\mathop{\operatorname{effQ}}_{v,u}(Q_{x},Q_{y},T)$,
the third step is because $\tau_{2}(i,j,u,v)=\tau_{1}(j,i,v,u)$ and switching
$u$ and $v$, and the last step is by definition of
$\mathop{\operatorname{eff}}_{\tau}$ (part 4 of Fact 4.7).

Therefore, the statement holds. ∎

####  4.4.3 Step 3. Detect $(x^{*},y^{*})$ using $S$

To simplify notation, we write the distribution
$\mathcal{D}^{x}_{Q_{x}^{\otimes N}\otimes Q_{y}^{\otimes N}}$ as
$\mathcal{D}^{x}$, omitting the matrix $Q_{x}^{\otimes N}\otimes
Q_{y}^{\otimes N}$ acting on $x$. Similarly, we write
$\mathcal{D}^{y^{*}}_{Q_{y}^{\otimes N}\otimes Q_{x}^{\otimes N}}$ as
$\mathcal{D}^{y}$.

We let $S_{x}:=\\{x\mid\mathcal{D}^{x^{*}}(x)=\mathcal{D}_{\tau}\\}$ and
$S_{y}:=\\{y\mid\mathcal{D}^{y^{*}}(y)=\mathcal{D}_{\tau}\\}$. By Claim 4.12,
$S\subseteq S_{x}\otimes S_{y}$, and also $|S_{x}|=|S_{y}|$ follows by
symmetry.

In line 12, 13 of our Algorithm 2, for each $x_{i}\in[q]^{2N}$ (also $y_{i}$),
we make $c$ copies $i_{1},\ldots,i_{c}$ independently drawn from
$\mathcal{D}^{x_{i}}$, and put $x_{i}$ into the buckets
$X_{i_{1}},\ldots,X_{i_{c}}$. (If two copies turned out to be identical, we
only put $x_{i}$ into that bucket once.) Let $g^{*}$ be the least power of $2$
that is larger than $\frac{n}{q^{2N}\cdot|S_{\tau}|\cdot D_{\tau}}$ (this
number is roughly $\mathop{\operatorname{effQ}}_{\tau}^{2}$; see Eq. (8)).
Since our algorithm iterates over all $g$ which are powers of $2$, there’s an
iteration where $g=g^{*}$. In the remaining analysis, we focus on this case.
Note that

$\displaystyle
c=q^{2N}g^{*}/n\geq\frac{1}{|S_{\tau}|\cdot\mathcal{D}_{\tau}}\geq 1.$ (7)

######  Claim 4.13.

Suppose $c\geq\frac{1}{|S_{\tau}|\cdot\mathcal{D}_{\tau}}$, then with $\geq
1/4$ probability, there’s one copy $x^{\prime}$ of $x^{*}$ and one copy
$y^{\prime}$ of $y^{*}$ such that $(x^{\prime},y^{\prime})\in S$.

###### Proof.

The copies of the planted vector $x^{*}$ are drawn independently according to
$\mathcal{D}^{x^{*}}$. Hence, the number of copies which fall into $S_{x}$
follows a binomial distribution with mean
$c\cdot\mathcal{D}_{\tau}\cdot|S_{x}|\geq 1$. It follows that, with constant
probability, there are at least $c\cdot\mathcal{D}_{\tau}\cdot|S_{x}|$ many
copies of $x^{*}$ which fall into $S_{x}$. For the same reason, there is a
constant probability that $c\cdot\mathcal{D}_{\tau}\cdot|S_{y}|$ many copies
of $y^{*}$ fall into $S_{y}$.

Furthermore, since for all $x\in S_{x},y\in S_{y}$,
$\mathcal{D}^{x^{*}}(x)=\mathcal{D}^{y^{*}}(y)=\mathcal{D}_{\tau}$, it follows
that: conditioned on some particular copies of $x^{*}$ falling into $S_{x}$,
those copies will be independently uniformly random elements of $S_{x}$ (and
similarly for $S_{y}$). Also, since $|S_{x}|=|S_{y}|$ and
$c\cdot\mathcal{D}_{\tau}\cdot|S_{x}|\geq|S_{x}|/\sqrt{|S|}$ (by the choice of
our $c$ and $|S|=|S_{\tau}|^{2}$) and $V_{x}(S),V_{y}(S)\leq|S|^{1.5}$ (Claim
4.12), it follows by Lemma 3.6 that with probability at least $1/4$, there is
a pair of one copy of $x^{*}$ and one copy of $y^{*}$ which falls into $S$. ∎

######  Lemma 4.14.

Given $i,j\in[q]^{2N}$, let $|X_{i}|$ and $|Y_{j}|$ be the number of input
vectors that placed a copy into $X_{i}$ and $Y_{j}$, respectively. Then, over
the randomness of the first $2N$ coordinates of the input vectors and the
process of making random copies,

$\displaystyle\mathbb{E}[|X_{i}|]$
$\displaystyle~{}=g^{*}\cdot\Pi_{l=1}^{N}\partial_{x}(i_{l})\cdot\Pi_{l=N+1}^{2N}\partial_{y}(i_{l}),~{}~{}~{}and$
$\displaystyle\mathbb{E}[|Y_{i}|]$
$\displaystyle~{}=g^{*}\cdot\Pi_{l=1}^{N}\partial_{y}(j_{l})\cdot\Pi_{l=N+1}^{2N}\partial_{x}(j_{l}).$

###### Proof.

For every input vector $x$ other than the planted pair, $x$ is uniformly
sampled from $[q]^{2N}$. For a copy $x^{\prime}$ of $x$ drawn from the
distribution $\mathcal{D}^{x}_{Q_{x}^{\otimes N}\otimes Q_{y}^{\otimes N}}$,
we have

$\displaystyle\Pr[x^{\prime}\in
X_{i}]=\frac{1}{q^{2N}}\Pi_{l=1}^{N}\partial_{x}(i_{l})\cdot\Pi_{l=N+1}^{2N}\partial_{y}(i_{l}).$

By linearity of expectation over all input vectors and all copies, we have

$\displaystyle\mathbb{E}[|X_{i}|]=nc\cdot\Pr[x^{\prime}\in X_{i}].$

Similarly, on the $y$ side, we have

$\displaystyle\mathbb{E}[|Y_{j}|]=\frac{nc}{q^{2N}}\Pi_{l=1}^{N}\partial_{y}(j_{l})\cdot\Pi_{l=N+1}^{2N}\partial_{x}(j_{l}).$

Thus, the claim follows since $g^{*}=\frac{nc}{q^{2N}}$. ∎

The following gives an upper bound on $g^{*}$,

$\displaystyle
g^{*}\leq\frac{2n}{q^{2N}|S_{\tau}|\mathcal{D}_{\tau}}=\frac{n\gamma^{N}}{10(N+1)^{q^{4}}\cdot|S_{\tau}|\mathcal{D}_{\tau}n}\leq\frac{N^{q^{4}}\mathcal{D}_{\tau}|S_{\tau}|{\mathop{\operatorname{effQ}}}_{\tau}^{2}}{10(N+1)^{q^{4}}\cdot|S_{\tau}|\mathcal{D}_{\tau}}={\mathop{\operatorname{effQ}}}_{\tau}^{2}/10,$
(8)

where the second step is by our choice of $N$ from Equation (5) and $c$ from
Equation (7), and the third step is by Lemma 4.8.

####  4.4.4 Step 4. Matrix multiplication

Our vectors currently come from $[q]^{N}$, but we would like to map them to
vectors in $\\{-1,1\\}^{N}$ so that the independent uniformly random vectors
are still independent uniformly random, and the planted pair is correlated. If
$q$ is even, we use the mappings $g$, $h$ from Lemma 4.9. If $q$ is odd, we
first map each bit of vectors from $[q]$ to $[2q]$ by adding a uniform bit in
$\\{0,1\\}$, so that the planted pair still has non-zero correlation, then we
use the mappings $g$, $h$.

As we discussed earlier, we use fresh bits (different from the ones used in
the bucketing process above) for each matrix multiplication. Sample
$q_{k}^{2N}$ coordinates, and apply the mapping $g$ to $x$, and $h$ to $y$,
bit-wise. Here we abuse notation and still write
$x_{i},y_{i}\in\\{-1,1\\}^{q_{k}^{2N}}$ to denote the mapped input vectors
$x_{i},y_{i}$. The result is that the mapped vectors $x_{i}$ and $y_{i}$ are
independently uniformly chosen from $\\{-1,1\\}^{q_{k}^{2N}}$, except the
correlated pair $x^{*},y^{*}$ has

$\langle x^{*},y^{*}\rangle=\Omega(q_{k}^{2N}).$

For each $i\in[q]^{2N}$, create vectors $a_{i},b_{i}\in\mathbb{R}^{m}$ given
by $a_{i}=\sum_{j\in X_{i}}x_{j}$ and $b_{i}=\sum_{j\in Y_{i}}y_{j}$. Let
$s_{a},s_{b}\in\\{-1,1\\}^{q^{2N}}$ be random vectors whose entries are i.i.d.
uniformly sampled from $\\{-1,1\\}$. Form the matrices
$A,B\in\mathbb{R}^{q^{2N}\times m}$ whose rows are $s_{a}[1]\cdot
a_{1},\ldots,s_{a}[q^{2N}]\cdot a_{q^{2N}}$ and $s_{b}[1]\cdot
b_{1},\ldots,s_{b}[q^{2N}]\cdot b_{q^{2N}}$, respectively.

We now apply the tensor $T^{\prime}$ to the matrices $A$ and $B^{\top}$,
resulting in the matrix $C\in\mathbb{R}^{q^{2N}\times q^{2N}}$. By Claim 4.13,
with $\geq 1/4$ probability, one copy of $x^{*}$ and one copy of $y^{*}$ fall
into $S$. Denote the index by $(i,j)\in S$.

Using the same variance-based analysis from Theorem 3.2 and Theorem 3.4, we
have

$\displaystyle\mathbb{E}[C[i,j]]$
$\displaystyle~{}=\Omega(1)\cdot\sum_{k}T^{\prime}(X_{i,k}Y_{j,k}Z_{i,j})$
$\displaystyle\mathrm{var}[C[i,j]]$
$\displaystyle~{}=\sum_{i^{\prime},j^{\prime}k,k^{\prime}}T^{\prime}(X_{i^{\prime},k}Y_{j^{\prime},k^{\prime}}Z_{i,j})^{2}\cdot\mathbb{E}[|X_{i}^{\prime}|]\cdot\mathbb{E}[|Y_{j}^{\prime}|].$

$\displaystyle~{}\frac{\mathbb{E}[C[i,j]]}{\mathrm{var}[C[i,j]]^{1/2}}$
$\displaystyle=$
$\displaystyle~{}\Omega(1)\cdot\frac{\sum_{k}T^{\prime}(X_{i,k}Y_{j,k}Z_{i,j})}{\mathop{\operatorname{effQ}}_{\tau}^{2}\cdot\sqrt{\sum_{i^{\prime},j^{\prime}k,k^{\prime}}T^{\prime}(X_{i^{\prime},k}Y_{j^{\prime},k^{\prime}}Z_{i,j})^{2}\cdot\Pi_{l=1}^{N}\partial_{x}(i^{\prime}_{l})\cdot\Pi_{l=N+1}^{2N}\partial_{y}(i^{\prime}_{l})\cdot\Pi_{l=1}^{N}\partial_{y}(j^{\prime}_{l})\cdot\Pi_{l=N+1}^{2N}\partial_{x}(j^{\prime}_{l})}}$
$\displaystyle=$
$\displaystyle~{}\Omega(1)\cdot\frac{\mathop{\operatorname{effQ}}_{i,j}(Q_{x}^{\otimes
N}\otimes Q_{y}^{\otimes N},Q_{y}^{\otimes N}\otimes Q_{x}^{\otimes
N},T^{\prime})}{\mathop{\operatorname{effQ}}_{\tau}^{2}}$ $\displaystyle=$
$\displaystyle~{}\Omega(1),$

where the first step is by replacing
$\mathbb{E}[|X_{i}^{\prime}|],\mathbb{E}[|Y_{j}^{\prime}|]$ from Lemma 4.14
and Eq. (8), the second step is by definition of
$\mathop{\operatorname{eff}}_{Q}$ (Def.4.1), the third step is because
$\mathop{\operatorname{effQ}}_{\tau}=\mathop{\operatorname{effQ}}_{x,y}(Q_{x}^{\otimes
N},Q_{y}^{\otimes N},T^{\otimes N})$ for any $(x,y)\in S_{\tau}$ from Eq.4.4.2
and the fact that $(i,j)\in S=S_{\tau}\otimes S_{\tau}^{\top}$.

As before, because the expectation exceeds the square root of variance, we can
detect $x^{*}$ and $y^{*}$ by repeatedly running $T^{\prime}$-matrix
multiplication $O(\log n)$ times, which takes total running time
$\tilde{O}(\mathop{\operatorname{rank}}(T^{\prime}))$.

Overall, by repeating $(q^{2N})^{o(1)}$ times, we can boost the success
probability to nearly $1$. Once we can detect if the planted pair ($x^{*}$,
$y^{*}$) exists, we can do binary search to find them with comparably
negligible time overhead.

The exponent $\omega_{P}$ we get is

$\displaystyle\omega_{P}=\frac{\log\left((q^{2N})^{o(1)}\cdot\mathop{\operatorname{rank}}(T)^{2N}\right)}{\log
n}=\frac{\log\left((q^{2N})^{o(1)}\cdot\mathop{\operatorname{rank}}(T)^{2N}\right)}{\log\left(q^{2N}\gamma^{N}N^{-q^{4}}\right)}=\frac{\log\mathop{\operatorname{rank}}(T)}{\log(q\gamma^{1/2})}+o(1),$

where the second step is by (5).

##  5 New Tensor Construction

In this section, we formally give the tensors summarized in Figure 1 from the
introduction. (In Figure Figure 1, the bounds on $\omega_{\ell}$ from each of
these tensors is calculated.) We begin with our new tensor $T_{2112}$.

For any $\varepsilon>0$, define the rank-$5$ tensor $T_{2112}$ as the sum of
the following five rank-1 tensors:

$\displaystyle(\mathsf{X}_{0,0}+\mathsf{X}_{1,0}/\varepsilon+\mathsf{X}_{0,1}/\varepsilon^{3}+\mathsf{X}_{1,1})(\mathsf{Y}_{0,0}/\varepsilon^{3}+\mathsf{Y}_{1,0}+\mathsf{Y}_{0,1}+\mathsf{Y}_{1,1}/\varepsilon)(\varepsilon^{3}\mathsf{Z}_{0,0}+\varepsilon^{4}\mathsf{Z}_{1,0}+\varepsilon^{4}\mathsf{Z}_{0,1}+\varepsilon\mathsf{Z}_{1,1})/4$
$\displaystyle+$
$\displaystyle(\mathsf{X}_{0,0}+\mathsf{X}_{1,0}/\varepsilon-\mathsf{X}_{0,1}/\varepsilon^{3}-\mathsf{X}_{1,1})(\mathsf{Y}_{0,0}/\varepsilon^{3}-\mathsf{Y}_{1,0}-\mathsf{Y}_{0,1}+\mathsf{Y}_{1,1}/\varepsilon)(\varepsilon^{3}\mathsf{Z}_{0,0}+\varepsilon^{4}\mathsf{Z}_{1,0}-\varepsilon^{4}\mathsf{Z}_{0,1}-\varepsilon\mathsf{Z}_{1,1})/4$
$\displaystyle+$
$\displaystyle(\mathsf{X}_{0,0}-\mathsf{X}_{1,0}/\varepsilon-\mathsf{X}_{0,1}/\varepsilon^{3}+\mathsf{X}_{1,1})(\mathsf{Y}_{0,0}/\varepsilon^{3}-\mathsf{Y}_{1,0}+\mathsf{Y}_{0,1}-\mathsf{Y}_{1,1}/\varepsilon)(\varepsilon^{3}\mathsf{Z}_{0,0}-\varepsilon^{4}\mathsf{Z}_{1,0}+\varepsilon^{4}\mathsf{Z}_{0,1}-\varepsilon\mathsf{Z}_{1,1})/4$
$\displaystyle+$
$\displaystyle(\mathsf{X}_{0,0}-\mathsf{X}_{1,0}/\varepsilon+\mathsf{X}_{0,1}/\varepsilon^{3}-\mathsf{X}_{1,1})(\mathsf{Y}_{0,0}/\varepsilon^{3}+\mathsf{Y}_{1,0}-\mathsf{Y}_{0,1}-\mathsf{Y}_{1,1}/\varepsilon)(\varepsilon^{3}\mathsf{Z}_{0,0}-\varepsilon^{4}\mathsf{Z}_{1,0}-\varepsilon^{4}\mathsf{Z}_{0,1}+\varepsilon\mathsf{Z}_{1,1})/4$
$\displaystyle-$
$\displaystyle\mathsf{X}_{0,1}\mathsf{Y}_{0,0}\mathsf{Z}_{1,1}/\varepsilon^{5}$
$\displaystyle=$
$\displaystyle(\mathsf{X}_{0,0}\mathsf{Y}_{0,0}+\mathsf{X}_{0,1}\mathsf{Y}_{1,0}+\varepsilon^{3}\mathsf{X}_{1,1}\mathsf{Y}_{0,1}+\varepsilon\mathsf{X}_{1,0}\mathsf{Y}_{1,1})\mathsf{Z}_{0,0}$
$\displaystyle+$
$\displaystyle(\varepsilon^{4}\mathsf{X}_{0,0}\mathsf{Y}_{0,1}+\mathsf{X}_{0,1}\mathsf{Y}_{1,1}+\varepsilon\mathsf{X}_{1,1}\mathsf{Y}_{0,0}+\varepsilon^{3}\mathsf{X}_{1,0}\mathsf{Y}_{1,0})\mathsf{Z}_{0,1}$
$\displaystyle+$
$\displaystyle(\mathsf{X}_{1,0}\mathsf{Y}_{0,0}+\varepsilon^{4}\mathsf{X}_{1,1}\mathsf{Y}_{1,0}+\varepsilon\mathsf{X}_{0,1}\mathsf{Y}_{0,1}+\varepsilon^{3}\mathsf{X}_{0,0}\mathsf{Y}_{1,1})\mathsf{Z}_{1,0}$
$\displaystyle+$
$\displaystyle(\mathsf{X}_{1,0}\mathsf{Y}_{0,1}+\mathsf{X}_{1,1}\mathsf{Y}_{1,1}+\varepsilon\mathsf{X}_{0,0}\mathsf{Y}_{1,0})\mathsf{Z}_{1,1}.$

(As discussed earlier, one might normally interpret this as a border rank
expression, but here we substitute fixed values of $\varepsilon>0$ and view it
as a rank expression instead.) We can see that for any $\varepsilon>0$, it has
efficacies:

$\mathop{\operatorname{eff}}_{0,0}(T)=\frac{1+1}{\sqrt{1+1+\varepsilon^{6}+\varepsilon^{2}}}=\sqrt{2}-O(\varepsilon^{2}),$
$\mathop{\operatorname{eff}}_{0,1}(T)=\frac{\varepsilon^{4}+1}{\sqrt{\varepsilon^{8}+1+\varepsilon^{2}+\varepsilon^{6}}}=1-O(\varepsilon^{2}),$
$\mathop{\operatorname{eff}}_{1,0}(T)=\frac{1+\varepsilon^{4}}{\sqrt{1+\varepsilon^{8}+\varepsilon^{2}+\varepsilon^{6}}}=1-O(\varepsilon^{2}),$
$\mathop{\operatorname{eff}}_{1,1}(T)=\frac{1+1}{\sqrt{1+1+\varepsilon^{2}}}=\sqrt{2}-O(\varepsilon^{2}).$

Hence,

$\mathop{\operatorname{eff}}(T)=\sqrt{(\sqrt{2}-O(\varepsilon^{2}))^{2}+(1-O(\varepsilon^{2}))^{2}+(1-O(\varepsilon^{2}))^{2}+(\sqrt{2}-O(\varepsilon^{2}))^{2}}=\sqrt{6}-O(\varepsilon^{2}).$

###  5.1 Derivation of $T_{2112}$

Although the rank expression above for $T_{2112}$ suffices for our algorithm,
we give an alternate, fairly simple way to see why $T_{2112}$ has rank $5$;
this is how we first found this tensor. Our rank expression for $T_{2112}$ was
derived by a modification of the structural tensor $T_{(\mathbb{Z}/2)^{2}}$ of
the group $(\mathbb{Z}/2)^{2}$ in the following way. $T_{(\mathbb{Z}/2)^{2}}$
is defined as

$T_{(\mathbb{Z}/2)^{2}}=\sum_{a,b\in(\mathbb{Z}/2)^{2}}\mathsf{X}_{a}\mathsf{Y}_{b}\mathsf{Z}_{a+b},$

and it has rank $4$ since it is the structural tensor of an Abelian group. We
can expand its terms:

$\displaystyle
X_{0,0}Y_{0,0}Z_{0,0}+X_{0,0}Y_{0,1}Z_{0,1}+X_{0,0}Y_{1,0}Z_{1,0}+X_{0,0}Y_{1,1}Z_{1,1}$
$\displaystyle+X_{0,1}Y_{0,0}Z_{0,1}+X_{0,1}Y_{0,1}Z_{0,0}+X_{0,1}Y_{1,0}Z_{1,1}+X_{0,1}Y_{1,1}Z_{1,0}$
$\displaystyle+X_{1,0}Y_{0,0}Z_{1,0}+X_{1,0}Y_{0,1}Z_{1,1}+X_{1,0}Y_{1,0}Z_{0,0}+X_{1,0}Y_{1,1}Z_{0,1}$
$\displaystyle+X_{1,1}Y_{0,0}Z_{1,1}+X_{1,1}Y_{0,1}Z_{1,0}+X_{1,1}Y_{1,0}Z_{0,1}+X_{1,1}Y_{1,1}Z_{0,0}$

First, we rename some variables, swapping the names of
$\mathsf{X}_{0,1}\leftrightarrow\mathsf{X}_{1,1}$ and the names of
$\mathsf{Y}_{1,0}\leftrightarrow\mathsf{Y}_{1,1}$ to yield

$\displaystyle
X_{0,0}Y_{0,0}Z_{0,0}+X_{0,0}Y_{0,1}Z_{0,1}+X_{0,0}Y_{1,1}Z_{1,0}+X_{0,0}Y_{1,0}Z_{1,1}$
$\displaystyle+X_{1,1}Y_{0,0}Z_{0,1}+X_{1,1}Y_{0,1}Z_{0,0}+X_{1,1}Y_{1,1}Z_{1,1}+X_{1,1}Y_{1,0}Z_{1,0}$
$\displaystyle+X_{1,0}Y_{0,0}Z_{1,0}+X_{1,0}Y_{0,1}Z_{1,1}+X_{1,0}Y_{1,1}Z_{0,0}+X_{1,0}Y_{1,0}Z_{0,1}$
$\displaystyle+X_{0,1}Y_{0,0}Z_{1,1}+X_{0,1}Y_{0,1}Z_{1,0}+X_{0,1}Y_{1,1}Z_{0,1}+X_{0,1}Y_{1,0}Z_{0,0}$

Since we just renamed variables, this tensor still has rank 4.

Next, we multiply some variables by powers of $\varepsilon$. We multiply
$X_{1,0}$ by $1/\varepsilon$, multiply $X_{0,1}$ by $1/\varepsilon^{3}$,
multiply $Y_{1,1}$ by $1/\varepsilon$, multiply $Y_{0,0}$ by
$1/\varepsilon^{3}$, multiply $Z_{0,0}$ by $\varepsilon^{3}$, multiply
$Z_{0,1}$ by $\varepsilon^{4}$, multiply $Z_{1,0}$ by $\varepsilon^{4}$, and
multiply $Z_{1,1}$ by $\varepsilon$, to yield

$\displaystyle
X_{0,0}Y_{0,0}Z_{0,0}+\varepsilon^{4}X_{0,0}Y_{0,1}Z_{0,1}+\varepsilon^{3}X_{0,0}Y_{1,1}Z_{1,0}+\varepsilon
X_{0,0}Y_{1,0}Z_{1,1}$ $\displaystyle+\varepsilon
X_{1,1}Y_{0,0}Z_{0,1}+\varepsilon^{3}X_{1,1}Y_{0,1}Z_{0,0}+X_{1,1}Y_{1,1}Z_{1,1}+\varepsilon^{4}X_{1,1}Y_{1,0}Z_{1,0}$
$\displaystyle+X_{1,0}Y_{0,0}Z_{1,0}+X_{1,0}Y_{0,1}Z_{1,1}+\varepsilon
X_{1,0}Y_{1,1}Z_{0,0}+\varepsilon^{3}X_{1,0}Y_{1,0}Z_{0,1}$
$\displaystyle+\varepsilon^{-5}X_{0,1}Y_{0,0}Z_{1,1}+\varepsilon
X_{0,1}Y_{0,1}Z_{1,0}+X_{0,1}Y_{1,1}Z_{0,1}+X_{0,1}Y_{1,0}Z_{0,0}$

Since we just multiplied variables by scalars, this did not change the rank,
so this tensor still has rank $4$. (This is similar to an operation called a
“monomial degeneration” or “toric degeneration” in the literature, although
here we are thinking of $\varepsilon$ as a fixed, small positive value rather
than a formal variable.)

Finally, we delete the term $\varepsilon^{-5}X_{0,1}Y_{0,0}Z_{1,1}$, yielding

$\displaystyle