Accepted Papers for PODS
Round 1
- Bag Semantics Query Containment: The CQ vs. UCQ Case and Other Stories
Jerzy Marcinkowski (University of Wrocław)*; Piotr Ostropolski-Nalewaja (University of Wrocław)
- Tractability Frontiers of the Shapley Value for Aggregate Conjunctive Queries
Benny Kimelfeld (Technion - Israel Institute of Technology & RelationalAI); Christoph Standke (RWTH Aachen University)*
- A Unifying Algorithm for Hierarchical Queries
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)
- Codd’s Theorem for Databases over Semirings
Guillermo Badia (University of Queensland); Phokion G. Kolaitis (UC Santa Cruz and IBM Research - Almaden)*; Carles Noguera (University of Siena)
- Finding Heavy-Hitters with Optimal State Changes
William Swartworth (Carnegie Mellon University)*; David Woodruff (Carnegie Mellon University)
- The Space-Time Complexity of Sum-Product Queries
Kyle Deeds (University of Washington); Timo Merkl (TU Vienna); Reinhard Pichler (TU Wien)*; Dan Suciu (University of Washington)
- Query answering under volume-based diversity functions
Marcelo Arenas (PUC Chile); Timo Merkl (TU Vienna); Reinhard Pichler (TU Wien)*; Cristian Riveros (Pontificia Universidad Católica de Chile)
- Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation
Shangqi Lu (Hong Kong University of Science and Technology (Guangzhou)); Yufei Tao (The Chinese University of Hong Kong)*
- Representation Obliviousness and Pseudodeterminism in Streaming Algorithms
Sourav Chakraborty (Indian Statistical Institute); Michael Chen (Iowa State University); A. Pavan (Iowa State University)*; N. V. Vinodchandran (University of Nebraska, Lincoln)
- Clustering with Set Outliers and Applications in Relational Clustering
Vaishali Surianarayanan (University of California Santa Barbara); Neeraj Kumar (Meta); Stavros Sintos (University of Illinois Chicago)*
- On the Expressiveness of Languages for Querying Property Graphs in Relational Databases
Hadar Rotschield (Hebrew university of Jerusalem, Israel)*; Liat Peterfreund (The Hebrew University of Jerusalem)
- A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
Rachana Gusain (Indian Institute of Science, Bangalore); Saladi Rahul (Indian Institute of Science, Bangalore)*; Aditya Subramanian (Indian Institute of Science, Bangalore)
Round 2
- Near-Optimality for Single-Source Personalized PageRank
Xinpeng Jiang (Nanyang Technological University); Haoyu Liu (Nanyang Technological University)*; Siqiang Luo (Nanyang Technological University); Xiaokui Xiao (National University of Singapore)
- Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings
Yi Li (Nanyang Technological University); Mingmou Liu (Nanjing University)*
- Towards Parameterized Hardness on Maintaining Conjunctive Queries
Qichen Wang (Nanyang Technological University)*
- Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity
Kaiwen Liu (Indiana University Bloomington); Qin Zhang (Indiana University Bloomington)*
- FPT Parameterisations of Fractional and Generalised Hypertree Width
Daniel Unterberger (TU Wien)*; Matthias Lanzinger (TU Wien); Igor Razgon (Durham University)
- Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
Mahmoud Abo-Khamis (RelationalAI); Hubie Chen (King's College London)*
- PANDAExpress: a Simpler and Faster PANDA Algorithm
Mahmoud Abo Khamis (RelationalAI); Hung Ngo (RelationalAI Inc.)*; Dan Suciu (University of Washington)
- Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
Nofar Carmeli (Inria, LIRMM, University of Montpellier, CNRS); Nikolaos Tziavelis (University of California, Santa Cruz)*
- Recursive querying of neural networks via weighted structures
Martin Grohe (RWTH Aachen University); Christoph Standke (RWTH Aachen University); Juno Steegmans (Hasselt University); Jan Van den Bussche (Hasselt University)*
- Bound-Adorned Datalog
Christian Fattebert (EPFL); Zhekai Jiang (EPFL)*; Christoph Koch (EPFL); Reinhard Pichler (TU Wien); Qichen Wang (Nanyang Technological University)
- Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries
Mahmoud Abo Khamis (RelationalAI)*; Alexandru-Mihai Hurjui (University of Zurich); Ahmet Kara (OTH Regensburg); Dan Olteanu (University of Zurich); Dan Suciu (University of Washington)
- The Expressive Power of Query Languages for Computing and Transforming Graph Embeddings
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)
- On Sketching Trimmed Statistics
Honghao Lin (Carnegie Mellon University); Hoai-An Nguyen (Carnegie Mellon University)*; David P. Woodruff (Carnegie Mellon University)
- Subset Sampling over Joins
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)
- Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time
Florian Kerschbaum (University of Waterloo); Steven Lee (University of Waterloo); Hao Wu (University of Waterloo)*
- Faster Relational Algorithms Using Geometric Data Structures
Aryan Esmailpour (University of Illinois Chicago); Stavros Sintos (University of Illinois Chicago)*
- Analysis of Shuffling Beyond Pure Local Differential Privacy
Shun Takagi (LY Corporation)*; Seng Pei Liew (LY Corporation)
- Deterministic Lower Bounds for k-Edge Connectivity in the Distributed Sketching Model
Peter Robinson (Augusta University)*; Ming Ming Tan (Augusta University)
- Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries
Xiao Hu (University of Waterloo)*; Jinchao Huang (The Chinese University of Hong Kong)
- Optimal Enumeration of Regular Pattern Matches
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)
- Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries
Christian Janos Lebeda (Inria, Université de Montpellier, INSERM)*; Aleksandar Nikolov (University of Toronto); Haohua Tang (University of Toronto)
- Bounding the Fragmentation of B-trees Subject to Batched Insertions
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)
- Concurrent Composition for Differentially Private Continual Mechanisms
Monika Henzinger (Institute of Science and Technology Austria (ISTA)); Roodabeh Safavi (Institute of Science and Technology Austria (ISTA))*; Salil Vadhan (Harvard University)
- Improved Accuracy for Private Continual Cardinality Estimation in Fully Dynamic Streams via Matrix Factorization
Joel Daniel Andersson (Institute of Science and Technology Austria); Palak Jain (Boston University); Satchit Sivakumar (Boston University)*
- Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations
Mahmoud Abo Khamis (RelationalAI); Eden Chmielewski (University of Zurich); Andrei Draghici (University of Zurich); Ahmet Kara (OTH Regensburg); Dan Olteanu (University of Zurich)*
- Coresets for Robust Query Optimization
Pankaj Agarwal (Duke University); Rahul Raychaudhury (Duke University); Stavros Sintos (University of Illinois Chicago)*; Haibo Xiu (Duke Univerisity); Jun Yang (Duke University)
- Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
Honghao Lin (Carnegie Mellon University)*; Hoai-An Nguyen (Carnegie Mellon University); William Swartworth (Carnegie Mellon University); David Woodruff (Carnegie Mellon University)
- Tight Lower Bounds for $\ell_2$ Sampling
William Swartworth (Voleon)*; David Woodruff (Carnegie Mellon University)
- Improved Lower Bounds for Privacy under Continual Release
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)