Nearest Neighbor Complexity and Boolean Circuits

Mason DiCicco, Vladimir Podolskii, Daniel Reichman

A nearest neighbor representation of a Boolean function $f$ is a set of vectors (anchors) labeled by $0$ or $1$ such that $f(\vec{x})=1$ if and only if the closest anchor to $\ve…