Cover Image

Optimal Phylogenetic Reconstruction from Sampled Quartets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Arvanitakis, Dionysis, Chatziafratis, Vaggos, Luo, Yiyuan, Makarychev, Konstantin
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
by: Arvanitakis, Dionysis, et al.
Published: (2026)

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
by: Chatziafratis, Vaggos, et al.
Published: (2023)

Constraint Satisfaction Problems with Advice
by: Ghoshal, Suprovat, et al.
Published: (2024)

Welfare Approximation in Additively Separable Hedonic Games
by: Bullinger, Martin, et al.
Published: (2025)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
by: Dalirrooyfard, Mina, et al.
Published: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
by: Dalirrooyfard, Mina, et al.
Published: (2025)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
by: Dalirrooyfard, Mina, et al.
Published: (2024)

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
by: Makarychev, Yury
Published: (2026)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
by: Makarychev, Konstantin, et al.
Published: (2025)

Hardness of Approximation for Shortest Path with Vector Costs
by: Carlson, Charlie, et al.
Published: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
by: Makarychev, Yury, et al.
Published: (2024)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

Path Partitions of Phylogenetic Networks
by: Lafond, Manuel, et al.
Published: (2024)

Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
by: van Iersel, Leo, et al.
Published: (2026)

Near-Optimal Trace Reconstruction for Mildly Separated Strings
by: Aamand, Anders, et al.
Published: (2024)

Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
by: Holtgrefe, Niels, et al.
Published: (2026)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
by: Bansal, Nikhil, et al.
Published: (2024)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
by: Black, Hadley
Published: (2023)

Optimal Dynamic Parameterized Subset Sampling
by: Gan, Junhao, et al.
Published: (2024)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
by: Holtgrefe, Niels, et al.
Published: (2026)

Optimal Dimension-Free Sampling for Regularized Classification
by: Alishahi, Meysam, et al.
Published: (2026)

Finding Maximum Common Contractions Between Phylogenetic Networks
by: Marchand, Bertrand, et al.
Published: (2024)

Weighted Reservoir Sampling With Replacement from Data Streams
by: Meligrana, Adriano, et al.
Published: (2024)

Fingerprint Filters Are Optimal
by: Kuszmaul, William, et al.
Published: (2025)

Optimal antimatroid sorting
by: Berendsohn, Benjamin Aram
Published: (2025)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Near-Optimal Sample Complexity for MDPs via Anchoring
by: Lee, Jongmin, et al.
Published: (2025)

Simpler Optimal Sorting from a Directed Acyclic Graph
by: van der Hoog, Ivor, et al.
Published: (2024)

New Bounds for Circular Trace Reconstruction
by: Burudgunte, Arnav, et al.
Published: (2025)

Graph Reconstruction via MIS Queries
by: Konrad, Christian, et al.
Published: (2024)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

The Role of Commitment in Optimal Stopping
by: Correa, José, et al.
Published: (2025)

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)