Reconstructing Markov processes from independent and anonymous experiments

DOI10.1016/J.DAM.2015.06.035MaRDI QIDQ906437zbMATH OpenOpenAlexFDO

Authors Zeyuan Allen Zhu, Silvio Micali

Publication date 21 January 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.06.035

zbMATH Keywords

random walkMarkov processgraph reconstructionlocal algorithms

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random walks on graphs (05C81)

Recommendations

• scientific article; zbMATH DE number 1029228
• Sampling reconstruction of Markov processes with a finite number of states
• Reconstruction of Markov random fields from samples: some observations and algorithms
• Reconstruction of sequential machines by experiments
• Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms

Cites work

• scientific article; zbMATH DE number 5957397 (Why is no real title available?)
• scientific article; zbMATH DE number 3567782 (Why is no real title available?)
• scientific article; zbMATH DE number 733406 (Why is no real title available?)
• scientific article; zbMATH DE number 1168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3436645 (Why is no real title available?)
• scientific article; zbMATH DE number 2079368 (Why is no real title available?)
• An optimal algorithm to reconstruct trees from additive distance data
• Approximating discrete probability distributions with dependence trees
• Finding sparse cuts locally using evolving sets
• Graph reconstruction via distance oracles
• Graph-Theoretic Concepts in Computer Science
• Learning a Hidden Matching
• Learning a Hidden Subgraph
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Memory Efficient Anonymous Graph Exploration
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Network Inference From Co-Occurrences
• Optimal reconstruction of graphs under the additive model
• Optimally reconstructing weighted graphs using queries
• Probabilistic graphical models.
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Sequential updating of conditional probabilities on directed graphical structures
• The structure and dynamics of networks
• Using PageRank to Locally Partition a Graph
• Using optimization to break the epsilon barrier: a faster and simpler width-independent algorithm for solving positive linear programs in parallel

This page was built for publication: Reconstructing Markov processes from independent and anonymous experiments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906437)