Document Open Access Logo

An Illuminating Algorithm for the Light Bulb Problem

Author Josh Alman

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.2.pdf
  • Filesize: 410 kB
  • 11 pages

Document Identifiers

Author Details

Josh Alman

Cite As Get BibTex

Josh Alman. An Illuminating Algorithm for the Light Bulb Problem. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 2:1-2:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.2

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 Locality-Sensitive 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 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(n^{1.582} + nd), improving previous results.

Subject Classification

Keywords
  • Light Bulb Problem
  • Polynomial Method
  • Finding Correlations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Josh Alman, Timothy M Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In FOCS, 2016. Google Scholar
  2. Josh Alman and Ryan Williams. Probabilistic polynomials and hamming nearest neighbors. In FOCS, 2015. Google Scholar
  3. Moses S Charikar. Similarity estimation techniques from rounding algorithms. In STOC, 2002. Google Scholar
  4. Lijie Chen. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. In CCC, 2018. Google Scholar
  5. Moshe Dubiner. Bucketing coding and information theory for the statistical high-dimensional nearest-neighbor problem. IEEE Transactions on Information Theory, 56(8):4166-4179, 2010. Google Scholar
  6. Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami. On agnostic learning of parities, monomials, and halfspaces. SIAM Journal on Computing, 39(2):606-645, 2009. Google Scholar
  7. Oded Goldreich and Avi Wigderson. Derandomization that is rarely wrong from short advice that is typically good. Lecture notes in computer science, 2483:209-223, 2002. Google Scholar
  8. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC, 1998. Google Scholar
  9. Matti Karppa, Petteri Kaski, and Jukka Kohonen. A faster subquadratic algorithm for finding outlier correlations. In SODA, 2016. Google Scholar
  10. Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig Ó Catháin. Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. In ESA, 2016. Google Scholar
  11. François Le Gall. Powers of tensors and fast matrix multiplication. In ISSAC, 2014. Google Scholar
  12. Shachar Lovett. Computing Polynomials with Few Multiplications. Theory of Computing, 7(1):185-188, 2011. Google Scholar
  13. Jonathan Marchini, Peter Donnelly, and Lon R Cardon. Genome-wide strategies for detecting multiple loci that influence complex diseases. Nature genetics, 37(4):413, 2005. Google Scholar
  14. Ramamohan Paturi, Sanguthevar Rajasekaran, and John Reif. The light bulb problem. Information and Computation, 117(2):187-192, 1995. Google Scholar
  15. Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of mathematics, pages 157-187, 2002. Google Scholar
  16. Volker Strassen. Gaussian elimination is not optimal. Numerische mathematik, 13(4):354-356, 1969. Google Scholar
  17. Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. Journal of the ACM, 62(2):13, 2015. Google Scholar
  18. Leslie G Valiant. Functionality in Neural Nets. In AAAI, 1988. Google Scholar
  19. Xiang Wan, Can Yang, Qiang Yang, Hong Xue, Nelson LS Tang, and Weichuan Yu. Detecting two-locus associations allowing for interactions in genome-wide association studies. Bioinformatics, 26(20):2517-2525, 2010. Google Scholar
  20. R Ryan Williams. Natural proofs versus derandomization. SIAM Journal on Computing, 45(2):497-529, 2016. Google Scholar
  21. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In STOC, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact