PODS Detailed Program
PODS Keynote
Keynote Talk: Models are data too: Towards expressive querying of machine-learning models
Speaker: Jan Van den Bussche (Hasselt University)
PODS 1
Gems of PODS: Enumeration Theory through the Lens of Database Challenges
Speaker: Benny Kimelfeld (Technion - Israel Institute of Technology)
PODS 2
Test of Time Award:FAQ: Questions Asked Frequently.
Authors: Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra.
Best Newcomer Award: Near-Optimality for Single-Source Personalized PageRank
Authors: Xinpeng Jiang (Nanyang Technological University); Haoyu Liu (Nanyang
Technological University)*; Siqiang Luo (Nanyang Technological University); Xiaokui Xiao (National
University of Singapore)
Paper: Clustering with Set Outliers and Applications in Relational Clustering
Authors: Vaishali Surianarayanan (University of California Santa Barbara); Neeraj Kumar
(Meta); Stavros Sintos (University of Illinois Chicago)*
Paper: Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and
Euclidean Separation
Authors: Shangqi Lu (Hong Kong University of Science and Technology (Guangzhou)); Yufei
Tao (The Chinese University of Hong Kong)*
PODS 3
Paper: Size Bound-Adorned Datalog
Authors: Christian
Fattebert (EPFL); Zhekai Jiang (EPFL)*; Christoph Koch (EPFL); Reinhard Pichler (TU Wien); Qichen Wang
(Nanyang Technological University)
Paper: Recursive querying of neural networks via weighted structures
Authors: Martin Grohe (RWTH Aachen University); Christoph Standke (RWTH Aachen
University); Juno Steegmans (Hasselt University); Jan Van den Bussche (Hasselt University)*
Paper: A Logical View of GNN-Style Computation and the Role of Activation
Functions
Authors: Pablo Barceló (Universidad Católica de Chile); Floris Geerts
(University of Antwerp); Matthias Paul Lanzinger (TU Wien); Klara Pakhomenko (UHasselt)*; Jan Van den
Bussche (UHasselt)
Paper: On the Expressiveness of Languages for Querying Property Graphs in
Relational Databases
Authors: Hadar Rotschield (Hebrew university of Jerusalem,
Israel)*; Liat Peterfreund (The Hebrew University of Jerusalem)
Paper: Bag Semantics Query Containment: The CQ vs. UCQ Case and Other
Stories
Authors: Jerzy Marcinkowski (University of Wrocław)*; Piotr Ostropolski-Nalewaja
(University of Wrocław)
PODS 4
Best Paper Award: Unbiased Insights: Optimal Streaming Algorithms for
$\ell$p Sampling, the Forget Model, and Beyond
Authors: Honghao Lin (Carnegie Mellon
University)*; Hoai-An Nguyen (Carnegie Mellon University); William Swartworth (Carnegie Mellon
University); David Woodruff (Carnegie Mellon University)
Paper: Tight Lower Bounds for ℓ2 Sampling
Authors:
William Swartworth (Carnegie Mellon University)*; David Woodruff (Carnegie Mellon University)
Paper: Finding Heavy-Hitters with Optimal State Changes
Authors: William Swartworth (Carnegie Mellon University)*; David Woodruff (Carnegie Mellon
University)
Paper: Representation Obliviousness and Pseudodeterminism in Streaming
Algorithms
Authors: Sourav Chakraborty (Indian Statistical Institute); Michael Chen
(Iowa State University); A. Pavan (Iowa State University)*; N. V. Vinodchandran (University of Nebraska,
Lincoln)
Paper: Frequency Moments in Noisy Streaming and Distributed Data under
Mismatch Ambiguity
Authors: Kaiwen Liu (Indiana University Bloomington); Qin Zhang
(Indiana University Bloomington)*
Paper: On Sketching Trimmed Statistics
Authors: Honghao
Lin (Carnegie Mellon University); Hoai-An Nguyen (Carnegie Mellon University)*; David P. Woodruff
(Carnegie Mellon University)
PODS 5
Paper: Bounding the Fragmentation of B-trees Subject to Batched Insertions
Authors: Michael A. Bender (Stony Brook University and RelationalAI); Aaron Bernstein
(NYU); Nairen Cao (NYU); Alex Conway (Cornell Tech); Martin Farach-Colton (NYU); Hanna Komlós (Simons
Institute and Max Planck Institute for Informatics); Yarin Shechter (NYU)*; Nicole Wein (University of
Michigan)
Paper: Faster Relational Algorithms Using Geometric Data Structures
Authors: Aryan Esmailpour (University of Illinois Chicago); Stavros Sintos (University
of Illinois Chicago)*
Paper: A Bouquet of Results on Maximum Range Sum: General Techniques and
Hardness Reductions
Authors: Rachana Gusain (Indian Institute of Science, Bangalore); Saladi Rahul (Indian
Institute of Science, Bangalore)*; Aditya Subramanian (Indian Institute of Science, Bangalore)
Paper: Tractability Frontiers of the Shapley Value for Aggregate
Conjunctive Queries
Authors: Benny Kimelfeld (Technion - Israel Institute of Technology & RelationalAI);
Christoph Standke (RWTH Aachen University)*
Paper: Codd’s Theorem for Databases over Semirings
Authors: Guillermo Badia (University of Queensland); Phokion G. Kolaitis (UC Santa Cruz
and IBM Research - Almaden)*; Carles Noguera (University of Siena)
PODS 6
Distinguished Paper: FPT Parameterisations of Fractional and Generalised
Hypertree Width
Authors: Daniel Unterberger (TU Wien)*; Matthias Lanzinger (TU Wien); Igor Razgon
(Durham University)
Paper: A Unifying Algorithm for Hierarchical Queries
Authors: Mahmoud Abo Khamis (RelationalAI)*; Jesse Comer (University of Pennsylvania);
Phokion G. Kolaitis (UC Santa Cruz & IBM Research); Sudeepa Roy (Duke University); Val Tannen (University
of Pennsylvania)
Paper: Towards Parameterized Hardness on Maintaining Conjunctive Queries
Authors: Qichen Wang (Nanyang Technological University)*
Paper: Maintaining Queries under Updates Using Heavy-Light Partitioning of
the Input Relations
Authors: Mahmoud Abo Khamis (RelationalAI); Eden Chmielewski (University of Zurich);
Andrei Draghici (University of Zurich); Ahmet Kara (OTH Regensburg); Dan Olteanu (University of Zurich)*
Paper: Acyclic Conjunctive Regular Path Queries are no Harder than
Corresponding Conjunctive Queries
Authors: Mahmoud Abo Khamis (RelationalAI)*; Alexandru-Mihai Hurjui (University of
Zurich); Ahmet Kara (OTH Regensburg); Dan Olteanu (University of Zurich); Dan Suciu (University of
Washington)
Paper: Optimal Enumeration of Regular Pattern Matches
Authors: Pawel Gawrychowski (University of Wroclaw); Florin Manea (University of
Göttingen)*; Paul Sarnighausen-Cahn (Institute for Computer Science, Georg-August-Universität Göttingen,
Göttingen); Stefan Siemer (Georg-August University Göttingen)
PODS 7
Tutorial: Query Optimization and Evaluation via Information Theory
Speaker: Mahmoud Abo Khamis (RelationalAI)
Distinguished Paper: PANDAExpress: a Simpler and Faster PANDA Algorithm
Authors: Mahmoud Abo Khamis (RelationalAI); Hung Ngo (RelationalAI Inc.)*; Dan Suciu
(University of Washington)
Paper: Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
Authors: Mahmoud Abo-Khamis (RelationalAI); Hubie Chen (King's College London)*
PODS 8
Tutorial: Fine-grained Complexity of Database Queries
Speaker: Karl Bringmann (ETH Zurich)
Paper: Fine-Grained Dichotomies for Conjunctive Queries with Minimum or
Maximum
Authors: Nofar Carmeli (Inria, LIRMM, University of Montpellier, CNRS); Nikolaos
Tziavelis (University of California, Santa Cruz)*
Paper: The Space-Time Complexity of Sum-Product Queries
Authors: Kyle Deeds (University of Washington); Timo Merkl (TU Vienna); Reinhard
Pichler (TU Wien)*; Dan Suciu (University of Washington)
PODS 9
Paper: Optimal Pure Differentially Private Sparse Histograms in
Deterministic Linear Time
Authors: Florian Kerschbaum (University of Waterloo); Steven Lee (University of
Waterloo); Hao Wu (University of Waterloo)*
Paper: Analysis of Shuffling Beyond Pure Local Differential Privacy
Authors: Shun Takagi (LY Corporation)*; Seng Pei Liew (LY Corporation)
Paper: Weighted Fourier Factorizations: Optimal Gaussian Noise for
Differentially Private Marginal and Product Queries
Authors: Christian Janos Lebeda (Inria, Université de Montpellier, INSERM)*; Aleksandar
Nikolov (University of Toronto); Haohua Tang (University of Toronto)
Paper: Concurrent Composition for Differentially Private Continual
Mechanisms
Authors: Monika Henzinger (Institute of Science and Technology Austria (ISTA));
Roodabeh Safavi (Institute of Science and Technology Austria (ISTA))*; Salil Vadhan (Harvard University)
Paper: Improved Accuracy for Private Continual Cardinality Estimation in
Fully Dynamic Streams via Matrix Factorization
Authors: Joel Daniel Andersson (Institute of Science and Technology Austria); Palak
Jain (Boston University); Satchit Sivakumar (Boston University)*
Paper: Improved Lower Bounds for Privacy under Continual Release
Authors: Bardiya Aryanfard (Institute of Science and Technology Austria)*; Monika
Henzinger (Institute of Science and Technology Austria); David Saulpic (Université Paris Cité, CNRS); A.
R. Sricharan (University of Vienna)
PODS 10
Paper: Coresets for Robust Query Optimization
Authors: Pankaj Agarwal (Duke University); Rahul Raychaudhury (Duke University);
Stavros Sintos (University of Illinois Chicago)*; Haibo Xiu (Duke University); Jun Yang (Duke University)
Paper: Subset Sampling over Joins
Authors: Aryan Esmailpour (University of Illinois Chicago); Xiao Hu (University of
Waterloo)*; Jinchao Huang (The Chinese University of Hong Kong); Stavros Sintos (University of Illinois
Chicago)
Paper: Towards Output-Optimal Uniform Sampling and Approximate Counting for
Join-Project Queries
Authors: Xiao Hu (University of Waterloo)*; Jinchao Huang (The Chinese University of
Hong Kong)
Paper: Deterministic Lower Bounds for k-Edge Connectivity in the
Distributed Sketching Model
Authors: Peter Robinson (Augusta University)*; Ming Ming Tan (Augusta University)
Paper: Query answering under volume-based diversity functions
Authors: Marcelo Arenas (PUC Chile); Timo Merkl (TU Vienna); Reinhard Pichler (TU
Wien)*; Cristian Riveros (Pontificia Universidad Católica de Chile)
Paper: Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings
Authors: Yi Li (Nanyang Technological University); Mingmou Liu (Nanjing University)*