Evolutionary trees can be learned in polynomial time in the two-state general Markov model

No abstract is available for this paper.

• Publication year

  1998

• Venue

  Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)

• Publication date

  1998-11-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.1998.743494
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Elements of Information Theory

  2005cited by this paper
• A few logs suffice to build (almost) all trees (I)

  1999cited by this paper
• A few logs suffice to build (almost) all trees

  1999cited by this paper
• A few logs suffice to build (almost) all trees (l): part I

  1997cited by this paper
• Nearly tight bounds on the learnability of evolution

  1997influential reference
• Efficient algorithms for inverting evolution

  1996influential reference
• On the approximability of numerical taxonomy (fitting distances by tree metrics)

  1996cited by this paper
• On the approximability of numerical taxonomy

  1996cited by this paper
• Eecient Algorithms for Inverting Evolution

  1995influential reference
• On the learnability of discrete distributions

  1994influential reference
• Recovering a tree from the leaf colourations it generates under a Markov model

  1994influential reference
• Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence

  1991cited by this paper
• Surveys in Combinatorics, 1989: On the method of bounded differences

  1989cited by this paper
• Reconstructing the shape of a tree from observed dissimilarity data

  1986cited by this paper
• Taxonomy with confidence

  1978cited by this paper
• A Probability Model for Inferring Evolutionary Trees

  1973cited by this paper
• MOLECULAR STUDIES OF EVOLUTION: A SOURCE OF NOVEL STATISTICAL PROBLEMS*

  1971cited by this paper

• Are theoretical advances in distance-based tree learning practical for phylogenetic inference?

  2026cites this paper
• A Distributional-Lifting Theorem for PAC Learning

  2025cites this paper
• Bounds on the sequence length sufficient to reconstruct level-1 phylogenetic networks

  2025influential citation
• Dynamic Simulation and Forecasting of Spatial Expansion in Small and Medium-Sized Cities Using ANN-CA-Markov Models

  2024cites this paper
• Model Stealing for Any Low-Rank Language Model

  2024cites this paper
• Lifting Uniform Learners via Distributional Decomposition

  2023cites this paper
• The Identification of Discrete Mixture Models

  2023cites this paper
• Learning Hidden Markov Models Using Conditional Samples

  2023cites this paper
• Causal Discovery under Latent Class Confounding

  2023cites this paper
• Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity

  2023cites this paper
• Efficient Algorithms for Sparse Moment Problems without Separation

  2022cites this paper
• Learning and Testing Latent-Tree Ising Models Efficiently

  2022cites this paper
• Hadamard Extensions and the Identification of Mixtures of Product Distributions

  2021cites this paper
• Causal Inference Despite Limited Global Confounding via Mixture Models

  2021cites this paper
• Identifying Mixtures of Bayesian Network Distributions

  2021cites this paper
• Hadamard Powers and the Identification of Mixtures of Products

  2021cites this paper
• The Sparse Hausdorff Moment Problem, with Application to Topic Models

  2020cites this paper
• Source Identification for Mixtures of Product Distributions

  2020cites this paper
• Principled approaches to robust machine learning and beyond

  2018cites this paper
• Circular Networks from Distorted Metrics

  2017cites this paper
• Distance-based species tree estimation under the coalescent: Information-theoretic trade-off between number of loci and sequence length

  2017cites this paper
• Coalescent-based species tree estimation: a stochastic Farris transform

  2017cites this paper
• Phase transition in the sample complexity of likelihood-based phylogeny inference

  2017cites this paper
• Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures

  2016cites this paper
• Efficient Robust Proper Learning of Log-concave Distributions

  2016cites this paper
• Robust Estimators in High Dimensions without the Computational Intractability

  2016cites this paper
• Testing Bayesian Networks

  2016cites this paper
• Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables

  2015cites this paper
• Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables

  2015cites this paper
• Phase transition in the sample complexity of likelihood-based phylogeny inference

  2015cites this paper
• Species Trees are Recoverable from Unrooted Gene Tree Topologies Under a Constant Rate of Horizontal Gene Transfer

  2015cites this paper
• Properly Learning Poisson Binomial Distributions in Almost Polynomial Time

  2015cites this paper
• Species Trees from Gene Trees Despite a High Rate of Lateral Genetic Transfer: A Tight Bound (Extended Abstract)

  2015cites this paper
• Symmetric Tensor Completion from Multilinear Entries and Learning Product Mixtures over the Hypercube

  2015cites this paper
• Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent

  2015cites this paper
• Learning Arbitrary Statistical Mixtures of Discrete Distributions

  2015cites this paper
• Learning Sums of Independent Integer Random Variables

  2013cites this paper
• Fast and reliable reconstruction of phylogenetic trees with indistinguishable edges

  2012cites this paper
• DACTAL: divide-and-conquer trees (almost) without alignments

  2012cites this paper
• Learning mixtures of arbitrary distributions over large discrete domains

  2012cites this paper
• Estimating Optimal Species Trees from Incomplete Gene Trees Under Deep Coalescence

  2012cites this paper
• Linear classifiers are nearly optimal when hidden variables have diverse effects

  2012cites this paper
• Learning Mixtures of Distributions over Large Discrete Domains

  2012cites this paper
• Learning transformed product distributions

  2011influential citation
• Parameter testing in bounded degree graphs of subexponential growth

  2010cites this paper
• A note on trees, tables, and algorithms

  2009cites this paper
• The minimum evolution problem: Overview and classification

  2009cites this paper
• A pr 2 00 6 Network Delay Inference from Additive Metrics

  2009cites this paper
• Reconstructing phylogenetic trees from noisy metrics

  2009cites this paper
• Inference from Sparse Sampling ( Extended Abstract )

  2008cites this paper
• Fast Phylogeny Reconstruction Through Learning of Ancestral Sequences

  2008cites this paper
• Learning Balanced Mixtures of Discrete Distributions with Small Sample

  2008cites this paper
• A pr 2 00 6 Network Delay Inference from Additive Metrics

  2008cites this paper
• Phylogenies without Branch Bounds: Contracting the Short, Pruning the Deep

  2008cites this paper
• Pattern classification via unsupervised learners

  2008influential citation
• Fast and reliable reconstruction of phylogenetic trees with very short edges

  2008cites this paper
• Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier

  2008cites this paper
• Markov models on trees: Reconstruction and applications

  2007influential citation
• Separating Populations with Wide Data: A Spectral Analysis

  2007cites this paper
• RECONSTRUCTING EVOLUTIONARY TREES IN A GENERAL MARKOV MODEL

  2007cites this paper
• PAC Learning Mixtures of Gaussians with No Separation Assumption

  2006cites this paper
• Some Discriminant-Based PAC Algorithms

  2006influential citation
• Routing, Disjoint Paths, and Classification (CMU-PDL-06-109)

  2006cites this paper
• PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption

  2006cites this paper
• PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption

  2006cites this paper
• Routing, disjoint paths, and classification

  2006cites this paper
• Network delay inference from additive metrics

  2006cites this paper
• Learning nonsingular phylogenies and hidden Markov models

  2005cites this paper
• PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

  2005cites this paper
• Learning mixtures of product distributions over discrete domains

  2005cites this paper
• Approximating the Best-Fit Tree Under Lp Norms

  2005cites this paper
• Distorted Metrics on Trees and Phylogenetic Forests

  2004influential citation
• PAC Classification based on PAC Estimates of Label Class Distributions

  2004cites this paper
• Large-scale phylogenetic analysis

  2003cites this paper
• Phase transitions in phylogeny

  2003cites this paper
• Combining polynomial running time and fast convergence for the disk-covering method

  2002cites this paper
• When Can Two Unsupervised Learners Achieve PAC Separation?

  2001cites this paper
• Absolute convergence: true trees from short sequences

  2001influential citation
• References to publications of

  2001cites this paper
• Fast Recovery of Evolutionary Trees with Thousands of Nodes

  2001cites this paper
• Provably Fast and Accurate Recovery of Evolutionary Trees through Harmonic Greedy Triplets

  2000cites this paper
• When Can Two Unsupervised Learners A hieve PACSeparation ?

  2000cites this paper
• Linear on epts and hidden variables

  2000cites this paper
• Inverting random functions

  1999cites this paper
• Efficient algorithms for inverting evolution

  1999cites this paper
• Learning and approximation algorithms for problems motivated by evolutionary trees

  1999influential citation
• Lower Bounds on Sequence Lengths Required to Recover the Evolutionary Tree

  1999cites this paper
• Disk-Covering, a Fast-Converging Method for Phylogenetic Tree Reconstruction

  1999influential citation
• A Few Logs Suffice to Build (almost) All Trees: Part II

  1999cites this paper
• Annals of Combinatorics Inverting Random Functions

  1998cites this paper
• Fast Recovery of Evolutionary Trees through Harmonic Greedy Triplets

  1998cites this paper
• Linear Concepts and Hidden Variables

  1997cites this paper
• ½ºº Ź¹óó×øøòò ×øøòòò¹¹¹××× Ññøøó× ½¹½½

  year unknowncites this paper
• I NDUSTRIAL M ATHEMATICS I NSTITUTE

  year unknowncites this paper