An illuminating algorithm for the light bulb problem

DOI10.4230/OASICS.SOSA.2019.2MaRDI QIDQ6593557zbMATH OpenFDO

Authors Josh Alman

Publication date 26 August 2024

Full work available at URL https://doi.org/10.4230/OASICS.SOSA.2019.2

zbMATH Keywords

polynomial methodlight bulb problemfinding correlations

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Recommendations

• A new algorithm for finding closest pair of vectors (extended abstract)
• A new coding-based algorithm for finding closest pair of vectors
• A Faster Subquadratic Algorithm for Finding Outlier Correlations
• A faster subquadratic algorithm for finding outlier correlations
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem

Cited in

(2)

• A non-trivial algorithm enumerating relevant features over finite fields
• Counting short vector pairs by inner product and relations to the permanent

This page was built for publication: An illuminating algorithm for the light bulb problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6593557)