# Nearest Neighbor Representations of Neurons

arXiv: https://arxiv.org/abs/2402.08748 · HTML: https://mlsanity.com/paper/2402.08748/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 17 references that are in the map.
- First posted on arXiv 13 Feb 2024.

## Builds on (most cited first, 2 of 2)

- [On the Information Capacity of Nearest Neighbor Representations](https://mlsanity.com/paper/2305.05808/) (2023)
- [On Algebraic Constructions of Neural Networks with Small Weights](https://mlsanity.com/paper/2205.08032/) (2022)

## Abstract (arXiv)

The Nearest Neighbor (NN) Representation is an emerging computational model that is inspired by the brain. We study the complexity of representing a neuron (threshold function) using the NN representations. It is known that two anchors (the points to which NN is computed) are sufficient for a NN representation of a threshold function, however, the resolution (the maximum number of bits required for the entries of an anchor) is O(nlogn). In this work, the trade-off between the number of anchors and the resolution of a NN representation of threshold functions is investigated. We prove that the well-known threshold functions EQUALITY, COMPARISON, and ODD-MAX-BIT, which require 2 or 3 anchors and resolution of O(n), can be represented by polynomially large number of anchors in n and O(logn) resolution. We conjecture that for all threshold functions, there are NN representations with polynomially large size and logarithmic resolution in n.