Nearest Neighbor Representations of Neural Circuits

2024/02/13 by Kordag Mehmet Kilic, Kilic, Kordag Mehmet, Jin Sima +3
Computer Science · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (cs.LG) #Machine Learning and Algorithms #Neural Networks and Applications #Neural and Evolutionary Computing (cs.NE)

paper · pdf · doi:10.48550/arxiv.2402.08751

openalex publication_date 2024/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Neural networks successfully capture the computational power of the human brain for many tasks. Similarly inspired by the brain architecture, Nearest Neighbor (NN) representations is a novel approach of computation. We establish a firmer correspondence between NN representations and neural networks. Although it was known how to represent a single neuron using NN representations, there were no results even for small depth neural networks. Specifically, for depth-2 threshold circuits, we provide explicit constructions for their NN representation with an explicit bound on the number of bits to represent it. Example functions include NN representations of convex polytopes (AND of threshold gates), IP2, OR of threshold gates, and linear or exact decision lists.

Related

• Nearest Neighbor Representations of Neurons
• Neural Network Processing Neural Networks: An efficient way to learn higher order functions
• Graph Neural Networks and Arithmetic Circuits
• Neural Networks are Decision Trees
• On the Information Capacity of Nearest Neighbor Representations