Abstract
This paper studies structure detection problems in high temperatureferromagnetic (positive interaction only) Ising models. The goal is todistinguish whether the underlying graph is empty, i.e., the model consists ofindependent Rademacher variables, versus the alternative that the underlyinggraph contains a subgraph of a certain structure. We give matching upper andlower minimax bounds under which testing this problem is possible/impossiblerespectively. Our results reveal that a key quantity called graph arboricitydrives the testability of the problem. On the computational front, under aconjecture of the computational hardness of sparse principal componentanalysis, we prove that, unless the signal is strong enough, there are nopolynomial time tests which are capable of testing this problem. In order toprove this result we exhibit a way to give sharp inequalities for the evenmoments of sums of i.i.d. Rademacher random variables which may be ofindependent interest.