# An Illuminating Algorithm for the Light Bulb Problem

arXiv: https://arxiv.org/abs/1810.06740 · HTML: https://mlsanity.com/paper/1810.06740/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2018.

## Built on by (most cited first, 3 of 3)

- [A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation](https://mlsanity.com/paper/2403.04726/) (2024)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [New Statistical and Computational Results for Learning Junta Distributions](https://mlsanity.com/paper/2505.05819/) (2025)

## Abstract (arXiv)

The Light Bulb Problem is one of the most basic problems in data analysis. One is given as input n vectors in -1,1d, which are all independently and uniformly random, except for a planted pair of vectors with inner product at least ρ · d for some constant ρ > 0. The task is to find the planted pair. The most straightforward algorithm leads to a runtime of Omega(n2). Algorithms based on techniques like Locality-Sensitive Hashing achieve runtimes of n2 - O(ρ); as ρ gets small, these approach quadratic. Building on prior work, we give a new algorithm for this problem which runs in time O(n1.582 + nd), regardless of how small ρ is. This matches the best known runtime due to Karppa et al. Our algorithm combines techniques from previous work on the Light Bulb Problem with the so-called `polynomial method in algorithm design,' and has a simpler analysis than previous work. Our algorithm is also easily derandomized, leading to a deterministic algorithm for the Light Bulb Problem with the same runtime of O(n1.582 + nd), improving previous results.