Tutorial 1
Speaker: Albert Atserias (UPC)
Title: Local-vs-Global Consistency of Annotated Relations
Slides (pdf)
Abstract: In database theory, two or more relations are considered
consistent if they can be realized as projections of a single global
universal relation. Similarly, in probability theory, two or more
probability distributions over overlapping sets of random variables
are called compatible if they arise as marginals of a single global
joint distribution. In quantum theory, two or more observables of a
quantum system are jointly measurable if they can be expressed as
orthogonal linear projections of a single global observable.
A fundamental challenge in each of these fields is determining the
necessary and sufficient conditions under which local components admit
a global realization. This tutorial begins with the observation that
the problem of comparing local and global phenomena in these three
scenarios can be formally unified as special cases of local-vs-global
consistency for relations annotated with elements from a positive
commutative monoid.
After reviewing the formal framework of K-relations, where K is a
positive commutative monoid, we adapt the standard notions of
consistency for classical relations to the setting of K-relations. We
highlight both the parallels with the classical framework and the key
differences that make this theory particularly rich and interesting.
Bio: Albert Atserias is a Professor of Computer Science at Universitat
Politècnica de Catalunya (UPC), Barcelona. His research focuses on
computational complexity, algorithms, combinatorics, random
structures, and the applications of logic to computer science. He has
made significant contributions to propositional proof complexity,
descriptive complexity, and finite model theory, particularly in
bridging the gap between the two traditional tracks of theoretical
computer science (track A and track B).
Atserias is renowned for establishing connections between methods such
as Ehrenfeucht-Fraïssé games in finite model theory and lower-bound
techniques for propositional proof systems in proof complexity. His
work also explores the interplay between two-player games,
lift-and-project methods in mathematical programming, and their
associated proof systems. Among his achievements in proof complexity
is the solution to the long-standing problem of the non-automatability
of Resolution, which earned him a Best Paper Award at FOCS 2019. His
early research in database theory led to influential concepts such as
the "AGM bound" for estimating the worst-case output size of
relational database joins. His more recent work on consistency of
annotated databases earned him a Best Paper Award at PODS
2024. Atserias has received over 1,500 citations for his work, with
significant contributions published in top-tier journals such as the
Journal of the ACM and SIAM Journal on Computing.
Atserias has been a principal investigator for an ERC Consolidator
Grant (AUTAR) and has held visiting positions at institutions such as
the University of California, Berkeley, the Isaac Newton Institute for
Mathematical Sciences, and the Simons Institute for the Theory of
Computing. He has been invited as a plenary speaker at numerous
conferences, including the ASL Logic Colloquium, LICS, SAT, ICALP and
STACS, and has served on the editorial boards of leading journals in
theoretical computer science.
Tutorial 2
Speaker: Stefan Mengel (French National Centre for Scientific Research)
Title: Lower Bounds for Conjunctive Query Evaluation
Accompanying paper (pdf)
Slides (pdf)
Abstract: In this tutorial, we will survey known results on the complexity of conjunctive query evaluation in different settings, ranging from Boolean queries over counting to more complex models like enumeration and direct access. A particular focus will be showing how different relatively recent hypotheses from complexity theory connect to query answering and allow showing that known algorithms in several cases can likely not be improved.
Bio: Stefan Mengel is a tenured full-time senior researcher at CNRS the French National Centre for Scientific Research and is working in Lens France. Before joining CNRS in 2015, he spent two years as a postdoc at Ecole Polytechnique in France. He holds a PhD in math from University of Paderborn. Stefan's research is mostly on applications of theoretical computer science, in particular complexity theory, to questions from database theory and artificial intelligence. In database theory, his contributions are mostly on different versions of query answering, including counting, enumeration and succinct representations of query results.
