Abstract
The Light Bulb Problem is one of the most basic problems in data analysis. One is given as input n vectors in {1,1}^d, which are all independently and uniformly random, except for a planted pair of vectors with inner product at least rho * d for some constant rho > 0. The task is to find the planted pair. The most straightforward algorithm leads to a runtime of Omega(n^2). Algorithms based on techniques like LocalitySensitive Hashing achieve runtimes of n^{2  O(rho)}; as rho gets small, these approach quadratic.
Building on prior work, we give a new algorithm for this problem which runs in time O(n^{1.582} + nd), regardless of how small rho 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 socalled `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(n^{1.582} + nd), improving previous results.
BibTeX  Entry
@InProceedings{alman:OASIcs:2018:10028,
author = {Josh Alman},
title = {{An Illuminating Algorithm for the Light Bulb Problem}},
booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)},
pages = {2:12:11},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770996},
ISSN = {21906807},
year = {2018},
volume = {69},
editor = {Jeremy T. Fineman and Michael Mitzenmacher},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10028},
URN = {urn:nbn:de:0030drops100289},
doi = {10.4230/OASIcs.SOSA.2019.2},
annote = {Keywords: Light Bulb Problem, Polynomial Method, Finding Correlations}
}
Keywords: 

Light Bulb Problem, Polynomial Method, Finding Correlations 
Collection: 

2nd Symposium on Simplicity in Algorithms (SOSA 2019) 
Issue Date: 

2018 
Date of publication: 

08.01.2019 