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