3 papers
cs.DS2026
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…
cs.DS2026
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…
cs.DS2026
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…