On the Information Capacity of Nearest Neighbor Representations

The textitvon Neumann Computer Architecture has a distinction between computation and memory. In contrast, the brain has an integrated architecture where computation and memory are indistinguishable. Motivated by the architecture of the brain, we propose a model of textitassociative computation where memory is defined by a set of vectors in ℝn (that we call textitanchors), computation is performed by convergence from an input vector to a nearest neighbor anchor, and the output is a label associated with an anchor. Specifically, in this paper, we study the representation of Boolean functions in the associative computation model, where the inputs are binary vectors and the corresponding outputs are the labels (0 or 1) of the nearest neighbor anchors. The information capacity of a Boolean function in this model is associated with two quantities: textit(i) the number of anchors (called textitNearest Neighbor (NN) Complexity) and textit(ii) the maximal number of bits representing entries of anchors (called textitResolution). We study symmetric Boolean functions and present constructions that have optimal NN complexity and resolution.