Mathematics Project Abstract
THE NEAREST-NEIGHBOR REPRESENTATION OF BOOLEAN FUNCTIONS
Presenter:
Zhihao Liu, Illinois Mathematics and Science Academy, 1500 West Sullivan Road, Aurora, IL 60506; zhliu@imsa.edu
Mentor:
Gyorgy Turan, University of Illinois at Chicago, 851 S. Morgan Street, Chicago, IL 60607-7045
Abstract:
The nearest-neighbor representation of data has many applications in medical diagnosis, pattern recognition, and artificial intelligence. We consider this representation for Boolean functions. The complexity of a function is measured by the minimum number of prototypes required in its representation. Previously we found that almost all functions have an exponential lower bound, and we proved a linear lower bound for a specific function. We also proved upper bounds. Now we extend our previous results by proving lower bounds for the k-nearest neighbor representation, and by proving a lower bound for the parity function.