| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | January 24, 2023 |
| Latest Amendment Date: | March 12, 2025 |
| Award Number: | 2236669 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Karl Wimmer
kwimmer@nsf.gov (703)292-2095 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | May 1, 2023 |
| End Date: | April 30, 2028 (Estimated) |
| Total Intended Award Amount: | $650,000.00 |
| Total Awarded Amount to Date: | $412,632.00 |
| Funds Obligated to Date: |
FY 2025 = $139,677.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1109 GEDDES AVE STE 3300 ANN ARBOR MI US 48109-1015 (734)763-6438 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
503 THOMPSON ST ANN ARBOR MI US 48109-1340 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01002526DB NSF RESEARCH & RELATED ACTIVIT 01002627DB NSF RESEARCH & RELATED ACTIVIT 01002728DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Clustering is the task of grouping given objects so that similar objects are in the same cluster and different objects are in different clusters. It is one of the most basic tasks in unsupervised machine learning, and clustering algorithms are run numerous times each day across every field dealing with data. This research aims to develop efficient clustering algorithms with improved performance guarantees and study the limitations of efficient algorithms. These goals will be achieved by creating algorithmic techniques that advance the state-of-the-art and building new connections between various fields of computer science and mathematics, including optimization, complexity theory, geometry, combinatorics, and analysis. The outcome of this project will be integrated into various courses in data science and approximation algorithms at both undergraduate and graduate levels. The education plan also includes training graduate students and broadening the participation of undergraduate students in theoretical computer science.
The project is centered around two main directions, one for algorithms and one for hardness. The first algorithmic direction is to revisit the study of local search, a discrete analog of gradient descent. While the standard local search has been well studied, new types of local search algorithms incorporating convex optimization methods or Euclidean geometry were recently proposed. Understanding the power of these local search algorithms seems to require a new global analysis. Secondly, the investigator will study a recently introduced complexity hypothesis called the Johnson Coverage Hypothesis which, if true, will result in significantly better hardness results for clustering in Euclidean spaces. It already reveals exciting connections to other areas of mathematics and theoretical computer science that are worth further investigation.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
Please report errors in award information by writing to: awardsearch@nsf.gov.
