4 papers
Can We Break Fine-Grained and NP-Hardness Barriers if We've Seen the Graph Before? The Isomorphic-Priors Model
Dani Dorfmann, Dani Dorfman, Simon Döring +5
If we run a heavy-duty computation on prior data, can we avoid repeated computation for similar future inputs? Inspired by this question, we introduce a new computational model for…
A Broader View on Clustering under Cluster-Aware Norm Objectives
Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase
We revisit the -clustering problem that we introduced in a recent work [SODA'25], and which subsumes fundamental clustering problems such as -Center, -Median, Min-Sum…
Sublinear Data Structures for Nearest Neighbor in Ultra High Dimensions
Martin G. Herold, Danupon Nanongkai, Joachim Spoerhase +2
Geometric data structures have been extensively studied in the regime where the dimension is much smaller than the number of input points. But in many scenarios in Machine Learning…
Clustering to Minimize Cluster-Aware Norm Objectives
Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase
We initiate the study of the following general clustering problem. We seek to partition a given set of data points into clusters by finding a set of centers and ass…