• Explore
    • Contact Us
  • Faculty
  • Research
    • Research Areas
    • Research Centers
  • Graduate Degrees
    • Computer Science Programs
    • Current Graduate Students
  • Undergraduate Degrees
  • News & Events
    • News
    • Seminar Series
    • Distinguished Lecture Series
    • Research Showcase
  • Apply Now
    • Undergraduate Admissions
    • Graduate Admissions
    • Faculty Candidates

David Eppstein Receives 2022 SIAM Best Paper Award

October 21, 2021

A paper by Chancellor’s Professor of Computer Science David Eppstein, “Finding Relevant Points for Nearest-Neighbor Classification,” has won the best paper award of the 2022 SIAM Symposium on Simplicity in Algorithms (SOSA22), to be held in a hybrid online and in-person format in Virginia in January 2022, jointly with several other SIAM conferences.

The Symposium on Simplicity in Algorithms is an annual conference, established in 2018 and sponsored by the Society for Industrial and Applied Mathematics (SIAM), “dedicated to advancing algorithms research by promoting simplicity and elegance in the design and analysis of algorithms.”

Eppstein’s paper concerns nearest-neighbor classification, a widely used method for predicting the properties of data points using a “training set” of points whose properties are known, by predicting that each new point will behave the same as its closest neighbor in the training set. The paper describes a new polynomial-time algorithm for simplifying the training set, by eliminating points that do not contribute to the boundary between regions of space with different predictions. In keeping with the focus of the conference, the new algorithm is based on a simple combination of two subroutines, for minimum spanning trees and convex hull vertices, both of which in turn have simple known algorithms.

A preprint version of the paper is available online.  

« ICSSC Hosts Annual WebJam Competition to Teach Web Development
2020 ACM Thacker Breakthrough in Computing Award Awarded to Professor Michael Franz »

Latest news

  • Identifying the Building Blocks of Attention in Deep Learning March 21, 2023
  • Faculty Spotlight: Jennifer Wong-Ma and the Power of Community March 20, 2023
  • Computer Science Ph.D. Candidate Takami Sato Named Public Impact Fellow March 14, 2023
  • Irani Builds New Collaborations as Associate Director of the Simons Institute March 6, 2023
  • UC Irvine Partners With Linux Foundation to Welcome New Open Source Projects from Peraton Labs to Scale 5G Security March 3, 2023
  • © 2023 UC Regents
  • Feedback
  • Privacy Policy