PODS 2022 - Program

Submitted by Pablo Barcelo on Tue, 05/03/2022 - 23:35

Monday June 13th

8:00 - 10:30: Session 1, PODS Opening, Keynote Talk, and Streaming (Session chairs: Leonid Libkin and Pablo Barceló)

(1.1) 8:00 - 8:10. Opening.
(1.2) 8:10 - 9:30. Plenary keynote talk. Frank Neven. Robustness against read committed: a free transactional lunch.
(1.3) 9:30 - 9:50. Miklos Ajtai, Vladimir Braverman, T.S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff and Samson Zhou. The White-Box Adversarial Data Stream Model.
(1.4) 9:50 - 10:10: Rajesh Jayaram, David P. Woodruff and Samson Zhou. Truly Perfect Samplers for Data Streams and Sliding Windows.
(1.5) 10:10 - 10:30. Sourav Chakraborty, Kuldeep S. Meel and N. V. Vinodchandran. Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size.

11:00 - 12:20: Session 2, Query Evaluation (Session chair: Cristian Riveros)

(2.1) 11:00 - 11:20. Mahmoud Abo Khamis, George Chichirim, Antonia Kormpa and Dan Olteanu. The Complexity of Boolean Conjunctive Queries with Intersection Joins.
(2.2) 11:20 - 11:40. Yilei Wang and Ke Yi. Query Evaluation by Circuits.
(2.3) 11:40 - 12:00. Markus L. Schmid and Nicole Schweikardt. Query Evaluation over SLP-Represented Document Databases With Complex Document Editing.
(2.4) 12:00 - 12:20. Matthias Lanzinger. The Complexity of Conjunctive Queries with Degree 2.

14:00 - 15:20: Session 3, PODS Awards (Session chair: Pablo Barceló)

(3.1) PODS Test-of-Time Awardees.
(3.1.1) 14:00 - 14:20. Hung Ngo, Ely Porat, Christopher Re, Atri Rudra. Worst-case optimal join algorithms
(3.1.2) 14:20 - 14:40. Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, Ke Yi. Mergeable Summaries
(3.2) PODS Best Paper Awardees.
(3.2.1) 14:40 - 15:00. Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu and Yisu Remy Wang. Convergence of Datalog over (Pre-) Semirings
(3.2.2) 15:00 - 15:20. Jelani Nelson and Huacheng Yu. Optimal Bounds for Approximate Counting

16:00 - 18:20: Session 4, Invited Tutorial, Gems of PODS, and Sampling (Session chair: Atri Rudra)

(4.1) 16:00 - 17:10. Tutorial. Rediet Abebe. Data as Inequality.
(4.2) 17:10 - 18:10. Gems of PODS.
( 4.2.1) 17:10 - 17:35. Yufei Tao. Algorithmic Techniques for Independent Query Sampling.
(4.2.2) 17:35 - 18:00. Nicole Schweikardt. Document Spanners - A Brief Overview of Concepts, Results, and Recent Developments
(4.3) 18:00 - 18:20. Flavio Chierichetti, Ravi Kumar and Silvio Lattanzi. The Gibbs--Rand Model.

Tuesday June 14th

11:00 - 12:20: Session 5, Graph Data (Session chair: Domagoj Vrgoc)

(5.1) 11:00 - 11:20. Wim Martens and Tina Popp. The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs.
(5.2) 11:20 - 11:40. Shangqi Lu, Wim Martens, Matthias Niewerth and Yufei Tao. Optimal Algorithms for Multiway Search on Partial Orders.
(5.3) 11:40 - 12:00. Diego Figueira, Artur Jez and Anthony Widjaja Lin. Data Path Queries over Embedded Graph Databases.
(5.4) 12:00 - 12:20. Diego Figueira and Varun Ramanathan. When is the Evaluation of Extended CRPQ Tractable?

14:00 - 15:20: Session 6, Privacy and Embeddings (Session chair: Xiao Hu)

(6.1) 14:00 - 14:20. Yi Li and Mingmou Liu. Lower Bounds for Sparse Oblivious Subspace Embeddings.
(6.2) 14:20 - 14:40. Lijie Hu, Shuo Ni, Hanshen Xiao and Di Wang. High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data.
(6.3) 14:40 - 15:00. Olga Ohrimenko, Anthony Wirth and Hao Wu. Randomize the Future: Asymptotically Optimal Locally Private Frequency Estimation Protocol for Longitudinal Data.
(6.4) 15:00 - 15:20. Wei Dong and Ke Yi. A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries.

16:00 - 18:30: Session 7, Invited Tutorial, Enumeration and Counting (Session chair: Rajesh Jayaram)

(7.1) 16:00 - 17:10. Tutorial. Wim Martens. Towards Theory for Real-World Data.
(7.2) 17:10 - 17:30. Carsten Lutz and Marcin Przybyłko. Efficiently Enumerating Answers to Ontology-Mediated Queries.
(7.3) 17:30 - 17:50. Antoine Amarilli, Louis Jachiet, Martín Muñoz and Cristian Riveros. Efficient Enumeration for Annotated Grammars.
(7.4) 17:50 - 18:10. Kazuhiro Kurita, Yasuaki Kobayashi and Kunihiro Wasa. Linear-Delay Enumeration for Minimal Steiner Problems.
(7.5) 18:10 - 18:30. Jacob Focke, Leslie Ann Goldberg, Marc Roth and Stanislav Živný. Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.

Wednesday June 15th

11:00 - 12:20: Session 8, Query Processing (Session chair: Nicole Schweikardt)

(8.1) 11:00 - 11:20. Georg Gottlob, Matthias Lanzinger, Cem Okulmus and Reinhard Pichler. Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth.
(8.2) 11:20 - 11:40. Steffen van Bergerem, Martin Grohe and Martin Ritzert. On the Parameterized Complexity of Learning First-Order Logic.
(8.3) 11:40 - 12:00. Jarosław Kwiecień, Jerzy Marcinkowski and Piotr Ostropolski-Nalewaja. Determinacy of Real Conjunctive Queries. The Boolean Case.
(8.4) 12:00 - 12:20. Piotr Ostropolski-Nalewaja, Jerzy Marcinkowski, David Carral and Sebastian Rudolph. A Journey to the Frontiers of Query Rewritability.

14:00 - 15:00: Session 9, Uncertainty and Incompleteness (Session chair: Frank Neven) 

(9.1) 14:00 - 14:20. Marco Calautti, Georg Gottlob and Andreas Pieris. Non-Uniformly Terminating Chase: Size and Complexity.
(9.2) 14:20 - 14:40. Meghyn Bienvenu, Gianluca Cima and Víctor Gutiérrez-Basulto. LACE: A Logical Approach to Collective Entity Resolution.
(9.3) 14:40 - 15:00. Marco Calautti, Ester Livshits, Andreas Pieris and Markus Schneider. Uniform Operational Consistent Query Answering.

16:00 - 17:20: Session 10, Counting and Dichotomies (Session chair: Wim Martens) 

(10.1) 16:00 - 16:20. Marco Calautti, Ester Livshits, Andreas Pieris and Markus Schneider. Counting Database Repairs Entailing a Query: The Case of Functional Dependencies.
(10.2) 16:20 - 16:40. Hendrik Fichtenberger and Pan Peng. Approximately Counting Subgraphs in Data Streams.
(10.3) 16:40 - 17:00. Karl Bringmann, Nofar Carmeli and Stefan Mengel. Tight Fine-Grained Bounds for Direct Access on Join Queries.
(10.4) 17:00 - 17:20. Miika Hannula and Jef Wijsen. A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys.