# The Complexity of Distinguishing

Markov Random Fields

Andrej Bogdanov, Elchanan Mossel, and Salil Vadhan

### Abstract

Markov random fields are often used to model high
dimensional distributions in a number of applied areas. A number of recent
papers have studied the problem of reconstructing a dependency graph of bounded
degree from independent samples from the Markov random field. These results
require observing samples of the distribution at all nodes of the graph. It was
heuristically recognized that the problem of reconstructing the model where
there are hidden variables (some of the variables are not observed) is much
harder.

Here we prove that the problem of reconstructing bounded-degree
models with hidden nodes is hard.
Specifically, we show that unless NP=RP,

- It is
impossible to decide in randomized polynomial time if two models generate
distributions whose statistical distance is at most 1/3 or at least 2/3.
- Given
two generating models whose statistical distance is promised to be at
least 1/3, and oracle access to independent samples from one of the
models, it is impossible to decide in randomized polynomial time which of
the two samples is consistent with the model.

The second problem remains hard even if the samples are
generated efficiently, albeit under a stronger assumption.

### Versions

- In
*Proceedings of the* *12th
International Workshop on Randomization and Computation (RANDOM `08), *volume
5171 of* Lecture Notes in Computer
Science, *pages 331-342. Springer-Verlag,
25-27 August 2008. [pdf][Springer page]

[ back to Salil Vadhan's research]