Tutorial 1
Speaker: Albert Atserias (UPC)
Title: Local-vs-Global Consistency of Annotated Relations
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 Conjuctive Query Evaluation
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.
