PODS Invited Tutorials
Tutorial 1
Speaker: Mahmoud Abo Khamis (RelationalAI)
Title: Query Optimization and Evaluation via Information Theory
Abstract: Conjunctive queries (CQs) are among the most fundamental queries in database systems, and they also subsume (hyper)graph pattern matching problems, and constraint satisfaction problems (CSP), among others. Before we evaluate a CQ Q, we typically have upfront some statistics S about the input database instance. Given a query Q and statistics S, two key questions are: (1) how do we estimate the output size of Q? and (2) how do we evaluate Q efficiently? Information theory has proven itself to be a powerful tool for answering both questions. This is because it allows us to *compress* the huge space of possible database instances into the much smaller and manageable space of entropies.
In this paper, we present an information-theoretic framework for proving upper bounds on the output size of a CQ under a wide range of statistics. The framework is the result of unification of several lines of work in this area, including the AGM-bound [FOCS’08] and the GLVV-bound [JACM’12] among others. We take the framework one step further and use it to prove upper bounds on *intermediate relations* that are computed during the evaluation of a CQ under some query plan, using various notions of query plans. This allows us to get accurate costs of query plans and pick the best one. By using the most general notion of query plans that is known, this idea leads to a unified algorithm for evaluating CQs under a wide range of statistics, which is called PANDA. For any CQ Q and and statistics S, PANDA achieves a runtime matching the “submodular width” defined by Marx [JACM’13], which is the best known runtime using combinatorial algorithms. PANDA was also recently extended to incorporate fast matrix multiplication [PODS’25]. The development of PANDA was only possible thanks to a preceding rich literature on query evaluation studying various special classes of CQs and statistics.
Bio: Mahmoud Abo Khamis is a Senior Computer Scientist at RelationalAI, where he has worked since 2017. He received his Ph.D. in Computer Science and Engineering from the State University of New York at Buffalo in 2016. Prior to joining RelationalAI, he was a Senior Database Engineer at Infor from 2015 to 2017. His research interests include database systems and theory, in-database machine learning, query optimization and evaluation, information theory, and beyond worst-case analysis. His work has been recognized with a Test-of-Time Award at ACM PODS 2025, three Best Paper Awards at ACM SIGMOD 2025 and ACM PODS 2022 and 2016, three ACM SIGMOD Research Highlight Awards, and the 2016 Best CSE Dissertation Award from SUNY Buffalo. His work has also received multiple invitations to the Journal of the ACM, ACM STOC, and ACM TODS. He is on the Editorial Board of ACM TODS, and serves on the program committees of ACM PODS, ICDT, and ICALP among others.
Tutorial 2
Speaker: Karl Bringmann (ETH Zurich)
Title: Fine-grained Complexity of Database Queries
Abstract: Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds. Starting from a popular conjecture about the time complexity of a core problem (e.g., the Strong Exponential Time Hypothesis for the Satisfiability problem), we can design fine-grained reductions to transfer the conjectured intractability to other problems, yielding conditional lower bounds. After initial results in the 90s, the field has matured over the last 15 years, demonstrating its usefulness across many areas of computer science including graph algorithms, optimization, computational geometry, and string processing.
Naturally, fine-grained complexity has also found compelling applications in database theory, specifically for join queries and, more generally, conjunctive queries, which generalize graph pattern matching problems that are fundamental in graph algorithms. In this talk, we will discuss recent results on listing, enumeration, and direct access algorithms for join queries and conjunctive queries, thereby exploring the intersection of database theory and graph algorithms through the lens of fine-grained complexity.
Bio: Karl Bringmann is a professor for theoretical computer science at ETH Zurich. He received his Ph.D. in Computer Science from Saarland University and Max Planck Institute for Informatics in 2014. After postdoctoral stays at ETH Zurich and the Simons Institute for the Theory of Computing, Berkeley, he was a senior researcher at Max Planck Institute for Informatics from 2016 to 2019, and a professor at Saarland University from 2019 to 2025, before joining ETH Zurich as a professor in January 2026. His research focuses on fine-grained complexity theory, i.e., proving conditional lower bounds based on conjectures such as the Strong Exponential Time Hypothesis, and the design of efficient algorithms that match these lower bounds. With this combination of algorithm design and conditional lower bounds he aims to achieve near-optimal algorithms for fundamental problems from diverse application areas, including discrete optimization, computational geometry, graph and string algorithms, and database theory. His work has been recognized with an ERC Starting Grant, the EATCS Presburger Award, and the EATCS Distinguished Dissertation Award. He serves on program committees of top conferences in theoretical computer science, such as FOCS 2026, SODA 2026, and STOC 2022, and he was program committee co-chair for ICALP 2024.