32 citations · 67 across the 14 of their papers we have counts for
13 papers · 1 filter
Strong Refutation of Ordering, Phylogenetic, and Ordinary CSPs, and New Satisfiability and Refutation Thresholds for Triplet and Quartet Reconstruction
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1
We study phase transitions and algorithms for refuting CSPs arising in hierarchical clustering (as well as ranking, and ordinary CSPs). Here, variables are assigned to leaves o…
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo
Embedding-based representations in Euclidean space are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that fait…
Optimal Phylogenetic Reconstruction from Sampled Quartets
Dionysis Arvanitakis, Vaggos Chatziafratis, Yiyuan Luo +1
Quartet Reconstruction, the task of recovering a phylogenetic tree from smaller trees on four species called \textit{quartets}, is a well-studied problem in theoretical computer sc…
Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
Vaggos Chatziafratis, Piotr Indyk
Metric embeddings traditionally study how to map items to a target metric space such that distance lengths are not heavily distorted; but what if we only care to preserve the r…
Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
Vaggos Chatziafratis, Mohammad Mahdian, Sara Ahmadian
In this paper, we study a number of well-known combinatorial optimization problems that fit in the following paradigm: the input is a collection of (potentially inconsistent) local…
Hierarchical Clustering via Sketches and Hierarchical Correlation Clustering
Danny Vainstein, Vaggos Chatziafratis, Gui Citovsky +3
Recently, Hierarchical Clustering (HC) has been considered through the lens of optimization. In particular, two maximization objectives have been defined. Moseley and Wang defined…