On the Information Capacity of Nearest Neighbor Representations
Kordag Mehmet Kilic Jin Sima Jehoshua Bruck
The $\textit{von 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 $\textit{associative
computation}$ where memory is defined by a set of vectors in $\mathbb{R}^n$
(that we call $\textit{anchors}$), 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 $\textit{Nearest Neighbor (NN) Complexity}$) and
$\textit{(ii)}$ the maximal number of bits representing entries of anchors
(called $\textit{Resolution}$). We study symmetric Boolean functions and
present constructions that have optimal NN complexity and resolution.