Speaker: Antonio Blanca (Penn State University)
Titolo: Lower bounds for testing spin systems
Giovedi' 24 Ottobre 2019 ORE 10:00
Dipartimento di Matematica e Fisica Universita' degli Studi Roma Tre Largo San Leonardo Murialdo,1 - Pal.C - Aula 211
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 for two prototypical spin systems: the Ising model and proper colorings. For the ferromagnetic (attractive) Ising model, Daskalakis et al. (2018) presented a polynomial-time algorithm for identity testing. I will present a hardness result for the antiferromagnetic (repulsive) setting. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal works on the hardness of approximate counting. The results for proper colorings are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. Based on joint work with Ivona Bezakova, Zongchen Chen, Daniel Stefankovic and Eric Vigoda