From the 1 of 3 linked papers with an AI index.
3 papers
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…
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…