Agenda

RESUMEN

In several computer science applications one encounters the following problem: Given two edge-labeled graphs G and H, how many homomorphic images of H can be found in G? Atserias, Grohe, and Marx developed a tight bound for this number, denoted #Hom(H,G), which is now known as the AGM bound. The bound relates #Hom(H,G) with the fractional edge covers of H in a very elegant and direct way. We will present a self-contained and simple proof of this result using Holder’s inequality.

PRESENTA

Pablo Barceló is a full Professor at the Pontificia Universidad Católica de Chile, where he also acts as Director of the Institute for Mathematical and Computational Engineering. Previously, he served as Deputy Director of the Millennium Nucleus Center for Semantic Web Research, an initiative that gave origin to the Millennium Institute for Foundational Research on Data. He obtained his Ph.D. in Computer Science from the University of Toronto, Canada. He is the author of more than 70 technical papers, has chaired ICDT 2019, will be chairing ACM PODS 2022, and is currently a member of the editorial committee of Logical Methods in Computer Science. From 2011 to 2014 he was the editor of the database theory column of SIGMOD Record. His areas of interest are database theory, logic in computer science, and the emerging relationship between these areas and machine learning.

DÓNDE Y CUÁNDO

Seminario IMC, 25 de mayo, 13 hrs: «The AGM Bound». 

Auditorio San Agustín del Instituto de Ingeniería Matemática y Computacional (IMC), Pontificia Universidad Católica de Chile.

Además, habrá link Zoom disponible escribiendo a imc@uc.cl.