Pith. sign in

REVIEW 3 major objections 5 minor 77 references

Learning-Augmented Hierarchical Clustering

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A splitting oracle that answers 90% of triplet queries correctly converts hierarchical clustering's approximation hard-walls into polynomial-time algorithms.

desk verdict A valuable partial-tree framework and solid Dasgupta results, but the Moseley-Wang (1-o(1)) guarantee rests on a lemma whose inductive step does not go through as written. read the letter →

arxiv 2506.05495 v1 pith:NZEAY7GS submitted 2025-06-05 cs.DS cs.LG

Vladimir Braverman , Jon C. Ergun , Chen Wang , Samson Zhou This is my paper
classification cs.DScs.LG MSC 68W2568Q1768W20
keywords hierarchicalclusteringsplittingoracleDasguptaobjectiveMoseley-Wanglearning-augmentedalgorithmspartialtreesapproximationSmallSetExpansionhardness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Hierarchical clustering has two widely studied objectives—Dasgupta's cost and Moseley-Wang's revenue—for which, without auxiliary data, polynomial-time algorithms cannot achieve constant-factor or near-optimal guarantees under plausible complexity assumptions. This paper argues that a noisy splitting oracle changes the picture: a query on three vertices returns which one splits away from the other two in an optimal tree, correctly with probability 9/10 and adversarially when wrong. With such an oracle, the paper constructs partial hierarchical clustering trees that mirror the optimal tree down to clusters of O(log n) vertices, then fills in the small clusters with known sparsest-cut or arbitrary methods. The resulting guarantees are an O(1)-approximation to Dasgupta's objective in polynomial time and a (1-o(1))-approximation to Moseley-Wang's objective in near-linear time. A sympathetic reader should care because, if the construction is sound, the oracle's local advice is a way around the Small Set Expansion hardness barrier for both objectives.

What carries the argument

The load-bearing mechanism is the partial hierarchical clustering tree, a binary dendrogram whose leaves may be 'super-vertices'—sets of at most 50000 log n vertices whose internal arrangement is initially unresolved. A strongly consistent partial tree collapses exactly the maximal subtrees of T* that are small; a weakly consistent partial tree allows a contractible region whose connection to the rest of the tree has out-degree at most two. The algorithms build these partial trees using the small-tree splitting order, which lists vertices by recursively taking the smaller side of each split in the restricted optimal tree, plus majority-count testers (counterpart and predecessor tests) run against sampled or horizon vertex sets. Concentration inequalities turn the 90%-accurate triplets into reliable signals, and a horizon set keeps the weak-consistency invariant stable when the current vertex set encounters orphaned vertices. The partial trees do the heavy lifting: they reduce the problem, for both objectives, to resolving clusters of logarithmic size, at which point brute-force or approximate sparsest cuts and even arbitrary partitions become affordable.

What would settle it

For a graph whose optimal tree is known—for instance two equal-size cliques joined by a single edge—simulate the oracle at p=9/10 with errors adversarially biased to flip the smaller-side signal, and run the strong partial-tree split on this instance; a systematic failure to recover the true root cut with probability at least 1-1/$n^{2}$ would falsify the core lemma behind Theorem 1.

Watch

Extended reading notes

Core claim

The central claim is that a single natural oracle model suffices to bypass the approximation barriers for hierarchical clustering. The paper establishes that with an oracle O that, on a triplet (u,v,w), reports the vertex that splits away from the other two in an optimal tree T*, correctly with probability 9/10 and independently per triplet, there is an algorithm computing a tree T with cost_G(T) <= O(1) * OPT_Das(G) in polynomial time and O($n^{3}$) queries (Theorem 1), and an algorithm computing T with rev_G(T) >= (1-o(1)) * OPT_MW(G) in O($n^{2}$ polylog n) time and O($n^{2}$) queries (Theorem 3). The engine is a pair of data structures: partial HC trees strongly or weakly consistent with T*, constructible directly from the oracle and the vertex set without reading the edge weights, in O($n^{3}$ log n) time with O($n^{3}$) queries (Theorem 5) and in O($n^{2}$ polylog n) time with O($n^{2}$) queries (Theorem 6). If true, these results show that a triplet oracle correct at rate 9/10 circumvents the Small Set Expansion-based inapproximability for both the minimization and the maximization formulation.

Load-bearing premise

The argument assumes the splitting oracle is correct with probability 9/10 on each distinct triplet, that incorrect answers are adversarial but fixed per triplet, and that 'the vertex that splits away in the optimal tree' names a single well-defined ground truth—which requires a fixed choice among ties when several optimal trees exist.

Editorial extensions

If this is right

  • If Theorem 1 is right, the splitting oracle yields a polynomial-time constant-factor approximation for Dasgupta's objective, a problem for which no constant-factor polynomial-time algorithm exists without the oracle under the Small Set Expansion hypothesis.
  • If Theorem 3 is right, the same oracle yields a (1-o(1))-approximation for Moseley-Wang's objective in near-linear time, also escaping the SSE-based inapproximability for that objective.
  • The strong partial tree construction supports a single-pass semi-streaming algorithm computing an O(1)-approximation to Dasgupta's objective in polynomial time using O(n log^3 n) bits of space (Theorem 8).
  • The weak partial tree construction yields a PRAM algorithm with O(n^2 polylog n) work and polylogarithmic depth achieving (1-o(1))-approximation to Moseley-Wang's objective (Theorem 9).
  • If the oracle is instead derived from an alpha-approximate tree, the Dasgupta-side guarantees degrade by an extra O(alpha) factor, while the Moseley-Wang argument is not shown to survive this weakening.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because partial HC trees are built only from the oracle and the vertex set, the same constructed tree could be reused for many different weightings of the same vertex set; the paper's streaming algorithm already exploits part of this separation, and offline re-weighting is a natural extension.
  • The objective-free construction suggests the partial-tree machinery should transfer to other hierarchical-clustering objectives beyond Dasgupta and Moseley-Wang; the proofs would only need the relevant cost or revenue to be controllable by the structure of super-vertices.
  • A practical pipeline implied by the paper's framework is to learn a triplet classifier on labeled instances using the PAC analysis of Appendix C, then run the near-linear Moseley-Wang algorithm; this is an end-to-end recipe the paper does not itself evaluate experimentally.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces a learning-augmented model for hierarchical clustering in which an oracle, given a triple of vertices, returns (with probability 9/10, adversarially on error) the vertex that splits away from the other two in an optimal tree T*. It defines partial hierarchical clustering trees that are strongly or weakly consistent with T*, gives constructions of these structures from the oracle, and uses them to obtain a polynomial-time O(1)-approximation for Dasgupta's objective (Theorem 1), an O(n^3 log n)-time O(sqrt(log log n))-approximation (Theorem 2), a near-linear O(n^2 polylog n)-time (1-o(1))-approximation for the Moseley-Wang objective (Theorem 3), and streaming/PRAM extensions (Theorems 4, 8, 9). The core claimed contribution is that a noisy triplet oracle can bypass known SSE-hardness barriers for both HC objectives.

Significance. If the results are correct, the paper makes a strong conceptual point: a natural triplet oracle, even with constant adversarial noise, can circumvent the strong approximation barriers for hierarchical clustering. The partial HC tree framework is a useful and potentially reusable abstraction, and the paper contains substantial technical machinery, including exchange arguments for optimal-tree structure and Chernoff-based concentration analyses. The algorithms are parameter-free in the sense that they do not fit parameters to the input, and the oracle is an external input rather than an assumed target of the algorithm. However, two load-bearing proof points are not established as written: Lemma 6.4, which underlies the (1-o(1)) Moseley-Wang guarantee, and Lemma 10.5, which underlies the O(log^3 n) recursion depth of the weak partial tree construction. These gaps affect the main theorems of the paper and need to be repaired before the claims can be accepted.

major comments (3)
  1. [§6, Lemma 6.4 (inductive step)] The inductive step asserts the inequality 1/2 * w(E1)/|X| <= (w(E1) - (50000 log n + 1) w(E3))/|X| and justifies it by the statement 'w(E3) = O(log^2 n / n) * w(E2)'. This requires a lower bound of the form w(E1) = Omega(log n * w(E3)), equivalently w(E1) = Omega(log n / (n - o(n)) * w(E2)). The displayed induction hypothesis and Claim 6.2 provide only upper bounds of the form w(E1) <= C log n * w(E2) / (n - 50000(log^2 n + log n)), which are the wrong direction. The claimed first inequality therefore does not follow. Since Lemma 6.4 is the only mechanism that discards the low-revenue edges Elow in the proof of Theorem 3, the central (1-o(1)) Moseley-Wang approximation is not established as written.
  2. [§6, Lemma 6.4 (cardinality bound)] The proof bounds |Elow| <= 50000(log^2 n + log n) with no counting argument. Condition (a) alone is insufficient: in a balanced optimal tree, all pairs crossing the root have zero non-leaves, so there can be Theta(n^2) such edges. The proof says that the inclusion relationship in (b) restricts the count, but for an arbitrary weakly consistent partial tree I the number of super-vertex pairs satisfying the inclusion and size conditions is not quantified anywhere. A valid counting argument for |Elow| is needed for the claimed O(log^4 n / n) revenue bound, and none is supplied.
  3. [§10.1, Lemma 10.5 (Item 4(b)ii)] The high-probability proof of the size upper bound is incorrect. With E[X] <= 1/(20 log n), the displayed equality Pr(X >= 1) = Pr(X >= 50 log n * E[X]) is false because 50 log n * E[X] = 2.5, not 1. The actual probability that 500 log n uniform samples hit a set of relative size 1/(10000 log^2 n) is about 1/(20 log n), which is not o(1). Thus Lemma 10.1's claim that |T* cap V| <= (1 - 1/(10000 log^2 n)) * n holds with high probability is not established. This upper bound is used in the O(log^3 n) depth argument in §10.3, so Theorem 6 and the near-linear time claim of Theorem 3 are affected. The fix may be to increase the sample size to O(log^3 n); the runtime analysis would then need to be redone, though it may still be O(n^2 polylog n).
minor comments (5)
  1. [§3.2, Definition 2] The oracle and all later consistency definitions refer to 'the optimal tree T*', but T* is not unique in general. Please fix an arbitrary optimal tree with an explicit deterministic tie-breaking rule as the ground truth; otherwise the split-away vertex and the guarantees of Theorems 5 and 6 are not well-defined.
  2. [§5.2, §5.3] There are several arithmetic/typographical slips: Lemma 5.4's derivation of O(n^50002) should be O(n^50001 log n) = O(n^50002) only after bounding log n by n; the proof of Lemma 5.6 writes O(n * log^3 n) = O(n^3 log n), which is not a valid equality; and the final paragraph of §5.3 says 'O(n^4) time efficiency' instead of 'O(n^3 log n)'.
  3. [§3.3, Problem 2] The sentence defining OPTMW says 'under Dasgupta's cost'; it should say 'under the Moseley-Wang objective'.
  4. [§4.1, Definition 3 and §6, Lemma 6.4] Definition 3 bounds super-vertex size by 50000 log n, but the proof of Lemma 6.4 uses |X| <= 5000 log n. The constants should be reconciled.
  5. [Figures 2 and 3] The figure captions contain un-filled placeholders such as 'Contains at most vertices'; the O(log n) bound should be filled in.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the splitting oracle is an external model input, and the approximation guarantees are proved against the same optimal tree via structural and exchange arguments, not by construction.

full rationale

The paper's central claims are not circular under the stated rubric. The splitting oracle in Definition 2 is part of the input model: it returns (possibly noisy) triplet split information about the optimal tree T*. The algorithms never fit a parameter to the Dasgupta or Moseley-Wang objective and then report that fitted value as a prediction; instead, they use oracle queries to construct partial HC trees (Theorems 5 and 6) and then prove approximation guarantees relative to OPT_Das(G) and OPT_MW(G). Those guarantees are derived from structural properties of optimal trees, such as the exchange arguments in Claims 6.2 and 6.3, and from established external results such as Proposition 5.1 cited to [CC17a, ACL+22]. The fact that the oracle is defined with respect to T* is a modeling assumption, not a self-definitional reduction: the oracle is an external information source, and the paper explicitly argues that simply following the noisy oracle does not recover T* (Section 2.1). The disputed inequality in Lemma 6.4, highlighted in the skeptic analysis, is a potential correctness gap (an unjustified bound relating w(E3) to w(E2) in the inductive step), but it is not a circularity: the lemma does not assume the theorem it proves. The self-citations that appear, e.g., [DGU+25], [AKL+24], and [ISZ21], are used for context, comparisons, or standard PAC tools and are not load-bearing for the main theorems. Overall, the derivation chain is independent of its conclusions, so the circularity score is minimal.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

No instance-dependent fitted parameters appear; fixed universal constants (e.g., p=9/10, the 50000 log n threshold, and 1/200) are analysis choices rather than data-fitted values. The main axioms are the oracle model, the implicit uniqueness of T*, and standard concentration and prior algorithmic results.

assumptions (6)
  • domain assumption The splitting oracle O answers each distinct triplet correctly with probability p=9/10, with errors adversarial and fixed per triplet.
    Definition 2, Section 3.2; all algorithms rely on concentration over independent triplet errors, and the fixed-randomness rule rules out boosting.
  • domain assumption A single well-defined optimal HC tree T* exists, i.e., unique or with fixed tie-breaking, and the oracle is consistent with it.
    Definition 2 and Definition 1 presuppose 'the optimal tree'; this is not explicitly justified in the paper.
  • domain assumption The HC tree is binary and n >= 200 log n (equivalently n >= 2500).
    Section 3.1 states the binary assumption and the size bound; for constant n a brute-force algorithm is used.
  • standard math Chernoff-Hoeffding concentration bounds.
    Appendix A.1; used throughout Sections 9 and 10 to separate oracle signal from adversarial noise.
  • domain assumption Recursive alpha-approximate sparsest cuts yield O(alpha)-approximation for Dasgupta's objective (Prop 5.3).
    Cited from [CC17a, ACL+22], used as a black box in Section 5.
  • domain assumption SSE hardness of constant approximation for Dasgupta and (1-C) for MW.
    Used only contextually to motivate the oracle model, not as a proof ingredient.
invented entities (2)
  • Splitting oracle O
    purpose: Provides triplet split-away answers from an optimal HC tree, enabling hardness circumvention.
    The oracle is a postulated model of auxiliary information; its existence is assumed, not demonstrated, and no independent falsifiable prediction is given.
  • Partial hierarchical clustering trees (strongly and weakly consistent)
    purpose: Coarse representation of the optimal tree that can be built from oracle answers and then completed locally.
    New data structure introduced in Section 4; its properties are proven algorithmically, but it has no external empirical evidence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning-Augmented Hierarchical Clustering." pith.science (2026). https://pith.science/paper/NZEAY7GS

@misc{pith2026250605495,
  author       = {Pith},
  title        = {Pith review of: Learning-Augmented Hierarchical Clustering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NZEAY7GS}},
  note         = {Machine review of arXiv:2506.05495}
}
abstract

Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recursively partition a dataset into a tree-like structure while grouping together similar data points at each level of granularity. Unfortunately, for many of the proposed HC objectives, there exist strong barriers to approximation algorithms with the hardness of approximation. Thus, we consider the problem of hierarchical clustering given auxiliary information from natural oracles. Specifically, we focus on a *splitting oracle* which, when provided with a triplet of vertices $(u,v,w)$, answers (possibly erroneously) the pairs of vertices whose lowest common ancestor includes all three vertices in an optimal tree, i.e., identifying which vertex ``splits away'' from the others. Using such an oracle, we obtain the following results: - A polynomial-time algorithm that outputs a hierarchical clustering tree with $O(1)$-approximation to the Dasgupta objective (Dasgupta [STOC'16]). - A near-linear time algorithm that outputs a hierarchical clustering tree with $(1-o(1))$-approximation to the Moseley-Wang objective (Moseley and Wang [NeurIPS'17]). Under the plausible Small Set Expansion Hypothesis, no polynomial-time algorithm can achieve any constant approximation for Dasgupta's objective or $(1-C)$-approximation for the Moseley-Wang objective for some constant $C>0$. As such, our results demonstrate that the splitting oracle enables algorithms to outperform standard HC approaches and overcome hardness constraints. Furthermore, our approaches extend to sublinear settings, in which we show new streaming and PRAM algorithms for HC with improved guarantees.

Figures

Figures reproduced from arXiv: 2506.05495 by the authors.

Figure 1
Figure 1. An illustration of the hard example that the straightforward majority voting does not work. Left: [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. An illustration of the strongly consistent partial HC trees as defined in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. An illustration of the weakly consistent partial HC trees as defined in [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: An illustration of how horizon sets help maintain weak consistency. With the same [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: An illustration of the algorithm that merges [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: An illustration of the edge weights and leaves described in [PITH_FULL_IMAGE:figures/full_fig_p025_6.png]
Figure 7
Figure 7. Figure 7: An illustration of the composable vertex sets and maximal trees as in [PITH_FULL_IMAGE:figures/full_fig_p034_7.png]
Figure 8
Figure 8. Figure 8: An illustration of the HC tree T to be restricted on a subset of vertices S. On the other hand, if at least one of x and x ′ is contracted, and let the new internal nodes be y and y ′ , we claim that there is still levelT (S) (y ′ ) > levelT (S) (y). This is simply bec…
Figure 9
Figure 9. Figure 9: An illustration of the notion of small-tree split order [PITH_FULL_IMAGE:figures/full_fig_p036_9.png]
Figure 10
Figure 10. Figure 10: An illustration of the analysis we used in the proof of [PITH_FULL_IMAGE:figures/full_fig_p042_10.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

77 extracted references · 71 canonical work pages

  1. [1]

    Hierarchical clustering: A 0.585 revenue approximation

    Noga Alon, Yossi Azar, and Danny Vainstein. Hierarchical clustering: A 0.585 revenue approximation. In Conference on Learning Theory, COLT , pages 153--162, 2020

    work page 2020

  2. [2]

    Bartlett

    Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations . Cambridge University Press, 1999

    work page 1999

  3. [3]

    Online metric algorithms with untrusted predictions

    Antonios Antoniadis, Christian Coester, Marek Eli \' a s, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithms , 19(2):19:1--19:34, 2023

    work page 2023

  4. [4]

    Chen, and Piotr Indyk

    Anders Aamand, Justin Y. Chen, and Piotr Indyk. (optimal) online bipartite matching with degree information. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS , 2022

    work page 2022

  5. [5]

    Hierarchical clustering in graph streams: Single-pass algorithms and space lower bounds

    Sepehr Assadi, Vaggos Chatziafratis, Jakub Lacki, Vahab Mirrokni, and Chen Wang. Hierarchical clustering in graph streams: Single-pass algorithms and space lower bounds. In Conference on Learning Theory , pages 4643--4702, 2022

    work page 2022

  6. [6]

    Online algorithms with multiple predictions

    Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In International Conference on Machine Learning, ICML , pages 582--598, 2022

    work page 2022

  7. [7]

    0(sqrt (log n)) approximation to SPARSEST CUT in \ o (n\( ^ 2 \)) time

    Sanjeev Arora, Elad Hazan, and Satyen Kale. 0(sqrt (log n)) approximation to SPARSEST CUT in \ o (n\( ^ 2 \)) time. In 45th Symposium on Foundations of Computer Science (FOCS) , Proceedings , pages 238--247, 2004

    work page 2004

  8. [8]

    Parallel approximate maximum flows in near-linear work and polylogarithmic depth

    Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, and Peilin Zhong. Parallel approximate maximum flows in near-linear work and polylogarithmic depth. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3997--4061. SIAM, 2024

    2024

Show all 77 references
  1. [9]

    Sublinear algorithms for hierarchical clustering

    Arpit Agarwal, Sanjeev Khanna, Huan Li, and Prathamesh Patil. Sublinear algorithms for hierarchical clustering. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Ne...

    2022

  2. [10]

    Online graph algorithms with predictions

    Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 35--66, 2022

    2022

  3. [11]

    Aho, Yehoshua Sagiv, Thomas G

    Alfred V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, and Jeffrey D. Ullman. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal on Computing , 10(3):405--421, 1981

    1981

  4. [12]

    On the compatibility of quartet trees

    Noga Alon, Sagi Snir, and Raphael Yuster. On the compatibility of quartet trees. SIAM J. Discret. Math. , 28(3):1493--1507, 2014

    2014

  5. [13]

    Jiang, Hoai-An Nguyen, Chen Wang, Yubo Zhang, and Samson Zhou

    Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H.-C. Jiang, Hoai-An Nguyen, Chen Wang, Yubo Zhang, and Samson Zhou. Relative error fair clustering in the weak-strong oracle model. In Proceedings of the 42nd International Conference on Machine Learning, ICML , 2025

    2025

  6. [14]

    Learning-augmented maximum independent set

    Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah, and Chen Wang. Learning-augmented maximum independent set. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 24:1--24:18, 2024

    2024

  7. [15]

    The primal-dual method for learning augmented algorithms

    \' E tienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

    2020

  8. [16]

    Advice querying under budget constraint for online algorithms

    Ziyad Benomar and Vianney Perchet. Advice querying under budget constraint for online algorithms. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neu...

    2023

  9. [17]

    Approximate hierarchical clustering via sparsest cut and spreading metrics

    Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 841--854. SIAM, 2017

    2017

  10. [18]

    Approximate hierarchical clustering via sparsest cut and spreading metrics

    Moses Charikar and Vaggos Chatziafratis. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 841--854, 2017

    2017

  11. [19]

    Hierarchical clustering better than average-linkage

    Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh. Hierarchical clustering better than average-linkage. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 2291--2304. SIAM , 2019

    2019

  12. [20]

    Hierarchical clustering for euclidean data

    Moses Charikar, Vaggos Chatziafratis, Rad Niazadeh, and Grigory Yaroslavtsev. Hierarchical clustering for euclidean data. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS , pages 2721--2730, 2019

    2019

  13. [21]

    Learning-augmented approximation algorithms for maximum cut and related problems

    Vincent Cohen - Addad, Tommaso d'Orsi, Anupam Gupta, Euiwoong Lee, and Debmalya Panigrahi. Learning-augmented approximation algorithms for maximum cut and related problems. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Process...

    2024

  14. [22]

    Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P

    Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, and Michael Zhang. Triangle and four cycle counting with predictions in graph streams. In The Tenth International Conference on Learning Repr...

    2022

  15. [23]

    Inapproximability for local correlation clustering and dissimilarity hierarchical clustering

    Vaggos Chatziafratis, Neha Gupta, and Euiwoong Lee. Inapproximability for local correlation clustering and dissimilarity hierarchical clustering. CoRR , abs/2010.01459, 2020

    2010 arXiv

  16. [24]

    Chen, Piotr Indyk, and Tal Wagner

    Justin Y. Chen, Piotr Indyk, and Tal Wagner. Streaming algorithms for support-aware histograms. In International Conference on Machine Learning, ICML , pages 3184--3203, 2022

    2022

  17. [25]

    Hierarchical clustering: Objective functions and algorithms

    Vincent Cohen - Addad, Varun Kanade, Frederik Mallmann - Trenn, and Claire Mathieu. Hierarchical clustering: Objective functions and algorithms. Journal of the ACM (JACM) , 66(4):1--42, 2019

    2019

  18. [26]

    Karthik C. S. , Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, and Samson Zhou. On approximability of _2^2 min-sum clustering. CoRR , abs/2412.03332, 2024

    2024 arXiv

  19. [27]

    Triplet reconstruction and all other phylogenetic csps are approximation resistant

    Vaggos Chatziafratis and Konstantin Makarychev. Triplet reconstruction and all other phylogenetic csps are approximation resistant. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 253--284, 2023

    2023

  20. [28]

    Hierarchical clustering with structural constraints

    Vaggos Chatziafratis, Rad Niazadeh, and Moses Charikar. Hierarchical clustering with structural constraints. In Proceedings of the 35th International Conference on Machine Learning, ICML , pages 773--782, 2018

    2018

  21. [29]

    Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang

    Justin Y. Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, ICML , pages 3583--3602, 2022

    2022

  22. [30]

    Bisect and conquer: Hierarchical clustering via max-uncut bisection

    Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, and Mohammad Mahdian. Bisect and conquer: Hierarchical clustering via max-uncut bisection. In The 23rd International Conference on Artificial Intelligence and Sta...

    2020

  23. [31]

    A cost function for similarity-based hierarchical clustering

    Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016 , pages 118--127. ACM , 2016

    2016

  24. [32]

    On the price of differential privacy for hierarchical clustering

    Chengyuan Deng, Jie Gao, Jalaj Upadhyay, Chen Wang, and Samson Zhou. On the price of differential privacy for hierarchical clustering. In The Thirteenth International Conference on Learning Representations, ICLR , 2025

    2025

  25. [33]

    Faster matchings via learned duals

    Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 10393--10406, 2021

    2021

  26. [34]

    Predictive flows for faster ford-fulkerson

    Sami Davies, Benjamin Moseley, Sergei Vassilvitskii, and Yuyan Wang. Predictive flows for faster ford-fulkerson. In International Conference on Machine Learning, ICML , volume 202, pages 7231--7248, 2023

    2023

  27. [35]

    Learning-augmented streaming algorithms for approximating MAX-CUT

    Yinhao Dong, Pan Peng, and Ali Vakilian. Learning-augmented streaming algorithms for approximating MAX-CUT . In 16th Innovations in Theoretical Computer Science Conference, ITCS , pages 44:1--44:24, 2025

    2025

  28. [36]

    Ergun, Zhili Feng, Sandeep Silwal, David P

    Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, and Samson Zhou. Learning-augmented k -means clustering. In The Tenth International Conference on Learning Representations, ICLR , 2022

    2022

  29. [37]

    Adaptive hierarchical clustering using ordinal queries

    Ehsan Emamjomeh - Zadeh and David Kempe. Adaptive hierarchical clustering using ordinal queries. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 415--429, 2018

    2018

  30. [38]

    Nguyen, Jung Hoon Seo, Ryan S

    Chunkai Fu, Brandon G. Nguyen, Jung Hoon Seo, Ryan S. Zesch, and Samson Zhou. Learning-augmented search data structures. In The Thirteenth International Conference on Learning Representations, ICLR , 2025

    2025

  31. [39]

    Efficient algorithms for divisive hierarchical clustering with the diameter criterion

    Alain Gu \'e noche, Pierre Hansen, and Brigitte Jaumard. Efficient algorithms for divisive hierarchical clustering with the diameter criterion. Journal of classification , 8:5--30, 1991

    1991

  32. [40]

    Learning-augmented algorithms for online linear and semidefinite programming

    Elena Grigorescu, Young - San Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. Learning-augmented algorithms for online linear and semidefinite programming. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, ...

    2022

  33. [41]

    Online algorithms for rent-or-buy with expert advice

    Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning, ICML , pages 2319--2327, 2019

    2019

  34. [42]

    Augmenting online algorithms with varepsilon -accurate predictions

    Anupam Gupta, Debmalya Panigrahi, Bernardo Subercaseaux, and Kevin Sun. Augmenting online algorithms with varepsilon -accurate predictions. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems...

    2022

  35. [43]

    On dasgupta's hierarchical clustering objective and its relation to other graph parameters

    Svein H gemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul, and Jan Arne Telle. On dasgupta's hierarchical clustering objective and its relation to other graph parameters. In Evripidis Bampis and Aris Pagourtzis, editors, Fundamentals of Computation Theory - 23rd Inter...

    2021

  36. [44]

    Learning-based frequency estimation algorithms

    Chen - Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR , 2019

    2019

  37. [45]

    Online knapsack with frequency predictions

    Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 2733--2743, 2021

    2021

  38. [46]

    Dimensionality reduction for wasserstein barycenter

    Zachary Izzo, Sandeep Silwal, and Samson Zhou. Dimensionality reduction for wasserstein barycenter. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS , 2021

    2021

  39. [47]

    Learning-based low-rank approximations

    Piotr Indyk, Ali Vakilian, and Yang Yuan. Learning-based low-rank approximations. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS , pages 7400--7410, 2019

    2019

  40. [48]

    Kearney, and Ming Li

    Tao Jiang, Paul E. Kearney, and Ming Li. A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput. , 30(6):1942--1961, 2000

    1942

  41. [49]

    Woodruff

    Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. Learning-augmented data stream algorithms. In 8th International Conference on Learning Representations, ICLR , 2020

    2020

  42. [50]

    Shaofeng H. - C. Jiang, Erzhi Liu, You Lyu, Zhihao Gavin Tang, and Yubo Zhang. Online facility location with predictions. In The Tenth International Conference on Learning Representations, ICLR , 2022

    2022

  43. [51]

    Chi, Jeffrey Dean, and Neoklis Polyzotis

    Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference , pages 489--504, 2018

    2018

  44. [52]

    Learning predictions for algorithms with predictions

    Misha Khodak, Maria - Florina Balcan, Ameet Talwalkar, and Sergei Vassilvitskii. Learning predictions for algorithms with predictions. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems, NeurIPS , 2022

    2022

  45. [53]

    Training gaussian mixture models at scale via coresets

    Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via coresets. J. Mach. Learn. Res. , 18:160:1--160:25, 2017

    2017

  46. [54]

    Woodruff

    Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, and David P. Woodruff. Learning the positions in countsketch. In The Eleventh International Conference on Learning Representations, ICLR , 2023

    2023

  47. [55]

    Online scheduling via learned weights

    Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 1859--1877, 2020

    2020

  48. [56]

    Woodruff

    Honghao Lin, Tian Luo, and David P. Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, ICML , pages 13431--13440, 2022

    2022

  49. [57]

    Mining of massive data sets

    Jure Leskovec, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive data sets . Cambridge university press, 2020

    2020

  50. [58]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM , 68(4):24:1--24:25, 2021

    2021

  51. [59]

    A model for learned bloom filters and optimizing by sandwiching

    Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 462--471, 2018

    2018

  52. [60]

    Hierarchical clustering: O(1)-approximation for well-clustered graphs

    Bogdan - Adrian Manghiuc and He Sun. Hierarchical clustering: O(1)-approximation for well-clustered graphs. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 9278--9289, 2021

    2021

  53. [61]

    Algorithms with predictions

    Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms , pages 646--662. Cambridge University Press, 2020

    2020

  54. [62]

    Benjamin Moseley and Joshua R. Wang. Approximation bounds for hierarchical clustering: Average linkage, bisecting k-means, and local search. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems , pages 3094--3103, 2017

    2017

  55. [63]

    Thy Dinh Nguyen, Anamay Chaturvedi, and Huy L. Nguyen. Improved learning-augmented algorithms for k-means and k-medians clustering. In The Eleventh International Conference on Learning Representations, ICLR , 2023

    2023

  56. [64]

    Improving online algorithms via ML predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predictions. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS , pages 9684--9693, 2018

    2018

  57. [65]

    Hierarchical clustering via spreading metrics http://papers.nips.cc/paper/6325-hierarchical-clustering-via-spreading-metrics.pdf

    Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metrics http://papers.nips.cc/paper/6325-hierarchical-clustering-via-spreading-metrics.pdf . In Advances in Neural Information Processing Systems , pages 2316--2324, 2016

    2016

  58. [66]

    Hierarchical clustering via spreading metrics

    Aurko Roy and Sebastian Pokutta. Hierarchical clustering via spreading metrics. J. Mach. Learn. Res. , 18:88:1--88:35, 2017

    2017

  59. [67]

    Procopiuc, and Claudio Gentile

    Anand Rajagopalan, Fabio Vitale, Danny Vainstein, Gui Citovsky, Cecilia M. Procopiuc, and Claudio Gentile. Hierarchical clustering of data streams: Scalable algorithms and approximation guarantees. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International ...

    2021

  60. [68]

    A comparison of document clustering techniques

    Michael Steinbach, George Karypis, and Vipin Kumar. A comparison of document clustering techniques. Technical report, University of Minnesota, 2000

    2000

  61. [69]

    Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis

    Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung - Chan An. Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In International Conference on Machine Learning, ICML , pages 31539--31561, 2023

    2023

  62. [70]

    Breast cancer classification and prognosis based on gene expression profiles from a population-based study

    Christos Sotiriou, Soek-Ying Neo, Lisa M McShane, Edward L Korn, Philip M Long, Amir Jazaeri, Philippe Martiat, Steve B Fox, Adrian L Harris, and Edison T Liu. Breast cancer classification and prognosis based on gene expression profiles from a population-based study. Proceedin...

    2003

  63. [71]

    Numerical taxonomy

    Peter HA Sneath, Robert R Sokal, et al. Numerical taxonomy. the principles and practice of numerical classification., 1973

    1973

  64. [72]

    A linear time approximation scheme for maximum quartet consistency on sparse sampled inputs

    Sagi Snir and Raphael Yuster. A linear time approximation scheme for maximum quartet consistency on sparse sampled inputs. SIAM J. Discret. Math. , 25(4):1722--1736, 2011

    2011

  65. [73]

    Goodfellow, and Rob Fergus

    Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In 2nd International Conference on Learning Representations, ICLR , Conference Track Proceedings , 2014

    2014

  66. [74]

    Who belongs in the family? Psychometrika , 18(4):267--276, 1953

    Robert L Thorndike. Who belongs in the family? Psychometrika , 18(4):267--276, 1953

    1953

  67. [75]

    Hierarchical grouping to optimize an objective function

    Joe H Ward Jr. Hierarchical grouping to optimize an objective function. Journal of the American statistical association , 58(301):236--244, 1963

    1963

  68. [76]

    Online algorithms for multi-shop ski rental with machine learned advice

    Shufan Wang, Jian Li, and Shiqiang Wang. Online algorithms for multi-shop ski rental with machine learned advice. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

    2020

  69. [77]

    Optimal robustness-consistency trade-offs for learning-augmented online algorithms

    Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning-augmented online algorithms. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS , 2020

    2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.