Lune

FOCS2023Top-tier venue

Generalizations of Matrix Multiplication can solve the Light Bulb Problem

Josh Alman, Hengjie Zhang

Abstract

In the light bulb problem, one is given as input vectors x1,…,xn,y1,…,yn∈{−1,1}dx_{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 (xi∗,yj∗)\left(x_{i^{*}}, y_{j^{*}}\right) which is chosen to have correlation ρ\rho for some constant ρ>0\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 Ω(n2)\Omega\left(n^{2}\right) time, and algorithms based on Locality-Sensitive Hashing approach quadratic time as ρ→0\rho \rightarrow 0. In 2012, G. Valiant gave a breakthrough algorithm running in time O(n(5−ω)/(4−ω))<O(n1.615)O\left(n^{(5-\omega)} /(4-\omega)\right)\lt O\left(n^{1.615}\right), no matter how small ρ>0\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(n2ω/3)<O\left(n^{2 \omega / 3}\right)\lt O(n1.582)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 ρ>0\rho\gt 0. We then focus on tensors for “multiplying“ 2×22 \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(n1.872)O\left(n^{1.872}\right). We introduce a new such low-rank tensor we call T2112T_{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(n1.797)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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. A Refined Laser Method and Faster Matrix MultiplicationJosh Alman, Virginia Vassilevska WilliamsSODA 2021 · 275 citations
  2. Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High DimensionsJosh Alman, Timothy M. Chan, R. Ryan WilliamsSODA 2020 · 9 citations

Related papers

  1. Faster Matrix Multiplication via Asymmetric HashingRan Duan, Hongxun Wu, Renfei ZhouFOCS 2023 · 54 citations
  2. A Subquadratic Time Algorithm for Robust Sparse Mean EstimationAnkit PensiaICML 2024 · 1 citation
  3. Hardness of Low Rank Approximation of Entrywise Transformed Matrix ProductsTamás Sarlós, Xingyou Song, David P. Woodruff, Richard ZhangNeurIPS 2023 · 5 citations
  4. Improving the Leading Constant of Matrix MultiplicationJosh Alman, Hantao YuSODA 2025 · 2 citations
  5. Deterministic Sparse Pattern Matching via the Baur-Strassen TheoremNick FischerSODA 2024 · 2 citations
Dusk over the sea between two cliffs drawn in fine vertical lines