4 papers
Recovery Beats Storage: Improved Space for Preprocessed 3SUM
Amir Carmel, Yakov Kosoburd, Robert Krauthgamer
The 3SUM problem asks, given sets of integers, whether there exist and whose sum belongs to . In the preprocessed variant with unknown , one preproc…
Optimal Stable Coresets for Geometric Median via Uniform Sampling
Amir Carmel, Robert Krauthgamer, Nir Petruschka
The geometric median problem asks to find a point in that minimizes the sum of Euclidean distances to an input set. It is a classical problem in computational geomet…
Stable coresets: Unleashing the power of uniform sampling
Amir Carmel, Robert Krauthgamer
Uniform sampling is a highly efficient method for data summarization. However, its effectiveness in producing coresets for clustering problems is not yet well understood, primarily…
Fitting Tree Metrics and Ultrametrics in Data Streams
Amir Carmel, Debarati Das, Evangelos Kipouridis +1
Fitting distances to tree metrics and ultrametrics are two widely used methods in hierarchical clustering, primarily explored within the context of numerical taxonomy. Given a posi…