An Illuminating Algorithm for the Light Bulb Problem

Gaussian elimination is not optimal

Volker Strassen · 1969

Earlier work this paper cites.

Functionality in neural nets

Leslie G Valiant · 1988

Earlier work this paper cites.

The light bulb problem

Ramamohan Paturi, Sanguthevar Rajasekaran, and John Reif · 1995

Earlier work this paper cites.

Approximate nearest neighbors: towards removing the curse of dimensionality

Piotr Indyk and Rajeev Motwani · 1998

Earlier work this paper cites.

Similarity estimation techniques from rounding algorithms

Moses S Charikar · 2002

Earlier work this paper cites.

Derandomization that is rarely wrong from short advice that is typically good

Oded Goldreich and Avi Wigderson · 2002

Earlier work this paper cites.

Entropy waves, the zig-zag graph product, and new constant-degree expanders

Omer Reingold, Salil Vadhan, and Avi Wigderson · 2002

Earlier work this paper cites.

Genome-wide strategies for detecting multiple loci that influence complex diseases

Jonathan Marchini, Peter Donnelly, and Lon R Cardon · 2005

Cited alongside, same era.

On agnostic learning of parities, monomials, and halfspaces

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Kumar Ponnuswami · 2009

Cited alongside, same era.

Bucketing coding and information theory for the statistical high-dimensional nearest-neighbor problem

Moshe Dubiner · 2010

Cited alongside, same era.

Detecting two-locus associations allowing for interactions in genome-wide association studies

Original

Xiang Wan, Can Yang, Qiang Yang, Hong Xue, Nelson LS Tang, and Weichuan Yu · 2010

Cited alongside, same era.

Computing polynomials with few multiplications

Shachar Lovett · 2011

Cited alongside, same era.

Probabilistic polynomials and hamming nearest neighbors

Josh Alman and Ryan Williams · 2015

Later among the works it cites.

Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem

Gregory Valiant · 2015

Later among the works it cites.

Polynomial representations of threshold functions and algorithmic applications

Josh Alman, Timothy M Chan, and Ryan Williams · 2016

Later among the works it cites.

A faster subquadratic algorithm for finding outlier correlations

Matti Karppa, Petteri Kaski, and Jukka Kohonen · 2016

Later among the works it cites.

Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time

Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig Ó Catháin · 2016

Later among the works it cites.

Natural proofs versus derandomization