Mathematics Computer Science Seminar
Gyorgy Turan
UIC
Nearest neighbor representations of Boolean functions
Abstract: 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.
Monday March 12, 2018 at 3:00 PM in SEO 427