Generalizations of Matrix Multiplication can solve the Light Bulb Problem

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 $\left(x_{i^{*}}, y_{j^{*}}\right)$ which is chosen to have correlation $\rho$ for some constant $\rho\gt 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\left(n^{2}\right)$ time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as $\rho \rightarrow 0$. In 2012, G. Valiant gave a breakthrough algorithm running in time $O\left(n^{(5-\omega)} /(4-\omega)\right)\lt O\left(n^{1.615}\right)$, no matter how small $\rho\gt 0$ is, by making use of fast matrix multiplication. This was subsequently refined by Karppa, Kaski, and Kohonen in 2016 to running time $O\left(n^{2 \omega / 3}\right)\lt$ $O\left(n^{1.582}\right)$, 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\gt 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\left(n^{1.872}\right)$. 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\left(n^{1.797}\right)$. We also explain why we are optimistic that this approach could yield asymptotically faster algorithms for the light bulb problem.