Demo Data from EDBT 2026 / reviewers in the wild / expert
Rachel Yuan
dblp:345/1582
· DBLP profile ↗
1ranked-venue papers
0as first author
1since 2021 · last 2023
—ORCID · unresolved
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 1 · 1 since 2021
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Databases, data mining, and information retrieval
1 paper |
Data mining · 100% | |
| Theoretical computer science
1 paper |
Computational complexity · 100% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Data mining
clustering |
0.7 | 1 | 2023 | The Price of Explainability for Clustering · FOCS 2023 |
Data mining › clustering
interpretable clustering |
0.7 | 1 | 2023 | The Price of Explainability for Clustering · FOCS 2023 |
Data mining › clustering › center-based clustering
k-median clustering |
0.7 | 1 | 2023 | The Price of Explainability for Clustering · FOCS 2023 |
Computational complexity
hardness of approximation |
0.2 | 1 | 2023 | The Price of Explainability for Clustering · FOCS 2023 |
Methods — techniques the papers use, named apart from their topics
random thresholds algorithm · 1.3lower bound construction · 1.3
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2023 | The Price of Explainability for ClusteringabstractGiven a set of points in d-dimensional space, an explainable clustering is one where the clusters are specified by a tree of axis-aligned threshold cuts. Dasgupta et al. (ICML 2020) posed the question of the price of explainability: the worst-case ratio between the cost of the best explainable clusterings to that of the best clusterings.We show that the price of explainability for k medians is at most $1+H_{k-1}$; in fact, we show that the popular Random Thresholds algorithm has exactly this price of explainability, matching the known lower bound constructions. We complement our tight analysis of this particular algorithm by constructing instances where the price of explainability (using any algorithm) is at least $(1-o(1)) \ln k$, showing that our result is best possible, up to lower-order terms. We also improve the price of explainability for the k-means problem to $O(k \ln \ln k)$ from the previous $O(k \ln k)$, considerably closing the gap to the lower bounds of $\Omega(k)$. Finally, we study the algorithmic question of finding the best explainable clustering: We show that explainable k medians and k-means cannot be approximated better than $O(\ln k)$, under standard complexity-theoretic conjectures. This essentially settles the approximability of explainable k-medians and leaves open the intriguing possibility to get significantly better approximation algorithms for k-means than its price of explainability. Anupam Gupta 0001, Madhusudhan Reddy Pittu, Ola Svensson, Rachel Yuan |
FOCS | 4 |