constraint satisfaction 1hierarchical clustering 1phase transitions 1phylogenetics 1refutation algorithms 1
From the 1 of 2 linked papers with an AI index.
2 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
The paper analyzes phase transitions and provides algorithms for refuting phylogenetic constraint satisfaction problems, establishing sharp density thresholds for triplet and quart…
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…