Prossimi notiziari settimanali

Su questa pagina, è possibile visualizzare le richieste approvate dai redattori per la pubblicazione di eventi nel notiziario scientifico delle prossime 2 settimane.

Seleziona il lunedì della settimana che desideri visualizzare:   


Notiziario dei seminari di carattere matematico
a cura del Dipartimento di Matematica G. Castelnuovo, Sapienza Università di Roma

Settimana dal 21-10-2019 al 27-10-2019


Giovedì 24 ottobre 2019
Ore 16:00, Aula 211, Dipartimento di Matematica e Fisica - Largo S. L. Murialdo,1
Seminario di Probabilità
Antonio Blanca (Penn State University)
Lower bounds for testing spin systems
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


Le comunicazioni relative a seminari da includere in questo notiziario devono pervenire esclusivamente mediante apposita form da compilare online, entro le ore 24 del giovedì precedente la settimana interessata. Le comunicazioni pervenute in ritardo saranno ignorate. Per informazioni, rivolgersi all'indirizzo di posta elettronica seminari@mat.uniroma1.it.
Coloro che desiderano ricevere questo notiziario via e-mail sono pregati di comunicare il proprio indirizzo di posta elettronica a seminari@mat.uniroma1.it.

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma