High-temperature structure detection in ferromagnets

Yuan Cao, Matey Neykov*, Han Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

This paper studies structure detection problems in high-temperature ferromagnetic (positive interaction only) Ising models. The goal is to distinguish whether the underlying graph is empty, i.e., the model consists of independent Rademacher variables, vs. the alternative that the underlying graph contains a subgraph of a certain structure. We give matching upper and lower minimax bounds under which testing this problem is possible/impossible, respectively. Our results reveal that a key quantity called graph arboricity drives the testability of the problem. On the computational front, under a conjecture of the computational hardness of sparse principal component analysis, we prove that, unless the signal is strong enough, there are no polynomial time tests which are capable of testing this problem. In order to prove this result, we exhibit a way to give sharp inequalities for the even moments of sums of i.i.d. Rademacher random variables which may be of independent interest.

Original languageEnglish (US)
Pages (from-to)55-102
Number of pages48
JournalInformation and Inference
Volume11
Issue number1
DOIs
StatePublished - Mar 1 2022

Keywords

  • ferromagnetic Ising model
  • graph structure detection
  • minimax testing
  • total variation distance

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Numerical Analysis
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'High-temperature structure detection in ferromagnets'. Together they form a unique fingerprint.

Cite this