[Newsletter PoDM ] Principles of Data Management, Newsletter 52, April 2025

Fri Apr 4 11:17:18 UTC 2025

Principles of Data Management, Newsletter 52, April 2025
The newsletter on Principles of Data Management from databasetheory.org

TABLE OF CONTENTS

Job Announcement: PHD POSITION, INRIA Lille
Call for Participation: ESSAI 2025 
Conference Announcement: KR 2025
PODS 2025: List of accepted, invited, and awarded papers

---------------------------------------------------------------------
PHD POSITION
Enumeration algoritms
INRIA Lille (Lille, France)
* 3 years
* URL: https://a3nm.net/work/research/offers/phd_enumeration_changes.pdf
* The LINKS team at Inria Lille is currently seeking PhD candidates to work on
the topic of “Efficient enumeration via edits”. More information on the PhD
subject and the context are at the URL above. The deadline to apply is
April 23, and the PhD would start in fall 2025; it will be co-supervised
by Antoine Amarilli and Mikaël Monet. Please circulate this offer to
potential candidates and colleagues who are looking for PhD positions,
and please contact us to apply or to ask for more details.
* Contact:
 Antoine Amarilli
 LINKS team, Inria Lille, France
 <antoine.a.amarilli at inria.fr>
 Mikaël Monet
 LINKS team, Inria Lille, France
 <mikael.monet at inria.fr>

---------------------------------------------------------------------

ESSAI 2025 EUROPEAN SUMMER SCHOOL ON ARTIFICIAL INTELLIGENCE
Call for Participation

30 June — 4 July   
Bratislava, Slovakia

https://www.essai2025.

* The European Summer School on Artificial Intelligence (ESSAI) invites participants from all over the world to attend its courses and tutorials.
* The school offers 20 courses to choose from, each consisting of five 90-minute sessions running over the course of the week. The schedule is available at https://www.essai2025.eu/courses/
* The program covers cutting-edge topics across diverse fields AI, delivered by top-class AI researchers.
* Participants can also attend the Advanced Course on AI (ACAI), a selection of short tutorials on advanced AI topics.
* Registration is now open! Early registration ends *30 April 2025*. 
* Travel grants funded by EurAI are available, please visit https://eurai.org/applications/travel_grant/ESSAI

---------------------------------------------------------------------

KR 2025 - 22ND INTERNATIONAL CONFERENCE ON PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING
November 11 - 17, 2025
Melbourne, Australia
https://kr.org/KR2025/
* Knowledge Representation and Reasoning (KR) builds on the thesis that knowledge can be represented in declarative form, suitable for processing by dedicated symbolic reasoning engines. KR has contributed to the theory and practice of various areas of AI, including agents, automated planning, robotics, and natural language processing, and to fields beyond AI, including data management, semantic web, verification, software engineering, computational biology, and cybersecurity.
* The KR conference series is the leading forum for timely, in-depth presentation of progress in the theory and practice of the representation and computational management of knowledge.
* KR 2025 will include special thematic tracks and a Recently Published Research Track, tutorials, workshops, and a Doctoral Consortium. 
* We invite contributions which clearly contribute to the formal foundations of the field or showcase applications of KR techniques. 
* KR 2025 will be co-located with ICAPS-2025: The 35th International Conference on Automated Planning and Scheduling; CPAIOR-2025: The 22nd International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research; NMR-2025: The 23rd International Workshop on Nonmonotonic Reasoning; and the Planning and Optimisation Summer School 2025.
* Important dates:   
Main track - Abstract Submission: May 7, 2025;
Main track - Paper Submission: May 12, 2025

---------------------------------------------------------------------

PODS 2025 - ACCEPTED, INVITED, AND AWARDED PAPERS

The conference will take place from June 22 to 27, 2025, in Berlin, Germany. For more details, please visit the conference website: https://2025.sigmod.org.

* KEYNOTE 

A Fine-Grained Approach to Algorithms and Complexity:
Virginia Vassilevska Williams (MIT)

* GEMS OF PODS

Querying Graph Data: Where We Are and Where To Go:
Wim Martens (University of Bayreuth)

* INVITED TUTORIALS

Local-vs-Global Consistency of Annotated Relations:
Albert Atserias (UPC)

Lower Bounds for Conjuctive Query Evaluation:
Stefan Mengel (French National Centre for Scientific Research)

* BEST PAPER AWARDS

Output-sensitive Conjunctive Query Evaluation: 
Shaleen Deep, Hangdong Zhao, Austen Fan and Paraschos Koutris

Output-Optimal Algorithms for Join-Aggregate Queries: 
Xiao Hu

* BEST NEWCOMER AWARD

Differentially Private Substring and Document Counting: 
Giulia Bernardini, Philip Bille, Inge Li Gørtz and Teresa Anna Steiner

* TEST OF TIME AWARD

Joins via Geometric Resolutions: Worst-case and Beyond:
Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, Atri Rudra

* ACCEPTED RESEARCH PAPERS 

Round 1:

Optimal (Multiway) Spatial Joins:
Ru Wang and Yufei Tao 

Optimal Dynamic Parameterized Subset Sampling:
Junhao Gan, Seeun William Umboh, Hanzhi Wang, Anthony Wirth and Zhuo Zhang

Differentially Private Hierarchical Heavy Hitters:
Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava and Zhengyi Zhou

Insert-Only versus Insert-Delete in Dynamic Query Evaluation
Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu and Dan Suciu

Polynomial Time Convergence of the Iterative Evaluation of Datalog Programs:
Sungjin Im, Benjamin Moseley, Hung Ngo and Kirk Pruhs

Output-sensitive Conjunctive Query Evaluation:
Shaleen Deep, Hangdong Zhao, Austen Fan and Paraschos Koutris 

Parallel Communication Obliviousness: One Round and Beyond:
Yufei Tao, Ru Wang and Shiyuan Deng

Below and Above Why-Provenance for Datalog Queries:
Marco Calautti, Ester Livshits, Andreas Pieris and Markus Schneider

Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue:
Marcelo Arenas, Timo Merkl, Reinhard Pichler and Cristian Riveros

Computing Range Consistent Answers to Aggregation Queries via Rewriting:
Aziz Amezian El Khalfioui and Jef Wijsen

Efficient Algorithms for k-Clustering with Noisy and Exact Oracles:
Sainyam Galhotra, Rahul Raychaudhury and Stavros Sintos

Computing A Well-Representative Summary of Conjunctive Query Results:
Pankaj Agarwal, Aryan Esmailpour, Xiao Hu, Stavros Sintos and Jun Yang 

Improved Approximation Algorithms for Relational Clustering:
Aryan Esmailpour and Stavros Sintos

Complex Event Recognition Meets Hierarchical Conjunctive Queries:
Dante Pinto and Cristian Riveros

Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration:
Pawel Gawrychowski, Florin Manea and Markus L. Schmid

Round 2:

Smallest Synthetic Witnesses for Conjunctive Queries:
Aryan Esmailpour, Boris Glavic, Xiao Hu and Stavros Sintos

Circuits and Formulas for Datalog over Semirings:
Austen Z. Fan, Paraschos Koutris and Sudeepa Roy 

Perfect Sampling in Turnstile Streams Beyond Small Moments:
David P. Woodruff, Shenghao Xie and Samson Zhou

Explaining k-Nearest Neighbors: Counterfactual and Abductive Explanations:
Pablo Barcelo, Alexander Kozachinskiy, Miguel Romero, Bernardo Subsercaseaux and Jose Verschae

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication:
Sepehr Assadi and Vihan Shah

Shapley Revisited: Tractable Responsibility Measures for Query Answers:
Meghyn Bienvenu, Diego Figueira and Pierre Lafourcade   

The Complexity of Maximal Common Subsequence Enumeration:
Giovanni Buzzega, Alessio Conte, Yasuaki Kobayashi, Kazuhiro Kurita and Giulia Punzi

Minimizing Conjunctive Regular Path Queries:
Diego Figueira, Rémi Morvan and Miguel Romero

REVISION: Towards Update-Dependent Analysis of Query Maintenance:
Xiao Hu and Qichen Wang

No Cliques Allowed: The Next Step Towards BDD/FC Conjecture:
Lucas Larroque, Piotr Ostropolski-Nalewaja and Michaël Thomazo

On the adversarial robustness of Locality-Sensitive Hashing in Hamming Space:
Mikhail Makarov, Michael Kapralov and Christian Sohler

Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces:
Qin Zhang

Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy:
Sofya Raskhodnikova and Teresa Anna Steiner

Circuit bounds for Conjunctive Queries with Self-Joins:
Austen Z. Fan, Paraschos Koutris and Hangdong Zhao 

A Quantum-Leap into Schema Matching: Beyond 1-to-1 Matchings:
Luisa Gerlach, Tobias Köppl, Stefanie Scherzinger, Nicole Schweikardt and René Zander

Restricted Chase Termination: You Want More than Fairness:
David Carral, Lukas Gerlach, Lucas Larroque and Michaël Thomazo

REVISION: Output-Optimal Algorithms for Join-Aggregate Queries:
Xiao Hu

Private Synthetic Data Generation in Small Memory:
Rayne Holland, Jason Xue, Chandra Thapa and Seyit Camtepe 

Rewriting Consistent Answers on Annotated Data:
Phokion Kolaitis, Nina Pardal, Jonni Virtema and Jef Wijsen 

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints:
Sungjin Im, Benjamin Moseley, Hung Ngo and Kirk Pruhs

Differentially Private Substring and Document Counting:
Giulia Bernardini, Philip Bille, Inge Li Gørtz and Teresa Anna Steiner

Towards practical FPRAS for #NFA: Exploiting the Power of Dependence:
Alexis de Colnet and Kuldeep S. Meel

A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity:
Stefan Mengel and Harry Vinall-Smeeth

Soft and Constrained Hypertree Width:
Matthias Lanzinger, Cem Okulmus, Reinhard Pichler, Alexander Selzer and Georg Gottlob

Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation:
Rasmus Pagh, Lukas Retschmeier, Hao Wu and Hanwen Zhang

Complex event recognition under time constraints: towards a formal framework for efficient query evaluation:
Julián García and Cristian Riveros

Fast Matrix Multiplication meets the Subdmodular Width:
Mahmoud Abo Khamis, Xiao Hu and Dan Suciu

Output-Sensitive Evaluation of Regular Path Queries:
Mahmoud Abo Khamis, Ahmet Kara, Dan Olteanu and Dan Suciu

Resilience for Regular Path Queries: Towards a Complexity Classification:
Antoine Amarilli, Wolfgang Gatterbauer, Neha Makhija and Mikaël Monet

A Theoretical Framework for Distribution-Aware Dataset Search:
Aryan Esmailpour, Sainyam Galhotra, Rahul Raychaudhury and Stavros Sintos

---------------------------------------------------------------------

The next issue of this newsletter is scheduled for early June 2025. Please submit your announcements to newsletter-owner at databasetheory.org until May 31, 2025. Please follow the formatting instructions at databasetheory.org/newsletter.

Past issues of the newsletter can be found at databasetheory.org/newsletter.