Hardness of Identity Testing for Potts models and RBMs

          @misc{ scivideos_16885,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-259},
            author = {},
            keywords = {},
            language = {en},
            title = {Hardness of Identity Testing for Potts models and RBMs},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {dec},
            note = {16885 see, \url{https://scivideos.org/Simons-Institute/16885}}
          }
          

Abstract

We study the identity testing problem in the context of spin systems where it takes the following form: given the parameter specification of the model M and a sampling oracle for the distribution μ of an unknown model M*, can we efficiently determine if the two models M and M* are the same? We establish hardness results for this problem in two prototypical cases: the q-state ferromagnetic Potts model and Restricted Boltzmann Machines (RBMs). Daskalakis, Dikkala and Kamath (2018) presented a polynomial-time algorithm for identity testing for the ferromagnetic Ising model, which corresponds to the special case where there are only two spins (q=2). In this talk, I will present recent, complementary hardness results for the Potts model when q > 2 and for RBMs (i.e., mixed Ising models on bipartite graphs). Our proofs lay out a methodology to reduce approximate counting to identity testing, utilizing the phase transitions exhibited by the models and using random graphs as gadgets in the reduction.  Based on joint work with Zongchen Chen, Daniel Stefankovic, and Eric Vigoda.