Mathematical Sciences Department
Discrete Math Seminar
Mason DiCicco, WPI
Monday, September 18, 2023
3:00 pm - 3:50 pm
Unity Hall 405
Title: Intro to nearest neighbor complexity
Abstract: A nearest neighbor (NN) instance is a collection of positive and negative points, or anchors. Given a query point x, we classify it as positive if its nearest neighbor (among all anchors) is positive. The key question of NN complexity is: How many anchors are required to represent a given function? This question was (to my knowledge) asked for the first time in the 2022 paper of Hajnal, Liu, and Turan, Nearest neighbor representations of Boolean functions. In this talk I will cover the main points from this paper and discuss some open problems.