Sanjoy Dasgupta, Charles F. Stevens and Saket Navlakha (2017), “A neural algorithm for a fundamental computing problem”, Science 358(6364): 793–796 — doi:10.1126/science.aam9868
Key takeaways
Unread. From the result as it is standardly stated, to be checked against the text.
- Three steps. Projection neuron responses are mean-centred, then sent by a sparse binary random matrix (each Kenyon cell samples about six glomeruli) into a space about 40 times larger, then sparsified by winner-take-all inhibition to the top 5% of Kenyon cells.
- It expands rather than reduces. Unlike the Johnson–Lindenstrauss setting, the random projection goes up in dimension, and sparsification does the work that dimension reduction does in standard LSH.
- A similarity-preserving hash. Similar odours get overlapping tags. On SIFT, GloVe and MNIST nearest-neighbour search the fly’s scheme beats random-projection LSH at the same tag length.
Standing in the record
Filed on 2026-10-14 for QUESTION-120. The record mentions random projections into the mushroom body twice in passing (NOTE-670, NOTE-165), and neither note cites this paper. This is the paper that makes the circuit an algorithm. Like the neuron view of sparse distributed memory, it expands and then thresholds, though SDM’s addresses are dense ±1 and the fly’s projection is a sparse {0, 1} matrix, outside Achlioptas’s ensembles (NOTE-926; NOTE-242, NOTE-779). The hashing it is measured against is Indyk and Motwani’s locality-sensitive hashing (LIT-1106), whose guarantee the record holds as THEORY-388: query cost n^ρ with ρ = ln(1/p₁)/ln(1/p₂). Read in those terms, the fly’s tag is a hash family, and the guarantee the question wants for it would be its collision probabilities p₁ and p₂. That framing is the record’s, not the paper’s, until the paper is read.
neuroscience comes first because the subject is a circuit. databases
and information-retrieval are for the nearest-neighbour search it is
evaluated on, tagged as the record tags Indyk and Motwani
(ADR-045).