Description
A coloring of a set of points in a metric space is represented by a colored set of prototypes if the color of each point is the same as the color of the closest prototype. Representing a classification by prototypes is also referred to as a nearest neighbor representation. This kind of representation is much studied in machine learning, and it is also related to case-based reasoning in artificial intelligence.
Given a coloring, what is the smallest number of prototypes needed to represent it? In the talk we consider this problem for two-colorings of the n-dimensional hypercube, which can be viewed as the problem of determining a smallest nearest neighbor representation of a Boolean function. We give upper and lower bounds, and discuss connections to problems in circuit complexity. Several open problems will also be mentioned.
Joint work with Peter Hajnal and Zhihao Liu.