The Complexity of Distinguishing Markov Random Fields

DOI10.1007/978-3-540-85363-3_27zbMath1159.68042OpenAlexW1584402024MaRDI QIDQ3541806

Andrej Bogdanov, Elchanan Mossel, Salil P. Vadhan

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85363-3_27

Mathematics Subject Classification ID

Random fields (60G60) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, A Unified Framework for Structured Graph Learning via Spectral Constraints, Learning loopy graphical models with latent variables: efficient methods and guarantees, Computational implications of reducing data to sufficient statistics, Region selection in Markov random fields: Gaussian case, High-dimensional structure estimation in Ising models: local separation criterion, Communication Complexity of Statistical Distance, Unnamed Item, The complexity of estimating min-entropy